kmjp's blog

競技プログラミング参加記です

yukicoder : No.1531 く2

yukicoder

細々とした知識が要る問題。
https://yukicoder.me/problems/no/1531

問題

非負整数N,Kが与えられる。
無限のサイズのグリッドに対し、初期状態でほとんどの要素はA(0,i,j)=0とする。
例外的に、y and K = yとなるyに対しA(0,0,y)=1とする。
いずれかの添え字が負である要素は、値が常に0であるものとする。

A(n,i,j)=A(n-1,i,j) xor A(n-1,i-1,j) xor A(n-1,i,j-1)
とするとき、A(N,*,*)が1となる要素の数を答えよ。

解法

K=0の時を考える。
A(N,x,y)は、(0,0)から初めて、右への移動をx回、下への移動をy回、その場にとどまることを(N-x-y)回行う移動経路の組み合わせを考えるとA(N,x,y)=Comb(N,x)*Comb(N-x,y) mod 2といえる。
Comb(a,b)が奇数である条件はa and b = bなので、求めるべきは \displaystyle \sum_{N\ \mathrm{and}\ x=x}^{} \sum_{N-x\ \mathrm{and}\ y=y}^{} 1である。

これを変形すると \displaystyle \sum_{N\ \mathrm{and}\ x=x}^{} \sum_{N-x\ \mathrm{and}\ y=y}^{} 1 = \sum_{N\ \mathrm{and}\ x=x}^{} 2^{popcount(N-x)} = \sum_{N\ \mathrm{and}\ x=x}^{} 2^{popcount(x)}である。

Kが任意の場合を考える。
A(0,0,y)=1となる条件より、Comb(K,y)が奇数となるyでA(0,0,y)=1となる。
これは、移動しない・または下に移動することをK回余分に行うことと等しい。

よって \displaystyle \sum_{N\ \mathrm{and}\ x=x}^{} \sum_{N-x+K\ \mathrm{and}\ y=y}^{} 1 = = \sum_{N\ \mathrm{and}\ x=x}^{} 2^{popcount(x+K)}を求めればよい。
popcount(x+K)がある値になるxの数え上げは、Nの下のビットから順に、xに含める・含めないを考えて列挙していくとよい。

ll N,K;
ll dp[62][65][2];
const ll mo=998244353;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	dp[0][0][0]=1;
	FOR(i,61) {
		int n=(N>>i)%2;
		int k=(K>>i)%2;
		FOR(j,62) {
			FOR(x,2) {
				// not take
				(dp[i+1][j+(k^x)][k&x]+=dp[i][j][x])%=mo;
				if(n) {
					(dp[i+1][j+(k^x^1)][((k+x+1)>>1)]+=dp[i][j][x])%=mo;
				}
			}
		}
	}
	ll ret=0;
	FOR(j,62) (ret+=dp[61][j][0]%mo*((1LL<<j)%mo))%=mo;
	cout<<ret<<endl;
}

まとめ

andの条件からLucasの定理につなげていくのか。