yukicoder : No.2839 AND Constraint

頭がこんがらがる。
https://yukicoder.me/problems/no/2839

問題

整数N,Mが与えられる。
変数xの初期値を0とする。
以後、i=1～(2^N-1)に対し以下を行う。

• iの2進数表記の末尾の0の個数をkとする。
  • 2^k以下の非負整数yのうち、(x+y) and i = x+y となるyを選び、x=x+yで更新する

yとして正整数を選択する回数がちょうどM回となるのは何通りか。

解法

i=2^(N-1)の処理を終えた直後のxは0か2^(N-1)のいずれかである。

• x=0とした場合
  • i=2^(N-1)+1～2^N-1では、kは常にN未満である。よって、i=1～2^(N-1)-1の時と取れるパターンは同じ。
• x=2^(N-1)とした場合
  • i=2^(N-1)の処理では、x=2^(N-1)となるようにyを選ぶとして、その手前の(2^(N-1)-1)回とその後の(2^(N-1)-1)回は同じような遷移ができる

[x^M]f(n)をn=Nとしたときの解とすると、f(n) = f(n-1) + x*f(n-1)^2なので、DPでO(N*M^2)で解ける。

int N,M;
const ll mo=998244353;

ll dp[505][505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	
	dp[0][0]=1;
	FOR(i,501) {
		FOR(x,501) dp[i+1][x]=dp[i][x];
		FOR(x,501) FOR(y,501) if(x+y<=499) (dp[i+1][x+y+1]+=dp[i][x]*dp[i][y])%=mo;
	}
	cout<<dp[N][M]<<endl;
	
}

まとめ

式で書かれても遷移をぱっと把握できないな…。