Rezibahasmanymagicgems.EachmagicgemcanbesplitintoMnormalgems.Theamountofspaceeachmagic(andnormal)gemtakesis1unit.Anormalgemcannotbesplit.
Rezibawantstochooseasetofmagicgemsandsplitsomeofthem,sothetotalspaceoccupiedbytheresultingsetofgemsisNunits.Ifamagicgemischosenandsplit,ittakesMunitsofspace(sinceitissplitintoMgems);ifamagicgemisnotsplit,ittakes1unit.
HowmanydifferentconfigurationsoftheresultingsetofgemscanRezibahave,suchthatthetotalamountofspacetakenisNunits?Printtheanswermodulo1000000007(109+7).TwoconfigurationsareconsidereddifferentifthenumberofmagicgemsRezibatakestoformthemdiffers,ortheindicesofgemsRezibahastosplitdiffer.
InputTheinputcontainsasinglelineconsistingof2integersNandM(1≤N≤1018,2≤M≤100).
OutputPrintoneinteger,thetotalnumberofconfigurationsoftheresultingsetofgems,giventhatthetotalamountofspacetakenisNunits.Printtheanswermodulo1000000007(109+7).
ExamplesInput
42
Output
5
Input
32
Output
3
现在有一款魔力宝石，一块能顶m块，现在选一些魔力宝石，你可以选择分裂一些，或者全分裂，再或者不分裂，但是要求这些宝石的总体积为n。求一共有多少种组合方法。一开始的时候，没有特别明显的方法，于是就先以分裂为2块为例，列出了前5项，没想到写出来竟然是斐波那契数列，所以这个题是不是有递推关系呢？对于总体积为n，分裂数为m的情况，显然，当n<m时，有且只有一种；只有当n>=m时，才会有分裂的选择。所以，可以选择在体积为n-1时，添加一块不分裂，也可以在体积为n-m时，添加一块分裂。综上所述，kind[n]=kind[n-1]+kind[n-m]但是由于数据量的关系，不能用普通dp或者迭代，因为内存不支持，所以在这里要使用矩阵的形式改写上述关系式，并用矩阵快速幂来求出结果。首先是设计矩阵，不妨首先考虑体积为m时这样就构造出系数矩阵，并且要注意，对于体积为n时，只需要计算系数矩阵的n-m+1次方，并不是n-m次方。在得到系数矩阵以及其幂次之后，就是要进行幂的运算，矩阵乘法不进行详细描述，请自行百度。快速幂则是将幂次分解。以二进制为例，1e19的二进制中，最高位也不过70次方，也就是说，70次幂以内，就i可以得到其1e19次幂，这样极大的优化了时间复杂度。所以现在只需要根据二进制数，在合适的位置上加即可。注意应用到矩阵快速幂中，不定义矩阵的零次幂，或者说以原矩阵初始化，这时计算的幂次要-1。
#include<stdio.h>#include<climits>#include<cstring>#include<time.h>#include<math.h>#include<iostream>#include<algorithm>#include<stack>#include<queue>#include<set>#include<map>#include<utility>#include<vector>#include<string>#defineINF0x3f3f3f3f#definelllonglong#definePairpair<int,int>#definerereturn#defineMake(a,b)make_pair(a,b)#definePush(num)push_back(num)#definerep(index,star,finish)for(registerintindex=star;index<finish;index++)#definedrep(index,finish,star)for(registerintindex=finish;index>=star;index--)usingnamespacestd;constintmod=1e9+7;intm;lln;voidQpow(llp,intc[][105]);voidmul(intlf[][105],intrg[][105]);intmain(){ios::sync_with_stdio(false);cin>>n>>m;if(n<m){cout<<1<<endl;}else{intc[105][105];memset(c,0,sizeof(c));rep(i,0,m-1)c[i][i+1]=1;c[m-1][0]=c[m-1][m-1]=1;intans=0;Qpow(n-m+1,c);rep(i,0,m){ans=(ans+c[m-1][i])%mod;}cout<<ans<<endl;}re0;}voidQpow(llp,intc[][105]){intrec[105][105];rep(i,0,m)rep(j,0,m)rec[i][j]=c[i][j];p--;while(p!=0){if(p%2){mul(c,rec);p--;}mul(rec,rec);p/=2;}}voidmul(intlf[][105],intrg[][105]){lltem[m][m];memset(tem,0,sizeof(tem));rep(i,0,m){rep(j,0,m){rep(k,0,m)tem[i][j]=(tem[i][j]+(1LL*lf[i][k]*rg[k][j])%mod)%mod;}}rep(i,0,m)rep(j,0,m)lf[i][j]=tem[i][j];}
