- 考虑 (dp) , (f[i]) 表示用 (i) 个单位空间的方案数,答案即为 (f[n]).
- 对于一个位置,我们可以放 (Magic) 的,占 (m) 空间,也可以放 (Normal) 的,占 (1) 空间.
- 转移方程即为 (f[i]=f[i-1]+f[i-m]) ,边界条件为 (f[0]=f[1]=f[2]=dots f[m-1]=1).
- 直接转移是 (O(n)) 的,无法通过,需要矩阵优化.
- 时间复杂度为 (O(m^3logn)) ,可以通过本题.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
inline ll read()
{
ll x=0;
bool pos=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())
if(ch=='-')
pos=0;
for(;isdigit(ch);ch=getchar())
x=x*10+ch-'0';
return pos?x:-x;
}
const int MAXM=110;
const int P=1e9+7;
inline int add(int a,int b)
{
return (a + b) % P;
}
inline int mul(int a,int b)
{
return 1LL * a * b % P;
}
ll n;
int m;
struct Matrix{
int a[MAXM][MAXM];
Matrix()
{
for(int i=1;i<=m;++i)
for(int j=1;j<=m;++j)
a[i][j]=0;
}
Matrix operator * (const Matrix &rhs) const
{
Matrix res;
for(int k=1;k<=m;++k)
for(int i=1;i<=m;++i) if(a[i][k])
for(int j=1;j<=m;++j) if(rhs.a[k][j])
res.a[i][j]=add(res.a[i][j],mul(a[i][k],rhs.a[k][j]));
return res;
}
};
Matrix fpow(Matrix x,ll b)
{
Matrix res;
for(int i=1;i<=m;++i)
res.a[i][i]=1;
while(b)
{
if(b&1)
res=res*x;
x=x*x;
b>>=1;
}
return res;
}
int main()
{
n=read(),m=read();
if(n<m)
return puts("1")&0;
Matrix st;//st_{m-1}
for(int i=1;i<=m;++i)
st.a[i][1]=1;
Matrix trans;
trans.a[1][1]=trans.a[1][m]=1;
for(int i=2;i<=m;++i)
trans.a[i][i-1]=1;
st=fpow(trans,1LL*(n-m+1))*st;
cout<<st.a[1][1];
return 0;
}