yukicoder : No.3215 Make K types-able

問題文はややこしいが、中身は簡単。
https://yukicoder.me/problems/no/3215

問題

整数Nに対し、01で構成される長さ2^N-1の数列Xを考える。
長さNの数列Aを考える。初期状態でA[1]=1で、それ以外A[i]=-1である。

• A[x]!=-1、X[A[x]]=1、X[A[2x]]=1の時、A[x+1]=2*A[x]とする
• A[x]!=-1、X[A[x]]=1、X[A[2x+1]]=1の時、A[x+1]=2*A[x]+1とする

上記処理を任意回数行える時、A[N]がK通りあり得るようなXは何通りか。

解法

問題を言い換えると以下のようになる。
深さNの完全二分木の各点を、白黒に彩色する。根から葉まで黒点になっているようなパスが(K-1)個あるような彩色は何通りか。
(A[N]=-1のケースがあるので、それ以外(K-1)通りを考える)

f(N,K) := 問題の解
とすると、f(N+1,K)は以下のようになる。

• 根を白くする場合、残り2^(N+1)-2点は白でも黒でもいいのでf(N+1,0) = 2^(2^(N+1)-2)
• 根を黒くする場合、f(N+1,K) += f(N,a) * f(N,K-a)

ll dp[202020][11];
ll nv[202020];
const ll mo=998244353;
int T,N,K;

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;
	
	dp[1][1]=1;
	dp[1][0]=1;
	nv[1]=1;
	for(i=2;i<=200000;i++) {
		nv[i]=(nv[i-1]*2+1)%(mo-1);
		// トップを選択不可
		dp[i][0]=modpow(2,nv[i-1]*2%(mo-1));
		// トップを選択可
		for(x=0;x<=10;x++) for(y=0;x+y<=10;y++) (dp[i][x+y]+=dp[i-1][x]*dp[i-1][y])%=mo;
	}
	
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		cout<<dp[N][K-1]<<endl;
	}
}

まとめ

★3～3.5でもいい気はする。