yukicoder : No.2899 Taffy Permutation

2898より簡単だったな…。
https://yukicoder.me/problems/no/2899

問題

N文字のバイナリ文字列Sが与えられる。
1～NのPermutation Pを作るとき、以下を満たすものは何通りか。

• i＜jかつS[i]＜S[j]の場合、P[i]＜P[j]

解法

先頭の要素から挿入ソートをすることを考える。
dp(n,k) := 先頭n要素のpermutationを考えたとき、S[i]=0となる要素のP[i]の最大値がkとなるような組み合わせ数

とする。dp(n,k)からdp(n+1,*)への遷移を考える。

• S[n]=0の場合
  • P[n]はどの値をとっても良い。仮にmを取るなら、dp(n,k)からdp(n+1,max(m,k))に遷移する
• S[n]=1の場合
  • P[n]はkより大きければどこに入っても良い。dp(n,k)*(n-k+1)だけdp(n+1,k)に遷移する

int N;
string S;

ll from[2020];
ll to[2020];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S;
	from[0]=1;
	FOR(i,N) {
		FOR(j,N) to[j]=from[j];
		if(S[i]=='0') {
			ZERO(from);
			//最上位を更新しないケース
			FOR(j,i+1) {
				from[j+1]=to[j]*j%mo;
			}
			//最上位を更新するケース
			FOR(j,N) {
				(to[j+1]+=to[j])%=mo;
			}
			for(j=1;j<=i+1;j++) (from[j]+=to[j-1])%=mo;
		}
		else {
			FOR(j,i+1) (from[j]*=(i-j+1))%=mo;
		}
		
	}
	ll ret=0;
	FOR(i,N+1) ret+=from[i];
	cout<<ret%mo<<endl;
		
	
	
}

まとめ

すんなり解けて良かったね。