WA

#include<bits/stdc++.h>
using namespace std;
//int dp[][];表示前i个坑，其中最后有连续j个坑
//不放：dp[i][0]=dp[i-1][0]+dp[i-1][1]+……+dp[i-1][m-1]（合法的所有可能相加）
//放；dp[i][j]=dp[i-1][j-1]
const int mod=1e9+7;
long long mat[105][105],t1[105][105];
long long ans[105],t2[105];
int main(){
	long long n,m;
	cin>>n>>m;
	ans[0]=1;
	for(int i=0;i<m-1;i++){
		mat[0][i]=1;
		mat[i+1][i]=1;
	}
	mat[0][m-1]=1;
	n++;
	while(n){
		if(n&1){
			memset(t2,0,sizeof t2);
			for(int i=0;i<m;i++){
				for(int j=0;j<m;j++){
					t2[i]+=mat[i][j]*ans[j]%mod;
				}
			}
			for(int i=0;i<m;i++) ans[i]=t2[i]%mod;
		}
		n>>=1;
		memset(t1,0,sizeof t1);
		for(int i=0;i<m;i++){
			for(int j=0;j<m;j++){
				for(int k=0;k<m;k++){
					t1[i][k]+=mat[i][j]*mat[j][k]%mod;
				}
			}
		}
		for(int i=0;i<m;i++){
			for(int j=0;j<m;j++){
				mat[i][j]=t1[i][j]%mod;
			}
		}
	}
	cout<<ans[0]<<"\n";;
	return 0;
}

© 2019 - 2025王码编程  滇ICP备19007937号-1如果您有任何