题目大意 :
有魔法石,一个魔法石可以分解为m个普通石,一个魔法师(普通石)占的空间为1,如果一个魔法石一个魔法石往容器里面装,装的时候可以选择分解魔法石为普通石或不分解,询问有多少种方法恰好占满空间为n的容器?分解顺序不同视为方法不同。
#include<bits/stdc++.h>
using namespace std;
//函数参数输入,返回值输出
//特别注意lenth一定要改,不然每次都遍历到最大的矩阵会tle
typedef long long ll;
ll lenth=200;
ll mod=1e9+7;
struct Sarray{
ll data[200][200];
//看着改
Sarray operator *(const Sarray&a){
Sarray tem;
for(ll i=0;i<lenth;i++){
for(ll j=0;j<lenth;j++){
for(ll k=0;k<lenth;k++){
tem.data[i][j]=(tem.data[i][j]+data[i][k]*a.data[k][j])%mod;
}
}
}
return tem;
}
Sarray operator +(const Sarray&a){
Sarray tem;
for(ll i=0;i<lenth;i++){
for(ll j=0;j<lenth;j++){
tem.data[i][j]=(data[i][j]+a.data[i][j])%mod;
}
}
return tem;
}
Sarray(const Sarray&a){
for(ll i=0;i<lenth;i++){
for(ll j=0;j<lenth;j++){
data[i][j]=a.data[i][j];
}
}
}
Sarray(){
memset(data,0,sizeof(data));
}
};
Sarray E;
void ini(){
for(ll i=0;i<lenth;i++)
for(ll j=0;j<lenth;j++)
if(i==j)E.data[i][j]=1;
else E.data[i][j]=0;
}
Sarray qpow(Sarray a,ll b){
Sarray tem=E;
while(b){
if(b&1)tem=a*tem;
a=a*a;
b>>=1;
}
return tem;
}
//sigma(p^i) from 0 to n [0,n]
Sarray sigma(Sarray&p,ll n){
if(n==0)return E;
if(n==1)return E+p;
if(n&1) return (E+qpow(p,n/2+1))*sigma(p,n>>1);
else return (E+qpow(p,n/2+1))*sigma(p,n/2-1)+qpow(p,n>>1);
}
///////////////////////////////////////
int main(){
ini();
ll n,m;
cin>>n>>m;
lenth=m;
Sarray p,r;
p.data[0][0]=1;
p.data[0][m-1]=1;
for(ll i=1;i<m;i++){
p.data[i][i-1]=1;
}
r.data[0][0]=2;
for(ll i=1;i<m;i++){
r.data[i][0]=1;
}
if(n>=m){
Sarray l=qpow(p,n-m)*r;
cout<<l.data[0][0]<<endl;
}
else{
cout<<1<<endl;
}
}