Partition

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1697 Accepted Submission(s): 688

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⁹).

Output

Output the required answer modulo 10⁹+7 for each test case, one per line.

Sample Input

2
4 2
5 5

Sample Output

5
1

　　题意是对一个数n有2^(n-1)这么多种分解形式，问这些分解式中某一个数字出现了多少次。

　　这一题在排位赛的时候发现了规律，然后按照递推式子Sn=2*Sn-2^(n-3) 其中n>=3 ;S1=1;S2=2。是只用这条式子的话会超时，所以继续想办法，然后回来以后看了其他人的博客，看到别人把Sn的式子写出来了，于是我尝试将式子迭代，然后就出现了被人博客中的式子了= =，然后根据式子Sn=2^(n-1)+(n-2)*2^(n-3) 其中n>=3;S1=1;S2=2。然后一开始用了递归的快速幂，结果爆栈了= =，然后换成递推形式的，然后一直wa，后来看到别人的代码里有一个判断k<n的情况，想到n里面有可能出现大于n的数，这时就要输出0。然后，然后就过了= =

上代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #define LL long long
 4 #define MOD 1000000007
 5 using namespace std;
 6 
 7 LL Fast_MOD(LL n)
 8 {
 9     LL r,k;
10     if(!n) return 1;
11     r=2;
12     k=1;
13     while(n>1)
14     {
15         if(n&1) k=k*r%MOD;
16         r=r*r%MOD;
17         n>>=1;
18     }
19     return r*k%MOD;
20 }
21 
22 LL operate(LL n,LL k)
23 {
24     LL ans,d;
25     d=n-k+1;
26     if(d<=0) return 0;
27     if(d==1) return 1;
28     if(d==2) return 2;
29     ans=(Fast_MOD(d-1)+(d-2)*Fast_MOD(d-3))%MOD;
30     return ans;
31 }
32 
33 int main()
34 {
35     int t;
36     LL n,k;
37     //freopen("data.txt","r",stdin);
38     scanf("%d",&t);
39     while(t--)
40     {
41         scanf("%I64d %I64d",&n,&k);
42         printf("%I64d
",operate(n,k));
43     }
44     return 0;
45 }

4602