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
4 2
5 5
Sample Output
5
1
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+,M=1e6+,inf=1e9,mod=1e9+;
struct is
{
ll a[][];
};
is juzhenmul(is a,is b,ll hang ,ll lie)
{
int i,t,j;
is ans;
memset(ans.a,,sizeof(ans.a));
for(i=;i<=hang;i++)
for(t=;t<=lie;t++)
for(j=;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&) ans=juzhenmul(ans,a,,);
a=juzhenmul(a,a,,);
x>>=;
}
return ans;
}
ll getans(ll x)
{
if(x==)
return ;
if(x==)
return ;
is ans,base;
memset(ans.a,,sizeof(ans.a));
ans.a[][]=;
ans.a[][]=;
base.a[][]=;
base.a[][]=;
base.a[][]=;
base.a[][]=;
ans=quickpow(ans,base,x-);
return (ans.a[][]*+ans.a[][])%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\n",getans(x-y+));
else
printf("0\n");
}
return ;
}