题目描述

我们需要计算第二类Stirling数$S(n, m)$的奇偶性，即$S(n, m) \mod 2$。第二类Stirling数$S(n, m)$表示将$n$个元素的集合划分为$m$个非空子集的方式数。题目给出了$1 \leq m \leq n \leq 10^9$，直接计算显然不可行，因此需要找到$S(n, m) \mod 2$的规律或数学性质。

解题思路

1. 第二类Stirling数的递推关系：

   • $S(0, 0) = 1$
   • $S(n, 0) = 0$（$n > 0$）
   • $S(0, m) = 0$（$m > 0$）
   • $S(n, m) = m \cdot S(n-1, m) + S(n-1, m-1)$（$n, m > 0$）

2. 模2的性质：

   • 在模2下，$m \cdot S(n-1, m)$的奇偶性取决于$m$和$S(n-1, m)$的奇偶性。
   • 如果$m$是偶数，则$m \cdot S(n-1, m) \equiv 0 \mod 2$。
   • 如果$m$是奇数，则$m \cdot S(n-1, m) \equiv S(n-1, m) \mod 2$。

3. 数学性质：

   • 通过观察或数学推导，可以发现$S(n, m) \mod 2$的值与组合数的奇偶性有关。
   • 具体来说，$S(n, m) \mod 2$等于$\binom{n - m + k - 1}{k - 1} \mod 2$，其中$k = \lceil m/2 \rceil$。
   • 根据Lucas定理，组合数$\binom{a}{b} \mod 2$为1当且仅当$b$的二进制表示是$a$的二进制表示的子集。

4. 结论：

   • 设$a = n - m$，$b = \lceil m/2 \rceil$。
   • 如果$\binom{a + b - 1}{b - 1} \mod 2 = 1$，则$S(n, m) \mod 2 = 1$，否则为0。
   • 用位运算表示为：$(a + b - 1) \& (b - 1) == (b - 1)$。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <map>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1050;
const ll INF = (1LL << 62) - 1;
const ll mod = 998244353;
const double eps = 1e-8;
 
int t;
ll n, m;
 
int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld%lld", &n, &m);
        if(n == 0 && m == 0) {printf("1\n"); continue;}
        if(n == 0 || m == 0 || n < 0) {printf("0\n"); continue;}
        ll a = n - m, b = (m + 1)/2;
        if(((a+b-1) & (b-1)) == (b-1)) printf("1\n");
        else printf("0\n");
    }
    return 0;
}