[USACO18JAN]Stamp Painting

Description:

Bessie想拿\(M\) 种颜色的长为\(K\) 的图章涂一个长为\(N\) 的迷之画布。假设他选择涂一段区间，则这段区间长度必须为\(K\) ，且涂完后该区间颜色全变成图章颜色。他可以随便涂，但是最后必须把画布画满。问能有多少种最终状态，\(N\leq 10^6,M\leq 10^6,K\leq 10^6\)

Solution:

好题

告诉我了思维僵化是多么可怕

想了各种排列组合

最后看到正解直接傻逼

正着做非常不可做

考虑补集转化,求任意一段相同颜色长度都小于k的方案,再拿总方案减去即可

那个dp还是有点东西

#include <map>

#include <set>

#include <stack>

#include <cmath>

#include <queue>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define ls p<<1

#define rs p<<1|1

using namespace std;

typedef long long ll;

const int mxn=1e6+5,mod=1e9+7;

int n,m,k,ans,f[mxn],s[mxn];

inline int read() {

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

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

	while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}

	return x*f;

}

inline void chkmax(int &x,int y) {if(x<y) x=y;}

inline void chkmin(int &x,int y) {if(x>y) x=y;}

int qpow(int a,int b) {

	int res=1,base=a;

	while(b) {

		if(b&1) res=1ll*res*base%mod;

		base=1ll*base*base%mod;

		b>>=1;

	}

	return res;

}

int main()

{

	n=read();m=read();k=read(); int ans=qpow(m,n);

	f[0]=1,s[0]=1;

	for(int i=1;i<=n;++i) {

		if(i<k) f[i]=1ll*f[i-1]*m%mod;

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

		s[i]=(s[i-1]+f[i])%mod;

	}

	printf("%d\n",(ans-f[n]+mod)%mod);

    return 0;

}

巴特西

[USACO18JAN]Stamp Painting

Description:

Solution:

最新文章

热门文章