在梦中ztxz16ztxz16ztxz16结婚生子了，他不得不照顾小宝宝。但这实在太无聊了，于是ztxz16ztxz16ztxz16会在散步。梦中ztxz16ztxz16ztxz16住在一个类似数轴的街上，数轴上的每个整点是一个街区，每个单位时间内ztxz16ztxz16ztxz16可以选择向左走一个街区或者向右走一个街区，但如果他离开家超过MMM个单位时间小宝宝会有危险，因此ztxz16ztxz16ztxz16必须在距离上次在家中不超过MMM个单位时间内回到家中。
NNN个单位时间后ztxz16ztxz16ztxz16会醒来，他希望此时正好在家中。
ztxz16ztxz16ztxz16想知道散步过程可能有多少种不同的散步过程。两个散步过程被认为不同，当且仅当存在至少一个单位时刻ztxz16ztxz16ztxz16选择的走向不同。
题目解析
DPDPDP，设f[i]f[i]f[i]为当在第iii时刻回到家的方案数，a[i]a[i]a[i]为在第iii时刻回到家的方案数且期间没回过家。所以f[i]=∑i=1mf[i−j]×a[j]f[i]=\sum_{i=1}^mf[i-j]\timesa[j]f[i]=∑i=1mf[i−j]×a[j]。
我们可以用矩阵乘法优化时间。
代码#include<bits/stdc++.h>#defineN105#defineM1000000007#definelllonglongusingnamespacestd;lln,m;lla[N][N],tmp[N][N],ans[N][N],k[N][N];voidmul(lla[N][N],llb[N][N]){memset(tmp,0,sizeof(tmp));for(inti=1;i<=m+1;i++)for(intj=1;j<=m+1;j++)for(intk=1;k<=m+1;k++)tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%M;memcpy(a,tmp,sizeof(tmp));}voidqpow(intt){while(t){if(t&1)mul(ans,a);mul(a,a);t>>=1;}}intmain(){cin>>n>>m;a[1][1]=1;for(inti=1;i<m;i++)for(intj=1;j<=m/2;j++){(a[i+1][j+1]+=a[i][j])%=M;(a[i+1][j-1]+=a[i][j])%=M;}for(inti=1;i<=m/2-1;i++)k[i+1][i]=1;for(inti=1;i<=m/2;i++)ans[i][i]=1,k[1][i]=2*a[i*2][0]%M;n/=2;while(n){if(n&1)mul(ans,k);mul(k,k);n>>=1;}cout<<ans[1][1];}
