嘘~ 正在从服务器偷取页面 . . .

UVA1118 Binary Stirling Numbers 题解

发布日期: 2024-05-26

更新日期: 2024-05-26

文章字数: 682

UVA1118 Binary Stirling Numbers 题解

题意：

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;
}