Educational Codeforces Round 104 (Rated for Div. 2) G.String Counting(dp+容斥)

题目

有c1个a，c2个b，...，c26个z。

你需要用这些字母构造出一个长度为n的字符串，使得不存在长度>=3的奇回文子串。

输出答案对998244353取模的值。

保证对于输入的所有ci来说，ci>n/3都成立。

思路来源

uoj群

题解

奇回文子串的限制，等价于s[i]!=s[i-2]。

如果没有ci的限制，就变成了一个计数问题，前两个字母26种选法，后面的只要保证和s[i-2]不同，25种选法。

于是，ci>n/3成为了突破口，鸽巢原理表明，最多只有两种字母会超出使用上限。

不妨就dp这两种字母，注意到字母之间其实是没有区别的。

于是，dp[i][j][k][l][m]表示“最多有两个数超过限制的情况下，

前i个数中，分别用了j个第一种数，k个第二种数，且当前倒数第二个位置的状态是l，倒数第一个是m

这里l m为枚举值0 1 2，其中0表示既不是第一种也不是第二种”的方案数

sum[i][j]表示第一种数用了>=i个，第二种数用了>=j个的方案数，做一遍二维后缀和。

此时再简单容斥一下，把每一种独立超限的减掉，于是两种同时超限的被多减了，加回来即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
//dp[i][j][k][l][m]:表示最多有两个数超过限制的情况下
//前i个数中 分别用了j个第一种数k个第二种数 且倒数第二个是l 倒数第一个是m
//这里l m为枚举值0 1 2,其中0表示既不是第一种也不是第二种  
const int N=405,mod=998244353;
int n,c[26],sum[N][N],dp[2][N][N][3][3],now,las;
void add(int &x,int y){x=(x+y)%mod;}
void sub(int &x,int y){x=(x+mod-y)%mod;}
int main(){
	scanf("%d",&n);
	for(int i=0;i<26;++i){
		scanf("%d",&c[i]);
	}
	dp[0][0][0][0][0]=1;
	now=0;las=1;
	for(int i=0;i<n;++i){
		swap(now,las);
		for(int j=0;j<=i;++j){
			for(int k=0;k<=i;++k){
				for(int x=0;x<3;++x){
					for(int y=0;y<3;++y){
						dp[now][j][k][x][y]=0;
					}
				}
			}
		}
		for(int j=0;j<=i;++j){
			for(int k=0;k<=i;++k){
				for(int x=0;x<3;++x){
					for(int y=0;y<3;++y){
						if(!dp[las][j][k][x][y])continue;
						add(dp[now][j][k][y][0],1ll*dp[las][j][k][x][y]*(x==0 && i>=2?23:24)%mod);
						if(x!=1)add(dp[now][j+1][k][y][1],dp[las][j][k][x][y]);
						if(x!=2)add(dp[now][j][k+1][y][2],dp[las][j][k][x][y]);
					}
				}
			}
		}	
	}
	for(int j=0;j<=n;++j){
		for(int k=0;k<=n;++k){
			for(int x=0;x<3;++x){
				for(int y=0;y<3;++y){
					add(sum[j][k],dp[now][j][k][x][y]);
				}
			}
		}
	}
	//二维前缀和 
	for(int i=n;i>=0;--i){
		for(int j=n;j>=0;--j){
			add(sum[i][j],sum[i+1][j]);
		}
	}
	for(int i=n;i>=0;--i){
		for(int j=n;j>=0;--j){
			add(sum[i][j],sum[i][j+1]);
		}
	} 
	int ans=1; 
	//没有限制的情况下 
	for(int i=0;i<n;++i){
		ans=1ll*ans*(i<2?26:25)%mod;
	} 
	//减去一种超过的 加上多减的两种超过的 容斥 
	for(int i=0;i<26;++i){
		sub(ans,sum[c[i]+1][0]);
	}
	for(int i=0;i<26;++i){
		for(int j=i+1;j<26;++j){
			add(ans,sum[c[i]+1][c[j]+1]);
		}
	}
	printf("%d\n",ans);
	return 0;
}