【POJ1430】Binary Stirling Numbers 【斯特林数】

题目传送门
题意：判断第二类斯特林数的奇偶性。
我自己先打了个表，发现结果挺有意思的，是个分形。

然而还是不会做，去膜了膜题解，发现看不懂，只好手推出来了一个和题解一样的公式。
题解：我们都知道S[i][j]=S[i−1][j−1]+j∗S[i−1][j]$S[i][j]=S[i-1][j-1]+j\ast S[i-1][j]$
于是在mod2的意义下，当j为偶数，S[i][j]≡S[i−1][j−1]$S[i][j]\equiv S[i-1][j-1]$；当j为奇数，S[i][j]≡S[i−1][j−1]+S[i−1][j]$S[i][j]\equiv S[i-1][j-1]+S[i-1][j]$。
我们可以倒过来。当j为奇数时，S[i][j]$S[i][j]$会被加到S[i+1][j+1]$S[i+1][j+1]$；当j为偶数，S[i][j]$S[i][j]$会被加到S[i+1][j+1]$S[i+1][j+1]$和S[i+1][j]$S[i+1][j]$。
我们还可以换一个角度描述问题：有一个点初始时在(0,0)$(0,0)$。若坐标(i,j)$(i,j)$的j为奇数，可以走到(i+1,j+1)$(i+1,j+1)$，把走到(i+1,j+1)$(i+1,j+1)$记为①变换；若坐标(i,j)$(i,j)$的j为偶数，可以走到(i+1,j+1)$(i+1,j+1)$和(i+1,j)$(i+1,j)$，把走到(i+1,j)$(i+1,j)$记为②变换。问走到点(n,m)$(n,m)$的方案总数。注意第一步只能是①变换走到(1,1)$(1,1)$，因为走到任意满足x>0$x>0$的(x,0)$(x,0)$之后对答案都没有贡献，任意S[x][0]=0$S[x][0]=0$。
接下来我们发现移动的模式一定是这样的：
①，若干②，①，①，若干②，①，①，若干②，①…。
我们发现由(0,0)$(0,0)$走到(n,m)$(n,m)$一定走了n$n$步，其中一定有m$m$个①变换，除第一步外，①变换都是两两一组的。很容易得到，这些①变换的组之间共有(m+1)/2$(m+1)/2$个间隔，每个间隔都可以塞若干或零个②变换。我们令a=n−m$a=n-m$，b=(m+1)/2$b=(m+1)/2$，则答案就相当于把a$a$个相同的球分成b$b$组，每组个数可以为0的方案总数。显然答案为Cb−1a+b−1$C_{a+b-1}^{b-1}$，由插板法得到。这里要用到一个结论，Cnm$C_m^n$为奇数当且仅当m&n=n。注意判一判n，m等于0的情况。于是就搞掂了!

代码

#include<cstdio>
int t,n,m,a,b;
int calc(int n,int m){
    return (m&n)==n;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        if(!n&&!m){
            puts("1");
            continue;
        }
        if(!n||!m||n<m){
            puts("0");
            continue;
        }
        a=n-m;
        b=(m+1)/2;
        printf("%d
",calc(b-1,a+b-1));
    }
    return 0;
}