可以大胆猜想的一点是，只要有不少于一个长度为k的颜色相同子串，方案就是合法的。
直接算有点麻烦，考虑减去不合法的方案。
一个正(xue)常(sha)的思路是枚举序列被分成的段数，问题变为用一些1~k-1的数组成n的方案数，这显然是可以容斥的。但好像对每一种都进行容斥就不太好办了。
暴力二维dp是很容易想到的。考虑去掉一维的暴力，设f[i]为前i位不合法染色方案数，枚举这一段的长度转移。这显然是可以前缀和的。
#include#include #include #include #include #include using namespace std;int read(){ int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') { if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f;}#define N 1000010#define P 1000000007int n,m,k,f[N],ans;int ksm(int a,int k){ int s=1; for (;k;k>>=1,a=1ll*a*a%P) if (k&1) s=1ll*s*a%P; return s;}int main(){#ifndef ONLINE_JUDGE freopen("bzoj5190.in","r",stdin); freopen("bzoj5190.out","w",stdout); const char LL[]="%I64d\n";#else const char LL[]="%lld\n";#endif n=read(),m=read(),k=read(); ans=ksm(m,n); for (int i=1;i<=n;i++) if (i-k+1>0) f[i]=(f[i-1]+1ll*(f[i-1]-f[i-k])*(m-1))%P; else f[i]=(f[i-1]+1ll*f[i-1]*(m-1)+m)%P; cout<<((ans-f[n]+f[n-1])%P+P)%P; return 0;}