Codeforces ECR #104 : G. String Counting

どうにか本番中に解けた。
https://codeforces.com/contest/1487/problem/G

問題

整数Nが与えられるので、N文字のアルファベット小文字からなる文字列を作ることを考える。
以下を満たす文字列は何通りか。

• 3文字以上奇数長の回文を含まない。
• a～zそれぞれ、使用可能な文字数が決められている。なお、いずれもN/3以上である。

解法

N/3以上使える文字は、高々2個である。
よって、個数の上限を無視して数えたものから、個数上限を1つまたは2つ生じるケースを引こう。

個数上限を無視すると、回文の条件は結局3文字の回文を作らなければいいので、末尾2文字を覚えてDPすればよい。
また、個数上限については、個数の上位2個だけ覚えてDPをしていけばよい。

int N;
int C[505];
ll from[404][404][3][4];
ll to[404][404][3][4];
ll dp[404][404];
const ll mo=998244353;
int NG[404][404];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,26) cin>>C[i];
	
	FOR(x,26) FOR(y,26) {
		from[(x==0)+(y==0)][(x==1)+(y==1)][x<2?x:2][y<2?y:((x==y)?2:3)]++;
	}
	
	FOR(i,N-2) {
		ZERO(to);
		FOR(x,N) FOR(y,N) FOR(j,3) FOR(k,4) if(from[x][y][j][k]) {
			ll v=from[x][y][j][k];
			if(j!=0) (to[x+1][y][min(k,2)][0]+=v)%=mo;
			if(j!=1) (to[x][y+1][min(k,2)][1]+=v)%=mo;
			if(j==0||j==1) {
				if(k>=2) {
					(to[x][y][min(k,2)][2]+=v)%=mo;
					(to[x][y][min(k,2)][3]+=v*23)%=mo;
				}
				else {
					(to[x][y][k][2]+=v*24)%=mo;
				}
			}
			else {
				if(k==0||k==1) (to[x][y][k][2]+=v*23)%=mo;
				else if(k==2) {
					(to[x][y][k][3]+=v*23)%=mo;
				}
				else {
					(to[x][y][2][2]+=v)%=mo;
					(to[x][y][2][3]+=v*22)%=mo;
				}
			}
		}
		swap(from,to);
	}
	ll ret=0;
	FOR(x,N+1) FOR(y,N+1) {
		FOR(i,3) FOR(j,4) dp[x][y]+=from[x][y][i][j];
		dp[x][y]%=mo;
		ret+=dp[x][y];
	}
	ret%=mo;
	// 1つNG
	FOR(i,26) {
		for(x=C[i]+1;x<=N;x++) FOR(y,N+1)  ret-=dp[x][y];
		ret%=mo;
	}
	// 2つNG
	FOR(y,26) FOR(x,y) NG[C[x]+1][C[y]+1]++;
	for(x=1;x<=N;x++) for(y=1;y<=N;y++) {
		NG[x][y]+=NG[x-1][y]+NG[x][y-1]-NG[x-1][y-1];
		(ret+=dp[x][y]*NG[x][y])%=mo;
	}
	cout<<ret<<endl;
	
	
	
}

まとめ

ECRのボス問にしては易しめ。