C++14(g++5.4) 解法, 执行用时: 153ms, 内存消耗: 736K, 提交时间: 2019-04-15 00:32:40

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int mod = 1e9+7;
LL n,k,a[110][110],b[110][1],dp[110];
void init(){
    a[0][0] = a[0][k-1] = 1,dp[0] = 1;
    for(int i = 1;i <= k; ++i) dp[i] = (dp[i-1] + (i-k >= 0 ? dp[i-k] : 0))%mod;
    for(int i = 1;i < k; ++i) a[i][i-1] = 1;
    for(int i = 0; i < k ; ++i) b[i][0] = dp[k-i];
}
void calmatrix1(){
    LL c[110][1] = {0};
    for(int i = 0;i < k; ++i)
        for(int j = 0;j < k; ++j)
            c[i][0] = (c[i][0] + a[i][j]*b[j][0]) % mod;
    memcpy(b,c,sizeof(c));
}
void calmatrix2(){
    LL c[110][110] = {0};
    for(int i = 0;i < k; ++i)
        for(int j = 0;j < k; ++j)
            for(int t = 0;t < k; ++t)
                c[i][t] = (c[i][t] + a[i][j]*a[j][t]) % mod;
    memcpy(a,c,sizeof(c));
}
LL solve(LL x)
{
    init();
    while(x){
        if(x & 1) calmatrix1();
        calmatrix2();
        x >>= 1;
    }
    return b[k-1][0];
}
int main()
{
    cin >> n >> k;
    if(n <= k) cout << 0 << '\n';
    else cout << (solve(n-1) - 2 + ((n%k)?1:0) + mod) % mod << '\n';
    return 0; 
}

C++11(clang++ 3.9) 解法, 执行用时: 2549ms, 内存消耗: 744K, 提交时间: 2019-04-13 17:38:07

#include<cstdio>
long long mo=1000000007;
long long n,x1,Pow,q[105][105],a[105][105],res[105][105],E[105][105],ans;
int main()
{
	scanf("%lld%lld",&n,&x1);
	a[1][1]=a[1][x1]=1;
	for(int i=1;i<x1;i++)
		a[i+1][i]=1;
	for(int i=1;i<=x1;i++)
		for(int j=1;j<=x1;j++)
		{
			q[i][j]=a[i][j];
			res[i][i]=1;
		}
	Pow=n-x1+1;
	while(Pow)
	{
		if(Pow&1)
		{
			for(int i=1;i<=x1;i++)
				for(int j=1;j<=x1;j++)
					for(int k=1;k<=x1;k++)
						E[i][j]=(E[i][j]+(q[i][k]*res[k][j])%mo)%mo;
			for(int i=1;i<=x1;i++)
				for(int j=1;j<=x1;j++)
				{
					res[i][j]=E[i][j];
					E[i][j]=0;
				}
		}
		for(int i=1;i<=x1;i++)
			for(int j=1;j<=x1;j++)
				for(int k=1;k<=x1;k++)
					E[i][j]=((q[i][k]*q[k][j])%mo+E[i][j])%mo;
		for(int i=1;i<=x1;i++)
			for(int j=1;j<=x1;j++)
			{
				q[i][j]=E[i][j];
				E[i][j]=0;
			}
		Pow/=2;
	}
	for(int i=1;i<=x1;i++)
		ans=(ans+res[i][1])%mo;
	ans=ans-1-(n%x1==0);
	if(ans<0) ans+=mo;
	printf("%lld",ans);
}