第二类斯特林数-BINSTIRL - Binary Stirling Numbers

· · 题解

前言：双倍经验。

题目大意

求第二类斯特林数 \begin{Bmatrix}n \\ m\end{Bmatrix}\bmod2 的值，也就是判断它的奇偶性。

思路

啊数学题，真快乐。

首先把递推式列出来，\begin{Bmatrix}n \\ m\end{Bmatrix}=\begin{Bmatrix}n-1 \\ m-1\end{Bmatrix}+m\cdot \begin{Bmatrix}n-1 \\ m\end{Bmatrix}。然后分类讨论一下 m 的奇偶性。

\begin{cases} \begin{Bmatrix}n-1 \\ m-1\end{Bmatrix}\pmod 2 ,2\mid m \\ \left(\begin{Bmatrix}n-1 \\ m-1\end{Bmatrix}+\begin{Bmatrix}n-1 \\ m\end{Bmatrix}\right)\pmod 2 ,2\nmid m \\ \end{cases}

然后转换一下，可以变为：

当 2\mid j 时，\begin{Bmatrix}i \\ j\end{Bmatrix} 会转移到 \begin{Bmatrix}i+1 \\ j+1\end{Bmatrix} 和 \begin{Bmatrix}i+1 \\ j\end{Bmatrix}。

当 2\nmid j 时，\begin{Bmatrix}i \\ j\end{Bmatrix} 会转移到 \begin{Bmatrix}i+1 \\ j+1\end{Bmatrix}。

就很类似在一个平面直角坐标系里跑，从 (0,0) 到 (n,m) 的方法再模 2 的问题。那 \begin{Bmatrix}i+1 \\ j\end{Bmatrix} 就可以看作往右走，\begin{Bmatrix}i+1 \\ j+1\end{Bmatrix} 为往右上走。又因为只有往右和右上两周方向，所以只能走 n 步，其中有 m 步右上，n-m 步右。

然后因为只能在奇数的情况下向右转移，也就是只有 \lfloor{\dfrac{m+1}{2}}\rfloor 次。那把这个带回去，就是有 n-m 个球，放到 \lfloor{\dfrac{m+1}{2}}\rfloor 个盒子里的问题，即 \dbinom{n-m+\lfloor{\dfrac{m+1}{2}}\rfloor-1}{\lfloor{\dfrac{m+1}{2}}\rfloor-1}。

也就把斯特林数的奇偶性转化为了组合数的奇偶性问题。

然后考虑组合数的奇偶性问题，虽然可能不是这道题的重点，但还是用我这种愚蠢的思维证一下。因为 Lucas 定理告诉了我们在 p 进制下的两数

x=(\overline {x_0x_1\cdots x_k})_p y=(\overline {y_0y_1\cdots y_k})_p

则有

\dbinom{x}{y}\equiv\prod_{i=0}^k\dbinom{x_i}{y_i} \pmod p

而对于本题，p=2，带进去就可以发现如果 \dbinom{x}{y} 要为奇数，则其中的 \dbinom{x_i}{y_i} 必须不出现 0。而我们又知道，\dbinom{0}{1}=0，所以对于任意的 x_i 和 y_i，不会出现 x_i=0 且 y_i=1 的情况。如果出现的话，当 x 与 y 做按位与运算的时候，答案就不可能为 y，即 x\&y\ne y。相反，如果未出现上述情况的话，即当 \dbinom{x}{y} 为奇数时，会有 x\&y=y。

那就得到了组合数的奇偶性的公式：

对于 \dbinom{a}{b}，当且仅当 a\&b=b，2\nmid \dbinom{a}{b}。

那把这个带回去，就可以直接写代码了。

然后注意特判。

code

/*
ID: enderch1    
PROG:
LANG: C++
*/
#include<iostream>
#include<cstdio>
#define change_max(a,b) a=max(a,b)
#define change_min(a,b) a=min(a,b)
#define int long long
using namespace std;

int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
void solve()
{
    int T=read();
    while(T--)
    {
        int n=read(),m=read();
        int temp=(m+1)/2;
        if((!n)&&(!m)) puts("1");
        else if((!n)||(!m)||n<m) puts("0");
        else if(((n-m+temp-1)&(temp-1))==(temp-1)) puts("1");
        else puts("0");
    }
}
signed main()
{
    solve();
    return 0;
}

放在最后：猪马好闪，拜谢猪马。

@cqbzlzm

The End