Codeforces #850 : Div1 D. Wooden Spoon

本番B,Cよりすんなり解いてた。
https://codeforces.com/contest/1785/problem/D

問題

2^N人の勝ち抜き製トーナメントを考える。
1～2^Nの番号を持つ参加者がおり、番号の小さい方が常に勝利する。

ある人vが木のスプーンを得る条件は下記である。

• 初戦でvが負ける
• 初戦でvに勝った人が、2戦目で負ける
• 前述の勝った人が3戦目で負ける
• 以下同様

トーナメントの組み方は(2^N)!通りあるが、各人が木のスプーンを得る組み合わせは何通りか。

解法

番号vの小さい順に以下を考えていく。
v番より番号の大きい人は無視して考え、v番までの人の配置を考えよう。
f(v,n) := v番から初めてn回戦までの人の配置の組み合わせ
はf(v-1,*)の状態でv番の人の配置を追加で考える求めることができる。

int N;
const ll mo=998244353;

int num[22],pat[22];
ll dp[1<<20][22];
ll fact[1<<21];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fact[0]=1;
	for(i=1;i<=1<<20;i++) fact[i]=fact[i-1]*i%mo;
	
	cin>>N;
	FOR(i,N) {
		FOR(j,i+1) num[i]+=1<<(N-1-j);
		pat[i]=1<<(N-1-i);
	}
	num[N]=1<<N;
	pat[N]=1;
	
	dp[0][0]=1<<(N-1);
	cout<<0<<endl;
	for(i=1;i<(1<<N);i++) {
		FOR(j,N) {
			//same
			if(num[j]>i) (dp[i][j]+=dp[i-1][j]*(num[j]-i))%=mo;
			// new
			(dp[i][j+1]+=dp[i-1][j]*pat[j+1])%=mo;
		}
		ll a=dp[i][N]*fact[(1<<N)-1-i]%mo;
		a=a*(1<<N)%mo;
		cout<<a<<endl;
		
	}
	
}

まとめ

なんでこれDなんだろ。