二项式反演
Shadovv
·
·
算法·理论
闲话
今天是高一回归 OI 的第一天，lf 说讲一些简单的东西。
听得糊里糊涂的，目前就只知道二项式反演是个啥，连套用都不会/kk
好了现在会生搬硬套了。
看到有人在看我的博客学二项式反演欸好感动，补充了一点东西。
前置芝士
首先你需要知道一个组合数式子：
\binom{n}{r}\binom{r}{m} = \binom{n}{m}\binom{n - m}{r - m}
证明的话从组合意义上理解就好：n 个球选 r 个，再从 r 个中选 m 个，等价于先从 n 个球中选 m 个，再在剩下的 n - m 个球中选 r - m 个。
数学归纳法也行，但是麻烦了。
或者直接暴力拆开：
\begin{aligned}
\binom{n}{r}\binom{r}{m} &= \dfrac{n!}{r!(n - r)!}\times\dfrac{r!}{m!(r - m)!}\\
&= \dfrac{n!}{m!(n - r)!(r - m)!}\\
&= \dfrac{n!}{m!(n - m)!}\times \dfrac{(n - m)!}{(n - r)!(r - m)!}\\
&= \binom{n}{m}\binom{n - m}{r - m}
\end{aligned}
然后你还需要知道如何交换求和次序。
假设你需要计算 \sum\limits_{i = 0}^{n}\sum\limits_{j = 0}^{i}f(i, j) 这个式子，但是并不想要在外层枚举 i，于是可以做如下变换：
\begin{aligned}
&\sum\limits_{i = 0}^{n}\sum\limits_{j = 0}^{i}f(i, j)\\
=&\sum\limits_{i = 0}^{n}\left[f(i, 0) + f(i, 1) + f(i, 2) + \cdots + f(i, i)\right]\\
=&\left[f(0, 0)\right] + \left[f(1, 0) + f(1, 1)\right] + \left[f(2, 0) + f(2, 1) + f(2, 2)\right] + \cdots + \left[f(n, 0) + f(n, 1) + f(n, 2) + \cdots + f(n, n)\right]\\
=&\left[f(0, 0) + f(1, 0) + f(2, 0) + \cdots + f(n, 0)\right] + \left[f(1, 1) + f(2, 1) + \cdots + f(n, 1)\right] + \cdots + \left[f(n, n)\right]\\
=&\sum\limits_{j = 0}^{n}\left[f(j, j) + f(j + 1, j) + \cdots + f(n, j)\right]\\
=&\sum\limits_{j = 0}^{n}\sum\limits_{i = j}^{n}f(i, j)
\end{aligned}
感性理解一下：枚举 i \in [0, n] 的时候 j \in [0, i]，现在枚举 j \in [0, n] 的话，i 一定大于等于 j，所以 i \in [j, n]。
好了还有一个就是二项式定理了。
(x + y)^{n} = \sum\limits_{i = 0}^{n}\binom{n}{i}x^{i}y^{n - i}
这个组合意义理解一下或者数学归纳法证明一下就好了。
具体地，把它写成 \underbrace{(x + y)(x + y)(x + y)\cdots(x + y)}_{n\text{个}(x + y)}，如果要用乘法分配律把它展开的话，对于每一项，我们可以选择把 x 提出来或者 把 y 提出来，所以 x^{i}y^{n - i} 的系数就应该是 \binom{n}{i}，表示从这 n 项里面选了 i 项把 x 提出来。
对于 (1 - 1)^{n} 这个式子我们从直觉上来说会认为它是 0，但是在 n 等于 0 的情况下我们会认为它是 1，因为此时 \sum\limits_{i = 0}^{0}\binom{0}{0}1^{0}(-1)^{0} = 1。
二项式反演
二项式反演其实就是在对一个函数反演的时候，利用二项式定理化简掉了某一项。
比如计数函数 f(k) 表示钦定/至多 k 个元素构成某个特定结构的方案数。
注意：我们口头上一般会将上面描述为至多（或至少），但是这样是不严谨的（甚至是错误的），因为以至多来定义的话那么 g(k) 可以直接通过 f(k) - f(k - 1) 来求了。更加严谨并且正确的描述是钦定，因为钦定给了我们可以容斥的空间，从而才能有二项式反演。
_感觉很像容斥，或许反演本质上就是一种容斥？_
那么很明显有：
$$
f(k) = \sum\limits_{i = 0}^{k}\binom{k}{i}g(i)
$$
~~如果理解不了上面的组合数系数的组合意义的话那估计没救了。~~
说明一下：这个组合数系数的意义是“从**钦定**的 $k$ 个元素中选出那**恰好**能构成特定结构的 $i$ 个”。
如果想求出 $g(n)$ 的值，又不方便计算，但是发现求 $f(i)$ 会比 $g(n)$ 方便许多的时候，就可以将上面的式子反演一下：
$$
f(k) = \sum\limits_{i = 0}^{k}\binom{k}{i}g(i) \Leftrightarrow g(k) = \sum\limits_{i = 0}^{k}(-1)^{k - i}\binom{k}{i}f(i)
$$
我不知道这个东西是怎么推出来的，但是看着应该是容斥出来的。问 cgy 他说是找规律找出来的，他在一次模拟赛赛时推式子的时候发现了这个规律，后来知道这个叫二项式反演。
补充：我越看这个式子越像容斥，然后翻了一下之前写的广义容斥笔记，发现他们俩好像就是一个玩意？所以说这个东西就当结论记就好了，还要明白它是容斥推出来的。
[放一下我之前写的广义容斥笔记](https://www.luogu.com.cn/blog/VividCycle/Inclusion-and-Exclusion)
如果你特别想了解怎么推出来可以点进去上面的链接看一下，你会发现这个柿子和广义容斥是一样的。
反演一个式子的方法我还不知道，但是这个东西挺好证明的，方法是直接硬刚代入：
$$
\begin{aligned}
f(k) &= \sum\limits_{i = 0}^{k}\binom{k}{i}g(i)\\
&= \sum\limits_{i = 0}^{k}\binom{k}{i}\left[\sum\limits_{j = 0}^{i}(-1)^{i - j}\binom{i}{j}f(j)\right]\\
&= \sum\limits_{i = 0}^{k}\sum\limits_{j = 0}^{i}(-1)^{i - j}\binom{k}{i}\binom{i}{j}f(j)\\
&= \sum\limits_{i = 0}^{k}\sum\limits_{j = 0}^{i}(-1)^{i - j}\binom{k}{j}\binom{k - j}{i - j}f(j)\\
&= \sum\limits_{j = 0}^{k}\sum\limits_{i = j}^{k}(-1)^{i - j}\binom{k}{j}\binom{k - j}{i - j}f(j)\\
&= \sum\limits_{j = 0}^{k}\binom{k}{j}f(j)\left[\sum\limits_{i = j}^{k}(-1)^{i - j}\binom{k - j}{i - j}\right]\\
&= \sum\limits_{j = 0}^{k}\binom{k}{j}f(j)\left[\sum\limits_{i = 0}^{k - j}(-1)^{i}\binom{k - j}{i}\right]\\
&= \sum\limits_{j = 0}^{k}\binom{k}{j}f(j)[k = j]\\
&= f(k)\\
\end{aligned}
$$
解释一下：第二步是把外面的组合数系数丢到里面的求和式里面去；
第三步用到了前置芝士里面的组合数柿子；
第四步用到了交换求和顺序；
第五步把和 $i$ 无关的项提到了外面；
第六步改变了 $i$ 的枚举范围；
第七步用到了二项式定理以及在前置芝士中提到的特殊情况。
二项式反演还有另外一种形式：上面的计数函数 $f(k)$ 表示的是 **钦定/至多** $k$ 个元素，下面的 $f(k)$ 表示的是 **钦定/至少** $k$ 个元素，$g(k)$ 不变，反演如下：
$$
f(k) = \sum\limits_{i = k}^{n}\binom{i}{k}g(i) \Leftrightarrow g(k) = \sum\limits_{i = k}^{n}(-1)^{i - k}\binom{i}{k}f(i)
$$
证明类似。这一种反演好像更常用一点？
_至此应该算是学会了二项式反演，但是我还不会套用式子，所以例题做出来了的话我会写在下面的。_
---
## 例题
### [已经没有什么好害怕的了](https://www.luogu.com.cn/problem/P4859)
直接套用上面的第二种二项式反演的式子。
首先将 $k$ 设为 $\dfrac{n + k}{2}$，从「恰好多 $k$ 对」变成「恰好 $k$ 对」，这一步要判无解。
令 $f(k)$ 表示**钦定/至少**有 $k$ 对「糖果大于药片」的配对的方案数，令 $g(k)$ 表示**恰好**有 $k$ 对的方案数。
套用二项式反演：
$$
f(k) = \sum\limits_{i = k}^{n}\binom{i}{k}g(i) \Leftrightarrow g(k) = \sum\limits_{i = k}^{n}(-1)^{i - k}\binom{i}{k}f(i)
$$
这里的 $f(i)$ 可以 dp 求出。具体地，先将药片和糖果按权值从小到大排序，统计出每种糖果能和多少种药片组成「糖果大于药片」的配对，记为 $cnt$。
令 $dp_{i, j}$ 表示前 $i$ 种糖果（排序后），已经有 $j$ 组「糖果大于药片」的配对的方案数，**这里的方案数只考虑已配对的糖果和药片**，不考虑未被配对的。因为如果考虑了就有后效性了。
有 dp 转移方程：
$$
\begin{cases}
dp_{i, 0} = 1\\
dp_{i, j} = dp_{i - 1, j} + dp_{i - 1, j - 1} \times \left[cnt_{i} - (j + 1)\right]
\end{cases}
$$
最后 $f(k) = (n - k)! \times dp_{n, k}$，因为剩下的可以随便配对。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000009;
ll n, k, ans, f[2005], fct[2005], inv[2005], a[2005], b[2005], cnt[2005], dp[2005][2005];
ll ksm(ll x, ll y) {
ll ret = 1;
while(y) {
if(y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
ll c(ll n, ll m) {
return fct[n] * inv[m] % mod * inv[n - m] % mod;
}
int gsm(int x) {return ((~x & 1) << 1) - 1;}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
fct[0] = 1;
for(int i = 1; i <= 2000; ++i) fct[i] = fct[i - 1] * i % mod;
inv[2000] = ksm(fct[2000], mod - 2);
for(int i = 2000; i >= 1; --i) inv[i - 1] = inv[i] * i % mod;
cin >> n >> k;
if((n + k) & 1) {
cout << "0";
return 0;
}
k = (n + k) >> 1;
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int i = 1; i <= n; ++i) cin >> b[i];
stable_sort(a + 1, a + 1 + n);
stable_sort(b + 1, b + 1 + n);
for(int i = 1; i <= n; ++i) {
cnt[i] = cnt[i - 1];
while(cnt[i] < n && b[cnt[i] + 1] < a[i]) ++cnt[i];
}
dp[0][0] = 1;
for(int i = 1; i <= n; ++i) {
dp[i][0] = 1;
for(int j = 1; j <= cnt[i]; ++j) {
dp[i][j] = (dp[i - 1][j] + dp[i - 1][j - 1] * (cnt[i] - j + 1) % mod) % mod;
}
}
for(int i = 0; i <= n; ++i) f[i] = dp[n][i] * fct[n - i] % mod;
for(int i = k; i <= n; ++i) {
ans += gsm(i - k) * c(i, k) * f[i] % mod;
}
cout << (ans % mod + mod) % mod;
return 0;
}
```
### [集合计数](https://becoder.com.cn/contest/4475/problem/2)
上面是学校 OJ 的链接，不是 luogu。
_题目好绕啊。_
套路：令 $f(k)$ 表示**钦定/至少**有 $k$ 个元素出现在交集中，令 $g(k)$ 表示**恰好**有 $k$ 个元素出现在交集中。
反演：
$$
f(k) = \sum\limits_{i = k}^{n}\binom{i}{k}g(i) \Leftrightarrow g(k) = \sum\limits_{i = k}^{n}(-1)^{i - k}\binom{i}{k}f(i)
$$
这里 $f(i) = \binom{n}{i}(2^{2^{n - i}} - 1)$，组合意义上理解是：先从 $n$ 个元素中选出交集的元素，那么剩下的 $n - i$ 个元素就会构成 $2^{n - i}$ 中集合（每种元素选或不选），这 $2^{n - i}$ 种集合每种可以选或不选，所以有 $2^{2^{n - i}}$ 种情况，但是不能不选，所以要减去 $1$。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
ll n, k, ans, fct[1000005], inv[1000005];
ll ksm(ll x, ll y, const int mod) {
ll ret = 1;
while(y) {
if(y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
ll c(ll n, ll m) {
return fct[n] * inv[m] % mod * inv[n - m] % mod;
}
int gsm(int x) {return ((~x & 1) << 1) - 1;}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
fct[0] = 1;
for(int i = 1; i <= 1000000; ++i) fct[i] = fct[i - 1] * i % mod;
inv[1000000] = ksm(fct[1000000], mod - 2, mod);
for(int i = 1000000; i >= 1; --i) inv[i - 1] = inv[i] * i % mod;
cin >> n >> k;
for(int i = k; i <= n; ++i) {
// cerr << i << ": " << gsm(i - k) << " " << c(i, k) << " " << (ksm(2, ksm(2, n - i, mod - 1), mod) - 1) * c(n, i) << '\n';
ans += gsm(i - k) * c(i, k) * (ksm(2, ksm(2, n - i, mod - 1), mod) - 1) % mod * c(n, i) % mod;
}
cout << (ans % mod + mod) % mod;
return 0;
}
```
### [分特产](https://www.luogu.com.cn/problem/P5505)
继续套路：
套路：令 $f(k)$ 表示**钦定/至少**有 $k$ 个同学没拿到特产，令 $g(k)$ 表示**恰好**有 $k$ 个没拿到特产。
反演：
$$
f(k) = \sum\limits_{i = k}^{n}\binom{i}{k}g(i) \Leftrightarrow g(k) = \sum\limits_{i = k}^{n}(-1)^{i - k}\binom{i}{k}f(i)
$$
$f(i) = \binom{n}{i}\prod\limits_{j = 1}^{m}\binom{a_{j} + n - i - 1}{n - i - 1}$，还是组合意义理解：先选出没有拿到特产的同学，接下来把每种特产分配给**可能拿到特产的同学**，里面的组合数是插板法。因为特产之间两两互不影响，应用乘法原理。
_插板法计算组合数不开二倍数组是什么几百年前就在犯的错误。_
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
ll n, m, ans, f, a[1005], fct[2005], inv[2005];
ll ksm(ll x, ll y, const int mod) {
ll ret = 1;
while(y) {
if(y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
ll c(ll n, ll m) {
return fct[n] * inv[m] % mod * inv[n - m] % mod;
}
int gsm(int x) {return ((~x & 1) << 1) - 1;}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
fct[0] = 1;
for(int i = 1; i <= 2000; ++i) fct[i] = fct[i - 1] * i % mod;
inv[2000] = ksm(fct[2000], mod - 2, mod);
for(int i = 2000; i >= 1; --i) inv[i - 1] = inv[i] * i % mod;
cin >> n >> m;
for(int i = 1; i <= m; ++i) cin >> a[i];
for(int i = 0; i < n; ++i) {
f = c(n, i);
for(int j = 1; j <= m; ++j) {
f = f * c(a[j] + n - i - 1, n - i - 1) % mod;
}
ans += gsm(i) * f % mod;
}
cout << (ans % mod + mod) % mod;
return 0;
}
```
### [Placing Rooks](https://www.luogu.com.cn/problem/CF1342E)
_看了半天题始终看不明白为什么 `3 3` 的样例输出 `0`，后来才发现车不能穿过别的车/lh_
做完之后发现这个东西原来是斯特林数？
先特判 $k = 0$ 或 $k \geqslant n$ 的情况，分别输出 $n!$ 和 $0$，一个是全排列一个是无解。
每一行或者每一列肯定都有一个车，并且**如果有车能互相攻击到，那么要么都是攻击到同一列的车，要么都是攻击到同一行的车**，这一点可以随便举几个例子感受一下。
具体证明的话：假设存在三个车，它们的坐标分别为 $(x_0, y_0)$，$(x_1, y_1)$，$(x_1, y_0)$，现在有两行/两列被覆盖到了，所以可以直接不考虑这两行/两列，把剩下的格子看成大小 $(n - 2) \times (n - 2)$ 的棋盘，我们要用 $n - 3$ 个车覆盖 $(n - 2) \times (n - 2)$ 的棋盘，这是不可能的。
有更多的车的情况也肯定不可能了。
所以**要么每一行有且仅有一个车，某些车处于同一列从而产生互相攻击的关系；要么每一列有且仅有一个车，某些车处于同一行从而产生互相攻击的关系**。
下面讨论**每一行有且仅有一个车**的情况，因为棋盘是正方形的所以旋转一下就可以得到列的情况，最终答案乘 $2$ 即可。
令 $f(k)$ 表示**钦定/至少**有 $k$ 对可以互相攻击的车，令 $g(k)$ 表示**恰好**有 $k$ 对可以互相攻击的车。答案即为 $g(k)$。
由二项式反演可以得到：
$$
f(k) = \sum\limits_{i = k}^{n}\binom{i}{k}g(i) \Leftrightarrow g(k) = \sum\limits_{i = k}^{n}(-1)^{i - k}\binom{i}{k}f(i)
$$
考虑如何计算 $f(i)$。
因为我们讨论的是每一行都有车的情况，所以车能互相攻击到一定是因为在同一列里。如果同一列有 $cnt$ 个车，那么会贡献 $cnt - 1$ 对能够互相攻击的车，**车的攻击判定是不能穿过别的车的**。
所以如果有 $i$ 对能够互相攻击到的车，那么肯定只有 $n - i$ 列上会有车。可以先选出是哪些列可以放车，再给每一行上的车分配它所在的列。所以 $f(i) = \binom{n}{n - i}(n - i)^{n}$。
直接计算 $g(k)$ 即可，时间复杂度 $\mathcal{O}(n \log n)$。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
ll n, k, ans, f, fct[200005], inv[200005];
ll ksm(ll x, ll y) {
ll ret = 1;
while(y) {
if(y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
ll c(ll n, ll m) {
return fct[n] * inv[m] % mod * inv[n - m] % mod;
}
int gsm(int x) {return ((~x & 1) << 1) - 1;}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
fct[0] = 1;
for(int i = 1; i <= 200000; ++i) fct[i] = fct[i - 1] * i % mod;
inv[200000] = ksm(fct[200000], mod - 2);
for(int i = 200000; i >= 1; --i) inv[i - 1] = inv[i] * i % mod;
cin >> n >> k;
if(k >= n) {
cout << "0";
return 0;
}
if(!k) {
cout << fct[n];
return 0;
}
for(int i = k; i <= n; ++i) {
ans += gsm(i - k) * c(i, k) * c(n, n - i) % mod * ksm(n - i, n) % mod;
}
cout << (ans * 2 % mod + mod) % mod;
return 0;
}
```
### [Another Filling the Grid](https://www.luogu.com.cn/problem/CF1228E)
_这道题我是用容斥做的，因为我不会有两个求和式的二项式反演/kel_
直接求**恰好**每一行每一列都没有 $1$ 的方案数不好求，考虑容斥。
令 $f(i, j)$ 表示**钦定/至少** $i$ 行和 $j$ 列没有 $1$ 的方案数，那么 $f(i, j) = k^{(n - i)(n - j)} (k - 1)^{n(i + j) - i \times j}$，意义显然。
然后这道题因为是求**恰好没有不满足要求**的方案数，不用广义容斥，直接凑 $(-1)^{k}$ 这个系数就好了，它显然是和 $i$ 和 $j$ 有关的，~~枚举一下四种情况就好了~~，让行和行之间容斥，列和列之间容斥，容斥系数就应该是 $(-1)^{i} \times (-1)^{j} = (-1)^{i + j}$。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
ll n, k, ans, f, fct[255], inv[255];
ll ksm(ll x, ll y) {
ll ret = 1;
while(y) {
if(y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
ll c(ll n, ll m) {
return fct[n] * inv[m] % mod * inv[n - m] % mod;
}
int gsm(int x) {return ((~x & 1) << 1) - 1;}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
fct[0] = 1;
for(int i = 1; i <= 250; ++i) fct[i] = fct[i - 1] * i % mod;
inv[250] = ksm(fct[250], mod - 2);
for(int i = 250; i >= 1; --i) inv[i - 1] = inv[i] * i % mod;
cin >> n >> k;
for(int i = 0; i <= n; ++i) {
for(int j = 0; j <= n; ++j) {
ans += gsm(i + j) * c(n, i) * c(n, j) % mod * ksm(k, (n - i) * (n - j)) % mod * ksm(k - 1, n * (i + j) - i * j) % mod;
}
}
cout << (ans % mod + mod) % mod;
return 0;
}
```
### [[MtOI2018] 情侣？给我烧了！](https://www.luogu.com.cn/problem/P4921)
一样的思路，令 $f(k)$ 表示**钦定/至少**有 $k$ 对和睦的情侣，令 $g(k)$ 表示**恰好**有 $k$ 对和睦的情侣。
反演：
$$
f(k) = \sum\limits_{i = k}^{n}\binom{i}{k}g(i) \Leftrightarrow g(k) = \sum\limits_{i = k}^{n}(-1)^{i - k}\binom{i}{k}f(i)
$$
而 $f(i) = \binom{n}{i}\binom{n}{i}i!2^{i}(2n - 2i)!$，其意义为：先钦定 $i$ 对情侣是和睦的，方案数 $\binom{n}{i}$ 给他们选出座位，方案数 $\binom{n}{i}$，而人与人之间是相异的（可以理解为带标号的小球），要全排列一下，方案数 $i!$。这钦定的 $i$ 对情侣中每一对有两种入座方式（或者说是这两个人全排列一下也行），总方案数 $2^{i}$。剩下的没有被钦定的人直接全排列就行，方案数 $(2n - 2i)!$。
我们发现难点仍然在于快速计算 $g(k)$，想办法把求和式化掉。开始推柿子：
$$
\begin{aligned}
g(k) &= \sum\limits_{i = k}^{n}(-1)^{i - k}\binom{i}{k}f(i)\\
&= \sum\limits_{i = k}^{n}(-1)^{i - k}\binom{i}{k}\binom{n}{i}\binom{n}{i}i!2^{i}(2n - 2i)!\\
&= \sum\limits_{i = k}^{n}(-1)^{i - k}\dfrac{i!}{k!(i - k)!}\dfrac{(n!)^{2}}{(i!)^{2}[(n - i)!]^2}i!2^{i}(2n - 2i)!\\
&= \sum\limits_{i = k}^{n}(-1)^{i - k}\dfrac{(n!)^{2}2^{i}(2n - 2i)!}{k!(i - k)![(n - i)!]^2}\\
&= \sum\limits_{i = 0}^{n - k}(-1)^{i}\dfrac{(n!)^{2}2^{i + k}[2(n - k - i)]!}{k!i![(n - k - i)!]^2}\\
&= \dfrac{(n!)^{2}2^{k}}{k!}\sum\limits_{i = 0}^{n - k}(-1)^{i}\dfrac{2^{i}[2(n - k - i)]!}{i![(n - k - i)!]^2}\\
\end{aligned}
$$
现在我们会发现，右边的求和式的结果只和 $n - k$ 的取值有关，于是我们可以将它 $\mathcal{O}(n^{2})$ 预处理出来过后直接 $\mathcal{O}(1)$ 询问。
代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 998244353;
ll t, n, ans, f[2005], fct[2005], inv[2005], power[2005];
ll ksm(ll x, ll y) {
ll ret = 1;
while(y) {
if(y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
ll c(ll n, ll m) {
return fct[n] * inv[m] % mod * inv[n - m] % mod;
}
int gsm(int x) {return ((~x & 1) << 1) - 1;}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
fct[0] = 1;
for(int i = 1; i <= 2000; ++i) fct[i] = fct[i - 1] * i % mod;
inv[2000] = ksm(fct[2000], mod - 2);
for(int i = 2000; i >= 1; --i) inv[i - 1] = inv[i] * i % mod;
power[0] = 1;
for(int i = 1; i <= 2000; ++i) power[i] = (power[i - 1] << 1) % mod;
for(int i = 0; i <= 1000; ++i) {
for(int j = 0; j <= i; ++j) {
f[i] += gsm(j) * power[j] * fct[(i - j) << 1] % mod * inv[j] % mod * inv[i - j] % mod * inv[i - j] % mod;
}
f[i] = (f[i] % mod + mod) % mod;
}
cin >> t;
while(t--) {
cin >> n;
for(int k = 0; k <= n; ++k) {
cout << fct[n] * fct[n] % mod * power[k] % mod * inv[k] % mod * f[n - k] % mod << '\n';
}
}
return 0;
}
```