找规律，推公式，快速幂
Partition
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2333 Accepted Submission(s): 924
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.
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≤10 9).
Output Output the required answer modulo 10 9+7 for each test case, one per line.
Sample Input
2 4 2 5 5
Sample Output
5 1
Source 2013 Multi-University Training Contest 1
#include#include #include #include #include using namespace std; typedef long long int LL; const long long int MOD=1e9+7; LL POW2(int x) { LL ret=1LL; LL e=2LL; while(x) { if(x&1) ret=ret*e%MOD; e=e*e%MOD; x>>=1; } return ret%MOD; } int main() { int T_T; scanf("%d",&T_T); while(T_T--) { int a,b,t; scanf("%d%d",&a,&b); t=a-b; if(t<0) { printf("0\n"); continue; } else if(t==0) { printf("1\n"); continue; } else if(t==1) { printf("2\n"); continue; } else if(t==2) { printf("5\n"); continue; } else printf("%I64d\n",((t+3)%MOD*POW2(t-2)%MOD)%MOD); } return 0; }