题解 P4921 【[MtOI2018]情侣？给我烧了！】
辰星凌
·
·
题解
【题解】情侣？给我烧了！[MtOI2018] [P4921]
\mathcal{My}\ \mathcal{Blog}
传送门：情侣？给我烧了！\text{[MtOI2018] [P4921]}
【题目描述】
共 T (T\leqslant 1000) 次询问，每次给出一个正整数 n (n\leqslant 1000) ，表示有 n 对情侣和 n 排座位（每排有两个位置），对于 k\in[0,n]，求出恰好有 k 对情侣坐在同一排的方案数。
【分析】
组合意义天地灭，代数推导保平安。 —— tiger0133
这里提供一个不需要费脑子的二项式反演做法（其实柿子都一样，只是这样做更易理解）。
题面加粗黑体字已经给出了很明显的提示，按照套路先设计两个状态：
$g(i)$：**至少**有 $i$ 对情侣坐在一排的方案数。
易知 $g(k)=\sum_{i=k}^{n}C_{i}^{k}f(i)$ 。
由二项式反演可得：$f(k)=\sum_{i=k}^{n}(-1)^{i-k}C_{i}^{k}g(i)$ 。
其中 $g(i)=C_{n}^{i}A_{n}^{i}(2!)^{i}(2n-2i)!$，$C_{n}^{i}$ 表示的是选定坐同一排的某 $i$ 对情侣，$A_{n}^{i}$ 为选定某 $i$ 排，$(2!)^{i}$ 为这 $i$ 对情侣内部顺序的乘积，$(2n-2i)!$ 表示剩下的人可以随便排。
则：
$$\begin{aligned}f(k)&=\sum_{i=k}^{n}(-1)^{i-k}C_{i}^{k}C_{n}^{i}A_{n}^{i}(2!)^{i}(2n-2i)!\\&=\sum_{i=0}^{n-k}(-1)^{i}C_{i+k}^{k}C_{n}^{i+k}A_{n}^{i+k}2^{i+k}(2n-2k-2i)!\\&=\sum_{i=0}^{n-k}(-1)^{i}\frac{(i+k)!}{k!i!}\frac{n!}{(i+k)!(n-i-k)!}\frac{n!}{(n-i-k)!}2^{i+k}(2n-2k-2i)!\\&=\frac{2^{k}(n!)^2}{k!}\sum_{i=0}^{n-k}\frac{(-1)^{i}2^{i}}{i!}\frac{(2n-2k-2i)!}{((n-k-i)!)^{2}} \end{aligned}$$
观察后面那个求和柿子，其值只与给定的上界 $n-k$ 有关，在同一上界下对于不同的 $n$ 都是一样的结果。把它预处理出来即可 $O(1)$ 查询。
时间复杂度为：$O(n^2+Tn)$ 。预处理的那个柿子是个卷积的形式，可以用 $\text{NTT}$ 优化到 $O(n\log n)$，但意义不大，也过不了加强版。
## **【Code】**
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=2003,P=998244353;
int n,T,h[N],Mi[N],jc[N],inv[N],invjc[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
int main(){
// freopen("123.txt","r",stdin);
inv[1]=Mi[0]=jc[0]=jc[1]=invjc[0]=invjc[1]=1,Mi[1]=2;
for(Re i=2;i<=2000;++i)jc[i]=(LL)jc[i-1]*i%P,inv[i]=(LL)inv[P%i]*(P-P/i)%P,invjc[i]=(LL)invjc[i-1]*inv[i]%P,Mi[i]=(Mi[i-1]<<1)%P;
for(Re i=0;i<=1000;++i)
for(Re j=0;j<=i;++j)
(h[i]+=(LL)((j&1)?P-1:1)*invjc[j]%P*Mi[j]%P*jc[i-j<<1]%P*invjc[i-j]%P*invjc[i-j]%P)%=P;
in(T);
while(T--){
in(n);
for(Re k=0;k<=n;++k)printf("%lld\n",(LL)jc[n]*jc[n]%P*invjc[k]%P*Mi[k]%P*h[n-k]%P);
}
}
```