Partition
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
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
思路：递推式a[n]=2*a[n-1]+2^(n-2);
#include<bits/stdc++.h> using namespace std; #define ll __int64 #define esp 0.00000000001 const int N=3e5+10,M=1e6+10,inf=1e9,mod=1e9+7; struct is { ll a[10][10]; }; is juzhenmul(is a,is b,ll hang ,ll lie) { int i,t,j; is ans; memset(ans.a,0,sizeof(ans.a)); for(i=1;i<=hang;i++) for(t=1;t<=lie;t++) for(j=1;j<=lie;j++) { ans.a[i][t]+=(a.a[i][j]*b.a[j][t]); ans.a[i][t]%=mod; } return ans; } is quickpow(is ans,is a,ll x) { while(x) { if(x&1) ans=juzhenmul(ans,a,2,2); a=juzhenmul(a,a,2,2); x>>=1; } return ans; } ll getans(ll x) { if(x==1) return 1; if(x==2) return 2; is ans,base; memset(ans.a,0,sizeof(ans.a)); ans.a[1][1]=1; ans.a[2][2]=1; base.a[1][1]=2; base.a[1][2]=0; base.a[2][1]=1; base.a[2][2]=2; ans=quickpow(ans,base,x-2); return (ans.a[1][1]*2+ans.a[2][1])%mod; } int main() { ll x,y,z,i,t; int T; scanf("%d",&T); while(T--) { scanf("%I64d%I64d",&x,&y); if(x>=y) printf("%I64d ",getans(x-y+1)); else printf("0 "); } return 0; }