BZOJ5190 Usaco2018 Jan Stamp Painting（动态规划）

　　可以大胆猜想的一点是，只要有不少于一个长度为k的颜色相同子串，方案就是合法的。

　　直接算有点麻烦，考虑减去不合法的方案。

　　一个正(xue)常(sha)的思路是枚举序列被分成的段数，问题变为用一些1~k-1的数组成n的方案数，这显然是可以容斥的。但好像对每一种都进行容斥就不太好办了。

　　暴力二维dp是很容易想到的。考虑去掉一维的暴力，设f[i]为前i位不合法染色方案数，枚举这一段的长度转移。这显然是可以前缀和的。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 1000010

#define P 1000000007

int n,m,k,f[N],ans;

int ksm(int a,int k)

{

    int s=;

    for (;k;k>>=,a=1ll*a*a%P) if (k&) 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=;i<=n;i++)

    if (i-k+>) f[i]=(f[i-]+1ll*(f[i-]-f[i-k])*(m-))%P;

    else f[i]=(f[i-]+1ll*f[i-]*(m-)+m)%P;

    cout<<((ans-f[n]+f[n-])%P+P)%P;

    return ;

}

巴特西

BZOJ5190 Usaco2018 Jan Stamp Painting（动态规划）

最新文章

热门文章