zcmimi's blog
查看原题

点击跳转

第二类斯特林数

n个不同的球放进m个相同的盒子,保证盒子非空,求方案数。

容斥法:

S(n,m)=\frac 1{m!}\sum_{i=0}^m {m\choose i}(m-i)^n(-1)^i

枚举空盒个数,剩下随便放,到这里开始也有了二项式反演的形式

由于盒子相同,所以除以m!

递推法:

S(n,m)=S(n-1,m-1)+mS(n-1,m)

相当于考虑现在要放的求是否单独在一个盒子里:

  1. 不占一盒:

    其余n-1个球放到m-1个盒子里

  2. 放到某个有球的盒子里:

    m个盒子可放(m种可能),其余n-1个球放到m个盒子里

此题要求的是S(n,m) \mod 2

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

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

这样的话,相当于:

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

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

求从(0,0)走到(n,m)的方案数\mod 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

#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