Solution -「SP 106」BINSTIRL

Description

Link.

求 (egin{Bmatrix}n \ mend{Bmatrix}mod2)

Solution

求

[egin{aligned} egin{Bmatrix}n \ mend{Bmatrix}mod2 &=left(egin{Bmatrix}n-1 \ m-1end{Bmatrix}+megin{Bmatrix}n-1 \ mend{Bmatrix} ight)mod2 \ &=egin{cases} egin{Bmatrix}n-1 \ m-1end{Bmatrix}mod2,mequiv0space(operatorname{mod}2) \ left(egin{Bmatrix}n-1 \ m-1end{Bmatrix}+egin{Bmatrix}n-1 \ mend{Bmatrix} ight)mod2,mequiv1space(operatorname{mod}2) end{cases} end{aligned} ]

(mequiv1space(operatorname{mod}2)) 的情况为组合数的递推。

转化一下，把填表转移换成刷表，即

• 当 (mequiv0space(operatorname{mod}2)) 时，(egin{Bmatrix}n \ mend{Bmatrix}) 转移到 (egin{Bmatrix}n+1 \ m+1end{Bmatrix})。

• 当 (mequiv1space(operatorname{mod}2)) 时，(egin{Bmatrix}n \ mend{Bmatrix}) 转移到 (egin{Bmatrix}n+1 \ m+1end{Bmatrix}) 和 (egin{Bmatrix}n+1 \ mend{Bmatrix})。

那么这个题目就转化成了在表格上 ((0,0)) 走到 ((n,m)) 的路径条数 (operatorname{mod}2) 问题。

两种情况都可以转移到 (egin{Bmatrix}n+1 \ m+1end{Bmatrix})，为了方便起见，我们定义这种情况为向右上转移，把 (egin{Bmatrix}n+1 \ mend{Bmatrix}) 定义为向上转移。

因为我们转移只能向上或右上走，所以只会走 (n) 步，其中 (m) 次向右上转移，(n-m) 次向右转移。

我们一共有 (lfloorfrac{m+1}{2} floor) 次机会向右转移（只能从奇数走）。

相当于我们现在需要把转移的过程分成 (n-m) 段，每一段的内部全部都是向右上转移，这样我们才能到达 ((n,m))。

用盒子与球的语言来描述，就是一共就有 (n-m+lfloorfrac{m+1}{2} floor) 个球（这里理解起来其实特别麻烦）（不过只是对于我这种组合差的人），分成 (lfloorfrac{m+1}{2} floor) 段，隔板即可。

于是 (egin{Bmatrix}n \ mend{Bmatrix}mod2={n-m+lfloorfrac{m+1}{2} floor-1chooselfloorfrac{m+1}{2} floor-1}mod2)。

关于组合数奇偶性，我这篇博客里写过，再贴上来：

结论：(dbinom{n}{m}equiv0space(operatorname{mod}2)) 当且仅当 (noperatorname{bitand}m=m)。

证明（也许不是特别严谨）：我们可以知道：

[{nchoose m}={lfloorfrac{n}{2} floorchooselfloorfrac{m}{2} floor} imes{nmod 2choose mmod2}={lfloorfrac{lfloorfrac{n}{2} floor}{2} floorchooselfloorfrac{lfloorfrac{m}{2} floor}{2} floor} imes {lfloorfrac{n}{2} floormod2chooselfloorfrac{m}{2} floormod2} imes{nmod 2choose mmod2}=cdots ]

我们发现：

[{lfloorfrac{lfloorfrac{lfloorfrac{n}{2} floor}{2} floor}{cdots} floorchooselfloorfrac{lfloorfrac{lfloorfrac{m}{2} floor}{2} floor}{cdots} floor} ]

这一坨，就是在一直进行二进制移位，(operatorname{shr}1)。

那么我们可以得出一个结论：如果对于我们记 ((n)_{k}) 表示 (n) 在二进制意义下的第 (k) 位。((n)_{k}in[0,1])

那么对于 (forall i)，有 ((n)_{i}=0) 且 ((m)_{i}=1)，那么 (dbinom{n}{m}equiv0space(operatorname{mod} 2))。

所以 (noperatorname{bitand}m=m)，证毕。

答案显然。

#include <cstdio>

int N, M;

int main () {
	int TC; scanf ( "%d", &TC ); while ( TC -- > 0 ) {
		scanf ( "%d%d", &N, &M );
		if ( ! N && ! M )	puts ( "1" );
		else if ( ! N || ! M || N < M )	puts ( "0" );
		else if ( ( ( N - M + ( ( M + 1 ) >> 1 ) - 1 ) & ( ( ( M + 1 ) >> 1 ) - 1 ) ) == ( ( ( M + 1 ) >> 1 ) - 1 ) )	puts ( "1" );
		else	puts ( "0" );
	}
	return 0;
}