UVA1118 Binary Stirling Numbers 题解
题目链接：Binary Stirling Numbers 或者 SP106
题意：
The Stirling number of the second kind \(S(n, m)\) represents the number of ways to partition a set of \(n\) things into \(m\) nonempty subsets. For example, there are seven ways to split a four-element set into two parts: \[ \begin{gathered} \{1,2,3\} \cup\{4\},\{1,2,4\} \cup\{3\},\{1,3,4\} \cup\{2\},\{2,3,4\} \cup\{1\} \\ \{1,2\} \cup\{3,4\},\{1,3\} \cup\{2,4\},\{1,4\} \cup\{2,3\} . \end{gathered} \] We can compute \(S(n, m)\) using the recurrence, \[ S(n, m)=m S(n-1, m)+S(n-1, m-1) \] but your task is slightly different:
给定整数 \(n,m\) ，计算出 \(S(n,m)\) 的奇偶性，也就是 \(S(n,m) \bmod 2\) 。
输入：多组数据，\(n,m\) 。输出：答案。
数据范围：
\(1 \le m \le n \le 10^9\) 。
首先 \[
\begin{aligned}
& S(n, m)=S(n-1, m-1)+m \times S(n-1, m)
\\[6pt] & S(0,0)=1, ~S(n, 0)=S(0, m)=0
\end{aligned}
\] 那么 \[
S(n, m) \equiv\left\{\begin{array}{ll}
S(n-1, m-1) & m \bmod 2=0 \\[8pt]
S(n-1, m-1)+S(n-1, m) & m \bmod 2=1
\end{array}\pmod 2\right.
\] 可以作图如下（这个图怎么看上去是歪的啊）
图中红线表示 \(S(n-1,m-1)\) 到 \(S(n,m)\) 的转移，蓝线表示 \(S(n-1,m)\) 到 \(S(n,m)\) 的转移。
因为只有红线能增加 \(m\) ，所以从 \((0,0)\) 到 \((n,m)\) 的转移中，红线经过了 \(m\) 次，则蓝线经过了 \(n-m\) 次。
而对于点 \((n,m)\) ，能用的蓝线的数量 \(k=\left\lfloor\frac{m+1}{2}\right\rfloor\) ，即将 \(n-m\) 次蓝线划分为不超过 \(k\) 个连续段。 \[ S(n,m)\equiv\binom{n-m+k-1}{k-1}\pmod{2} \] 于是问题转化为组合数的奇偶性问题。
根据 Lucas 定理， \[ \binom{n}{m} \equiv\binom{\left\lfloor\frac{n}{2}\right\rfloor}{\left\lfloor\frac{m}{2}\right\rfloor} \times\binom{ n \bmod 2}{m \bmod 2} \pmod{2} \] 这实际上就是在考察 \(m\) 的每个二进制位
可以发现，当且仅当 \(n,m\) 这一位同时为 \(1\) ，答案才可能是 \(1\) 。
即，当且仅当 \((n \land m)=m\) （\(\land\) 表示二进制按位与） ，\(\binom{n}{m} \bmod 2=1\) 。
于是原题就可以做了。
单次询问时间复杂度 \(\mathcal{O}(1)\)
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())
void solve()
{
int n, m; cin >> n >> m;
if(!n && !m) { cout << "1\n"; return; }
if(!n || !m || n < m) { cout << "0\n"; return; }
int t = (m + 1) / 2 - 1; cout << ((t & n - m + t) == t) << '\n';
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
int qwq; cin >> qwq; while(qwq--) solve();
return 0;
}参考文献：
[1] https://www.luogu.com.cn/article/u3g9is8w
[2] https://www.luogu.com.cn/article/7cxxhl0r
题外话：
