zcmimi's blog
查看原题

点击跳转

此题要求的是S(n,m) \mod 2(第二类斯特林数)

  1. m为偶数,S(n,m) \equiv S(n-1,m-1)

  2. m为奇数,S(n,m) \equiv S(n-1,m-1)+s(n-1,m)

这样的话,相当于:

  1. (x,y)y为奇数时,可以走到(x+1,y+1)(a变换)

  2. 否则可以走到(x+1,y+1)(a变换),或(x+1,y)(b变换)

求从(0,0)走到(n,m)的方案数\pmod 2

这个过程必然走了ma变换,走了n-mb变换

b变换只能在偶数位置出现,那么变换的序列必然是如下形式:

a,b\times ?,a,a,b\times ?,a,a,...,a

也就是在\frac {m+1}2个间隔中插入n-mb,即隔板法

方案数:C(n-m+\frac{m+1}2-1,\frac{m+1}2 -1) \mod 2

还有一个结论:仅当n\&m=m时,C(n,m) \equiv 1 \bmod 2(lucas定理代入即可推出)

#include<cstdio>
bool C(int n,int m){
    return (n&m)==m;
}
int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n,m;
        scanf("%d%d",&n,&m);
        if(!n&&!m)puts("1");
        else if(!n||!m||n<0)puts("0");
        else{
            int b=n-m,a=(m+1)>>1;
            puts(C(b+a-1,a-1)?"1":"0");
        }
    }
}
POJ 1430 Binary Stirling Numbers
comment评论
Search
search