传送门 其实本来想做组合数学的2333. 谁知道是道 d p dp dp. 唉只能顺手做了
还是用真难则反的思想。 这题我们倒着考虑，只需要求出不合法方案数就行了。 这个显然是随便 d p dp dp的。 f [ i ] f[i] f[i]表示到第 i i i个格子不合法的方案数。 那么有两种情况。
i < k i<k i<k，则无论怎么当前格子染都不合法， f [ i ] = f [ i − 1 ] ∗ m f[i]=f[i-1]*m f[i]=f[i−1]∗m i ≥ k i\geq k i≥k，则从当前的格子向左染最多染到第 i − k + 1 i-k+1 i−k+1个格子，因此 f [ i ] = ( m − 1 ) ∑ j = i − k + 1 i − 1 f [ i ] f[i]=(m-1)\sum _{j=i-k+1} ^{i-1}f[i] f[i]=(m−1)∑j=i−k+1i−1f[i]维护一个动态的前缀和来转移就行了。 代码：
#include<bits/stdc++.h> using namespace std; inline int read(){ int ans=0; char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar(); return ans; } typedef long long ll; const int N=1e6+5,mod=1e9+7; int n,m,k,f[N]; int main(){ n=read(),m=read(),k=read(); f[0]=1; int sum=0,ans=1; for(int i=1;i<=n;++i)ans=1ll*ans*m%mod; for(int i=1;i<=n;++i){ if(i<k)f[i]=1ll*f[i-1]*m%mod; else f[i]=1ll*sum*(m-1)%mod; sum+=f[i]; if(sum>=mod)sum-=mod; if(i>=k){ sum-=f[i-k+1]; if(sum<0)sum+=mod; } } ans-=f[n]; if(ans<0)ans+=mod; cout<<ans; return 0; }