Codeforces ECR #156 : D. Monocarp and the Set

4問目からAC率だいぶ下がった回。
https://codeforces.com/contest/1886/problem/D

問題

1～NのPermutation Pを考える。
文字列Sは不等号または?で構成される(N-1)文字の文字列で、S[i]は以下を意味する。

• S[i]=?の場合、P[i+1]はPの先頭(i+2)要素のうち最大値でも最小値でもない。
• S[i]=＞の場合、P[i+1]はPの先頭(i+2)要素のうち最大値である。
• S[i]=＜の場合、P[i+1]はPの先頭(i+2)要素のうち最小値である。

Sを1文字変えるクエリが与えられる。
その都度、Sの意味に合致するPが何通りか求めよ。

解法

挿入DPで計算していくことを考えると、S[i]='?'なら、P[i+1]の取りえる値はi通りである。
あとは、S[i]が'?'かそうでないかに応じてiの乗算をしていけばよい。

int N,M;
string S;
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	cin>>S;
	ll ret=1;
	for(i=1;i<N-1;i++) if(S[i]=='?') ret=ret*i%mo;
	if(S[0]=='?') cout<<0<<endl;
	else cout<<ret<<endl;
	
	while(M--) {
		cin>>i>>s;
		i--;
		if(i==0) S[0]=s[0];
		else {
			if(S[i]=='?') ret=ret*modpow(i)%mo;
			S[i]=s[0];
			if(S[i]=='?') ret=ret*i%mo;
		}
		if(S[0]=='?') {
			cout<<0<<endl;
		}
		else {
			cout<<ret<<endl;
		}
	}
	
	
	
}

まとめ

意外にシンプルな解答。