P4921 [MtOI2018] 情侣关系，为何要被烧毁呢？
摘要：P4921 [MtOI2018] 情侣？给我烧了！ 大意 (n) 对情侣，恰好 (k) 对在 (2 times n) 的电影院中坐一起的方案数。 思路 很好的题目，使得我的大脑旋转。 首先我们先定义函数 (f(n, k))
P4921 [MtOI2018] 情侣？给我烧了！
大意
\(n\) 对情侣，恰好 \(k\) 对在 \(2 \times n\) 的电影院中坐一起的方案数。
思路
很好的题目，使得我的大脑旋转。
首先我们先定义函数 \(f(n, k)\) 表示 \(n\) 对情侣有 \(k\) 对恰好坐到一块的方案数。首先我们要从 \(n\) 对情侣中选择 \(k\) 对，这个是 \(\binom{n}{k}\) 的，再从 \(n\) 排选择 \(k\) 排，这个也是 \(\binom{n}{k}\) 的，考虑到这 \(k\) 对情侣间也有先后顺序，贡献就是 \(k!\)，两人可以换位，贡献是 \(2 ^ k\)，剩下有 \(n - k\) 对情侣，我们只需要将其错排即可。
定义 \(g(m)\) 表示 \(m\) 对情侣错排的方案数，我们考虑这个怎么求。这个我们可以利用容斥原理，我们考虑直接计算至少 \(j\) 对和睦的方案数，那么这个的贡献与上面的类似，应当是 \(\binom{m}{j} ^ 2 j! 2 ^ j (2(m - j))!\)，那么由容斥可知：
\[g(m) = \sum_{j = 0} ^ {m}(-1) ^ j \binom{m}{j} ^ 2 j! 2 ^ j (2(m - j))!
\]
那么我们合并一下整个式子，就是：
\[f(n, k) = \binom{n}{k} ^ 2 k ! 2 ^ k g(n - k)
\\
= \binom{n}{k} ^ 2 k ! 2 ^ k \sum_{j = 0} ^ {n - k}(-1) ^ j \binom{n - k}{j} ^ 2 j! 2 ^ j (2(n - k - j))!
\]
这个式子我们是可以直接求的，于是就完成了。
代码
#include<iostream>
using namespace std;
#define int long long
const int MOD = 998244353;
const int MAXN = 2e3 + 5;
int C[MAXN][MAXN];
int fac[MAXN];
int g[MAXN], pow2[MAXN];
void init(){
C[0][0] = 1;
for(int i = 1;i < MAXN;i ++){
C[i][0] = C[i][i] = 1;
for(int j = 1;j < i;j ++){
C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
}
}
fac[0] = 1;
for(int i = 1;i < MAXN;i ++){
fac[i] = (fac[i - 1] * i) % MOD;
}
pow2[0] = 1;
for(int i = 1;i < MAXN;i ++){
pow2[i] = pow2[i - 1] * 2 % MOD;
}
for(int m = 0;m <= 1000;m ++){
g[m] = 0;
for(int j = 0;j <= m;j ++){
int a = (j % 2 == 0) ? 1 : MOD - 1;
int res = C[m][j] * C[m][j] % MOD;
res = (res * fac[j]) % MOD;
res = (res * pow2[j]) % MOD;
res = (res * fac[2 * (m - j)]) % MOD;
res = (res * a) % MOD;
g[m] = (g[m] + res) % MOD;
}
}
return;
}
int f(int n, int k){
int res = (C[n][k] * C[n][k]) % MOD;
res = (res * fac[k]) % MOD;
res = (res * pow2[k]) % MOD;
res = (res * g[n - k]) % MOD;
return res;
}
int T, n, k;
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
init();
cin >> T;
while(T --){
cin >> n;
for(int i = 0;i <= n;i ++){
cout << f(n, i) << '\n';
}
}
return 0;
}