Partition
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1388 Accepted Submission(s): 573
Problem Description
Define f(n) as the number of ways to perform n in format of the sum of some positive integers. For instance, when n=4, we have
4=1+1+1+1
4=1+1+2
4=1+2+1
4=2+1+1
4=1+3
4=2+2
4=3+1
4=4
totally 8 ways. Actually, we will have f(n)=2(n-1) after observations.
Given a pair of integers n and k, your task is to figure out how many times that the integer k occurs in such 2(n-1) ways. In the example above, number 1 occurs for 12 times, while number 4 only occurs once.
4=1+1+1+1
4=1+1+2
4=1+2+1
4=2+1+1
4=1+3
4=2+2
4=3+1
4=4
totally 8 ways. Actually, we will have f(n)=2(n-1) after observations.
Given a pair of integers n and k, your task is to figure out how many times that the integer k occurs in such 2(n-1) ways. In the example above, number 1 occurs for 12 times, while number 4 only occurs once.
Input
The first line contains a single integer T(1≤T≤10000), indicating the number of test cases.
Each test case contains two integers n and k(1≤n,k≤109).
Each test case contains two integers n and k(1≤n,k≤109).
Output
Output the required answer modulo 109+7 for each test case, one per line.
Sample Input
2 4 2 5 5
Sample Output
5 1
Source
Recommend
liuyiding
题意: 略:
思路: 推到出 2 ^ (m - 3) * (m + 2) m = n - k + 1;
用快速矩阵幂
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <vector> using namespace std; const int V = 100000 + 50; const int MaxN = 100000 + 5; const int mod = 1000000000 + 7; int T, n, k; __int64 pow_mod(__int64 b) { __int64 a = 2; __int64 res = 1; while(b) { if(b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res % mod; } int main() { int i, j; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &k); int m = n - k + 1; if(k > n) printf("0\n"); else if(m <= 2) printf("%d\n", m); else if(m == 3) printf("5\n"); else printf("%I64d\n", (pow_mod(m - 3) * (m + 2) % mod) % mod); } }