Codeforces ECR #062 : E. Palindrome-less Arrays

FもGも勉強になりました。
https://codeforces.com/contest/1140/problem/E

問題

N要素の整数列Aが与えられる。
各要素は1～Kのいずれかを取る。
また、一部の要素は未確定である。

未確定の要素に1～Kを入れたとき、３要素以上の奇数長の部分列が回文とならないようなものは何通りか。

解法

３要素以上とあるが、結局３要素の回文ができないようにすればよい。
そのためには、元の数列を奇数番目と偶数番目で分けたとき、隣同士が同じ値を取らないようにすればよい。
奇数番目と偶数番目で分けて数列に対し、確定済みの要素の間にいくつか未確定要素がある場合、それらの埋め方が何通りかはDPで埋めていこう。

int N,K;
vector<int> A[2];
ll mo=998244353;
ll dp[202020][3];

ll hoge1(int len) {
	int i;
	FOR(i,len+2) dp[i][0]=dp[i][1]=0;
	dp[0][0]=1;
	FOR(i,len) {
		dp[i+1][0]=dp[i][1]*(K-1)%mo;
		dp[i+1][1]=(dp[i][0]+dp[i][1]*(K-2))%mo;
	}
	return dp[len][1]*(K-1)%mo;
}

ll hoge2(int len) {
	int i;
	FOR(i,len+2) dp[i][0]=dp[i][1]=dp[i][2]=0;
	dp[0][0]=1;
	FOR(i,len) {
		dp[i+1][0]=(dp[i][1]+dp[i][2]*(K-2))%mo;
		dp[i+1][1]=(dp[i][0]+dp[i][2]*(K-2))%mo;
		dp[i+1][2]=(dp[i][0]+dp[i][1]+dp[i][2]*(K-3))%mo;
	}
	return (dp[len][0]+dp[len][2]*(K-2))%mo;
	
	
}

ll hoge(vector<int> V) {
	int i,L=V.size()+1,R=-1;
	
	FOR(i,V.size()) if(V[i]!=-1) {
		L=min(L,i);
		R=max(R,i);
	}
	
	ll ret;
	if(R==-1) {
		ret=K;
		FOR(i,V.size()-1) ret=ret*(K-1)%mo;
	} 
	else {
		ret=1;
		FOR(i,L) ret=ret*(K-1)%mo;
		for(i=V.size()-1;i>R;i--) ret=ret*(K-1)%mo;
		for(int cur=L+1;cur<=R;cur++) {
			if(V[cur]!=-1) {
				if(V[L]==V[cur]) ret=ret*hoge1(cur-L-1)%mo;
				else ret=ret*hoge2(cur-L-1)%mo;
				L=cur;
			}
		}
	}
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>x;
		A[i%2].push_back(x);
	}
	
	cout<<(hoge(A[0])*hoge(A[1]))%mo<<endl;
	
}

まとめ

これ方針は立ったとしても、両端の処理とか地味にめんどいんだよね。