TRANSP2 - Transposing is Even More Fun
题意翻译
现在存储了一个$ 2^a * 2^b $的矩阵
• 矩阵在内存中是按行存储的
• 现在你想求它的转置
• 唯一允许的操作是交换两个内存位置的值
• 求最少需要的次数?
• 4e5 组询问,每组询问 a + b <= 1e6
感谢@IceFox 提供的翻译
题目描述
输入输出格式
输入格式
First line of input contains number of test cases c (1<=c<=400000). Each test case consists of two integers a,b (0<=a+b<=1000000).
输出格式
For each test case output minimal number of swaps required to transpose an 2ax2b array. As it can be quite large, you have to output its remainder when divided by 1000003 (yes, it's a prime number :).
输入输出样例
输入样例 #1
3
1 1
2 2
5 7
输出样例 #1
1
6
3744