Partition
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2472 Accepted Submission(s): 978
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
对于1 <= k < n，我们能够等效为n个点排成一列，并取出当中的连续k个，这连续的看K个两端断开；
1、若取得是这K个点包含端点（我们仅仅考虑一个端点的情况），还剩下（n-k-1）个间隔，
每一个间隔有断开和闭合两种状态，故有2^（n-k-1），最后乘以2；
2、若取得是这K个点不包含端点，这连续的K个点有（n-k-1）种取法，还剩下（n-k-2）个间隔，
故有2^（n-k-2）*（n-k-1）；
总计2 ∗ 2^(n – k − 1) + 2^(n – k − 2) ∗ (n – k − 1) = (n – k + 3) * 2^(n – k − 2)。
#include"stdio.h"
#include"string.h"
#include"queue"
#include"vector"
#include"algorithm"
using namespace std;
#define LL __int64
const int mod=1000000007;
int main()
{
int T,i,n,k;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
if(n<k)
printf("0\n");
else if(n==k)
printf("1\n");
else
{
LL d=n-k,s1,t;
if(d==1) printf("2\n");
else
{
s1=d+3;
d-=2;
LL aa=2,tmp=1;
while(d)
{
if(d&1)
tmp*=aa;
d/=2;
aa=(aa*aa)%mod;
tmp%=mod;
}
printf("%I64d\n",(tmp*s1)%mod);
}
} }
return 0;
}