题解：P14654 夤生月
__FL__
·
·
题解
题意
排列连边必然形成若干个简单环；排列的权值定义说明（求 G 时）我们只需要关心每个环内有哪些数。故题目实际上为：
- 把 1...n 放进 m 个置换环里，问方案数；
- 把 1...n 放进 m 个集合里，问方案数。
换句话说，分别求第一类斯特林数和第二类斯特林数在模 2 意义下的值，要求 O(1)。
题解
关于斯特林数的推导这里不再赘述。考虑第一类斯特林数的递推式：
\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}
由于模数为 2，有简单转化：
\begin{bmatrix}n-1\\ k-1\end{bmatrix}+\begin{bmatrix}n-1\\ k\end{bmatrix}, & 2\mid n, \\
\begin{bmatrix}n-1\\ k-1\end{bmatrix}, & 2\nmid n.
\end{cases}
不妨令 n 为偶数，则有：
\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-2\\ k-2\end{bmatrix}+\begin{bmatrix}n-2\\ k-1\end{bmatrix}
其中，\begin{bmatrix}0\\ 0\end{bmatrix} = 1。
考虑一张这样的图：
$${n\choose m}\equiv [n\&m=m]\pmod 2$$
容易做到 $O(1)$。
第二类斯特林数与之类似，其推导出的式子为：
$$
\begin{Bmatrix}n\\ k\end{Bmatrix}=\begin{Bmatrix}n-2\\ k-2\end{Bmatrix}+\begin{Bmatrix}n-1\\ k\end{Bmatrix}
$$
注意此时我们令 $k$ 为奇数。
## Code
```cpp
#include<bits/stdc++.h>
using namespace std;
int q;
inline int C(int a,int b)
{
return (a&b) == b;
}
signed main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> q;
while (q--)
{
int op,n,m;
cin >> op >> n >> m;
if (n < m) cout << 0;
else if (op == 1)
{
if (n&1) n--,m--;
int l = n/2;
cout << C(l,m-l);
}
else
{
if (!(m&1)) n--,m--;
int l = (m-1)/2;
cout << C(n-1-l,l);
}
}
return 0;
}
```