题解 UVA1118 【Binary Stirling Numbers】

· · 题解

\text{Link}

双倍经验：\text{Link}

题意

求 \displaystyle{n\brace m}\bmod 2。多组数据。

1\le n,m\le 10^9,1\le T\le 200

思路

首先特判几个特殊情况

{n\brace 0}={0\brace n}=[n=0] {n\brace m}=0(n<m)

再来看递推式。

{n\brace m}=m{n-1\brace m}+{n-1\brace m-1}

此时可以对 m 的奇偶性分类讨论。

{n\brace m}\equiv {n-1\brace m-1}(\bmod 2) {n\brace m}\equiv {n-1\brace m-1}+{n-1\brace m}(\bmod 2)

考虑建立平面直角坐标系，其中点 (n,m) 的值即为 \displaystyle{n\brace m}\bmod 2。

考虑 \displaystyle{n\brace m} 可从 \displaystyle{n-1\brace m-1} 和 \displaystyle{n-1\brace m} （当 2|m）转移至，考虑 m 只能由第一种转移增加，于是从 (0,0) 至 (n,m) 的转移中第一种转移的次数为 m 次，那么第二种便转移了 n-m 次。

相当于有 n-m 个连续的第一种转移段，而可进行的第一次转移只有 d=\lceil\frac {m} {2}\rceil 次，故

{n\brace m}\equiv \binom{n-m+d-1}{d-1}(\bmod 2)

即问题转化为组合数奇偶性问题。

根据 \text{Lucas} 定理，

\binom n m\equiv \binom{\lfloor\frac n 2\rfloor}{\lfloor\frac m 2\rfloor}\times \binom{n\bmod 2}{m\bmod 2}(\bmod 2)

递归时我们发现每次都会将 n,m 去掉最后一位，若 n 二进制的第 i 位为 0 且 m 为 1 时，\displaystyle\binom n m\equiv0(\bmod 2)，即

\binom n m\equiv1(\bmod 2)

当且仅当 n\text{ and }m=m。

故原问题迎刃而解。

时间复杂度 O(T)。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO{//by cyffff

}
int main(){
    int t=read();
    while(t--){
        int n=read(),m=read();
        if(!n&&!m) write(1);
        else if(!n||!m) write(0);
        else if(n<m) write(0);
        else{
            int d=m+1>>1;
            write((n-m+d-1&d-1)==d-1);
        }
        putc('\n');
    }
    flush();
    return 0;
}

再见 qwq~