A85781 游园会 题解

代码见下

#include<bits/stdc++.h>
using namespace std;
#define MAXN (1<<15)+5
#define MAXM 1005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL; 
typedef long double ld;
typedef pair<int,int> pii;
const int INF=0x3f3f3f3f;
const int mo=1e9+7;
const int mod=1e7+7;
const int inv2=5e8+4;
const int jzm=2333;
const int zero=20000;
const int n1=1000;
const int M=100000;
const int orG=3,ivG=332748118;
const long double Pi=acos(-1.0);
const double eps=1e-12;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
	_T f=1;x=0;char s=getchar();
	while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
	while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1)t=1ll*t*a%p;a=1ll*a*a%p;s>>=1;}return t;}
int n,K,dp[2][MAXN][3],nxt[MAXN][3],a[MAXN],g[20],h[20],bit[MAXN],ans[20];
char str[MAXM];
signed main(){
	read(n);read(K);scanf("\n%s",str+1);const int lim=(1<<K);
	for(int i=1;i<=K;i++)a[i]=(str[i]=='N')?0:((str[i]=='O')?1:2);
	for(int i=0;i<lim;i++){
		for(int j=1;j<=K;j++)g[j]=(i>>j-1)&1,g[j]+=g[j-1];
		for(int k=0;k<3;k++){
			for(int j=1;j<=K;j++)
				h[j]=max(h[j-1],max(g[j],g[j-1]+(a[j]==k)));
			for(int j=K;j>0;j--)h[j]-=h[j-1],nxt[i][k]|=(h[j]<<j-1);
		}
	}
	int now=0,las=1;dp[0][0][0]=1;
	for(int i=1;i<=n;i++){
		swap(now,las);
		for(int j=0;j<lim;j++)
			for(int k=0;k<3;k++)if(dp[las][j][k])
				for(int l=0;l<3;l++){
					if(k==l&&k==2)continue;
					Add(dp[now][nxt[j][l]][k==l?k+1:(l==0)],dp[las][j][k],mo);
				}
		for(int j=0;j<lim;j++)
			for(int k=0;k<3;k++)dp[las][j][k]=0;
	}
	for(int i=1;i<lim;i++)bit[i]=bit[i>>1]+(i&1);
	for(int i=0;i<lim;i++)for(int j=0;j<3;j++)
		Add(ans[bit[i]],dp[now][i][j],mo);
	for(int i=0;i<=K;i++)printf("%d\n",ans[i]);
	return 0;
}