ZOJ3216Compositions - c++编程基础

We consider problems concerning the number of ways in which a number can be written as a sum. If the order of the terms in the sum is taken into account the sum is called a composition and the number of compositions of n is denoted by c(n). Thus, the compositions of 3 are

3 = 3

3 = 1 + 2

3 = 2 + 1

3 = 1 + 1 + 1

So that c(3) = 4.

Suppose we denote by c(n, k) the number of compositions of n with all summands at least k. Thus, the compositions of 3 with all summands at least 2 are

3 = 3

The other three compositions of 3 all have summand 1, which is less than 2. So that c(3, 2) = 1.

Input

The first line of the input is an integer t (t <= 30), indicate the number of cases.

For each case, there is one line consisting of two integers n k (1 <= n <= 109, 1 <= k <= 30).

Output

Output c(n, k) modulo 109 + 7.

Sample Input

3 1

3 2

Sample Output

搞了老半天TAT

DP：

递推公式为：f(i) = f(i-1)+f(i-k)

考虑到划分方案第一个数的大小：

1.>k 那么可以由f(i-1)的方案基础上在第一个数上+1

2.=k 那么可以在f(i-k)的方案基础上在头部填一个k

那么。。。。n有1e9 啊！！！！！！！！！！！！

矩阵加速！！！！！！！！矩阵快速幂！！！！！！

以k = 3 n = 9 为例

[f(4),f(3),f(2)] = 1 0 1 [f(3),f(2),f(1)]

1 0 0

0 1 0

答案为矩阵的n-k次方的MAT[0][0]

记得k=1时用快速幂

代码：

#include   
#include   
#include   
#include   
#include   
#include   
using namespace std;  
const int MOD =  1000000007;  
const int maxn = 40;  
int n,k;  
typedef long long LL;  
struct Mat{  
    LL mat[maxn][maxn];  
    Mat(){  
        memset(mat,0,sizeof(mat));  
    }  
  
};  
Mat operator *(Mat a,Mat b){  
    Mat c;  
    for(int i = 0; i < k; i++)  
        for(int j = 0; j < k; j++)  
            for(int m = 0; m < k; m++){  
                c.mat[i][j] = (c.mat[i][j]+a.mat[i][m]*b.mat[m][j])%MOD;  
            }  
    return c;  
}  
LL pow_mod(LL a,LL p){  
    if(p==0)    return 1;  
    LL ans = pow_mod(a,p/2);  
    ans = ans*ans%MOD;  
    if(p%2==1) ans = ans*a%MOD;  
    return ans;  
}  
void solve(){  
   Mat t;  
   t.mat[0][0] = t.mat[0][k-1] = 1;  
   for(int i = 1; i < k; i++){  
     t.mat[i][i-1] = 1;  
   }  
  /* for(int i = 0; i < k; i++){ 
    for(int j = 0; j < k; j++){ 
        cout<> ncase;  
    while(ncase--){  
        scanf("%d%d",&n,&k);  
        if(k==1){  
            cout<