comet oj 2714（概率dp+矩阵快速幂）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll inv;
ll qpow(ll n,ll m){
	ll ans=1;
	while(m){
		if(m&1)ans=n*ans%mod;
		n=n*n%mod;
		m/=2;
	}
	return ans;
}
struct st{
	ll ary[25][25];
	void init1(){
		memset(ary,0,sizeof(ary));
	}
	void init2(){
		for(int i=0;i<25;i++){
			ary[i][i]=1ll;
		}
	}
}tem1,tem2;
ll k,d;
st mul(st st1,st st2){
	st ans;
	ans.init1();
	for(int i=0;i<=k;i++){
		for(int j=0;j<=k;j++){
			for(int m=0;m<=k;m++){
				ans.ary[i][j]=(ans.ary[i][j]+st1.ary[i][m]*st2.ary[m][j]%mod)%mod;
			}
		}
	}
	return ans;
}
st st_qpow(st st1,ll m){
	st ans;
	ans.init1();
	ans.init2();
	while(m){
		if(m&1)ans=mul(ans,st1);
		st1=mul(st1,st1);
		m/=2;
	}
	return ans;
}
int main(){
	scanf("%lld%lld",&d,&k);
	inv=qpow(k,mod-2);
	tem1.init1();
	for(int i=0;i<k;i++){
		tem1.ary[i][0]=inv;
	}
	tem1.ary[k][0]=1ll;
	int cnt=0;
	int cnt1=1;
	for(int i=1;i<k;i++){
		tem1.ary[cnt][cnt1]=1ll;
		cnt++,cnt1++;
	}
	tem1.ary[k][k]=1ll;
	/*for(int i=0;i<=k;i++){
		for(int j=0;j<=k;j++){
			cout<<tem1.ary[i][j]<<" ";
		}
		cout<<endl;
	}*/
	tem2.init1();
	for(int i=0;i<k;i++){
		tem2.ary[0][i]=k;
	}
	tem2.ary[0][k]=1ll;
	printf("%lld\n",mul(tem2,st_qpow(tem1,d-k)).ary[0][0]);
	return 0;
}