time limit per test3 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Reziba has many magic gems. Each magic gem can be split into
M
M
normal gems. The amount of space each magic (and normal) gem takes is
1
1
unit. A normal gem cannot be split.
Reziba wants to choose a set of magic gems and split some of them,so the total space occupied by the resulting set of gems is
N
N
units. If a magic gem is chosen and split,it takes
M
M
units of space (since it is split into
M
M
gems); if a magic gem is not split,it takes
1
1
unit.
How many different configurations of the resulting set of gems can Reziba have,such that the total amount of space taken is
N
N
units? Print the answer modulo
1000000007
1000000007
(
10
9
+7
109+7
). Two configurations are considered different if the number of magic gems Reziba takes to form them differs,or the indices of gems Reziba has to split differ.
Input
The input contains a single line consisting of
2
2
integers
N
N
and
M
M
(
1≤N≤
10
18
1≤N≤1018
,
2≤M≤100
2≤M≤100
).
Output
Print one integer,the total number of configurations of the resulting set of gems,given that the total amount of space taken is
N
N
units. Print the answer modulo
1000000007
1000000007
(
10
9
+7
109+7
).
Examples
Input
copy
4 2
Output
copy
5
Input
copy
3 2
Output
copy
3
Note
In the first example each magic gem can split into
2
2
normal gems,and we kNow that the total amount of gems are
4
4
.
Let
1
1
denote a magic gem,and
0
0
denote a normal gem.
The total configurations you can have is:
1111
1111
(None of the gems split);
0011
0011
(First magic gem splits into
2
2
normal gems);
1001
1001
(Second magic gem splits into
2
2
normal gems);
1100
1100
(Third magic gem splits into
2
2
normal gems);
0000
0000
(First and second magic gems split into total
4
4
normal gems).
Hence,answer is
5
5
.

题解:有一些魔法宝石,魔法宝石可以分成m个普通宝石,每个宝石(包括魔法宝石)占用1个空间,让你求占用n个空间的方法有几种,有不同数量的魔法宝石和不同分法的方法算不同的方法,

根据样例可得递推式:f[n]=f[n-1]+f[n-m],最后一个不分加上最后一个分.

因为n比较大,可以用矩阵快速幂来求,这里当n<m,只有一种方法,n==m时有2种方法.

#include <bits/stdc++.h>
const int MOD=1e9+7;
const int M=105;
using namespace std;
typedef long long ll;
struct matrix{
    ll m[M][M];
}ans,res;
matrix mul(matrix a,matrix b,int n){
    matrix tmp;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            tmp.m[i][j]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++){
                tmp.m[i][j]+=a.m[i][k]*b.m[k][j];
                tmp.m[i][j]%=MOD;
            }
    return tmp;
}
void quickpower(ll n,int m){
    for(int i=1;i<=m;i++){
        res.m[i+1][i]=1;
        for(int j=1;j<=m;j++){
            if(i==j) ans.m[i][j]=1; else ans.m[i][j]=0;
        }
    }
    res.m[1][m]=1;res.m[m][m]=1;
    while(n){
        if(n&1){
            ans=mul(ans,res,m);
        }
        res=mul(res,m);
        n>>=1;
    }
}
int main(){
    ll n;
    int m;
    scanf("%I64d%d",&n,&m);
    if(n<m){
        printf("1\n");
        return 0;
    }
    matrix a;
    for(int i=1;i<m;i++) a.m[1][i]=1;
    a.m[1][m]=2;
    quickpower(n-m,m);
    a=mul(a,ans,m);
    printf("%I64d\n",a.m[1][m]);
    //cout << "Hello World!" << endl;
    return 0;
}