yukicoder : No.1741 Arrays and XOR Procedure

どこかで見たことある気がする。
https://yukicoder.me/problems/no/1741

問題

01で構成された数列Aを考える。
Aに対し、|A|=1となるまで以下の処理を繰り返す。

• 処理後の新しいAをA'と表現すると、|A'|=|A|-1で、かつA'[i] = A[i] xor A[i-1]

Aの初期値が与えられる。
一部の要素は未確定であり、0/1どちらでも埋められる。

上記処理を繰り返したとき、A=[1]となるような値の埋め方は何通りか。

解法

Aの各要素が、どの程度最終的にAの値に反映されるかを考える。
i番目の要素は、Binom(|A|-1,i)が奇数ならA[i]が最終的な値にxorされ、偶数なら全く寄与しない。

Binom(|A|-1,i)の偶奇はLucasの定理で求められる。あとは
dp(n,b) := Aのn要素目までを考えたとき、それらにより最終的な値がbとなる組み合わせ
としてdp(|A|,1)を求めよう。

int N;
int dp[202020][2];
const ll mo=998244353;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	dp[0][0]=1;
	FOR(i,N) {
		cin>>x;
		int flip=(((N-1)&i)==i);
		if(x==0||x==-1) {
			dp[i+1][0]+=dp[i][0];
			dp[i+1][1]+=dp[i][1];
		}
		if(x==1||x==-1) {
			(dp[i+1][0^flip]+=dp[i][0])%=mo;
			(dp[i+1][1^flip]+=dp[i][1])%=mo;
		}
	}
	cout<<dp[N][1]<<endl;
}

まとめ

Lucasの定理、存在は覚えてるけど、いつも偶奇の条件を忘れる。