P4921 [MtOI2018]情侣？给我烧了！

前言

情人节写的这道题，题目名称好符合我当时的心情。

题目链接

解法

容斥

我们发现最后要求的结果是恰好 \(k\) 对情侣坐在一起的方案数，我们就不难想到去计算恰好 \(n-k\) 对没坐在一起的方案数。那么我们很自然的得到最后答案： \(ans = C_n^k \times A_n^k \times 2^k \times g_{n-k}\)，\(g_k\) 为恰好 \(k\) 对情侣没坐在一起的方案数，然后就可以快乐的容斥了：

\[g_k = \sum_{i=0}^k (-1)^i \times 2^i \times C_k^i \times A_k^i \times (2\times k -2\times i)!
\]

这玩意预处理一下也就是 \(O(n^2)\) 的复杂度，总复杂度也就是 \(O(Tn + N^2)\)。

反演

我们发现题目中有恰好二字，这不就在暗示我们可以用二项式反演吗。我们直接令 \(F_i\) 为至少 \(i\) 对情侣坐一起的方案数，\(G_i\) 为恰好 \(i\) 对情侣坐一起的方案数，由二项式反演可知：

\[F_k = \sum_{i=k}^n \binom{i}{k} G_i \iff G_k = \sum_{i=k}^n (-1)^{i-k} \binom{i}{k} F_i
\]

我们现在只需要求出 \(F_i\) 即可。

显而易见，\(F_k = C_n^k \times A_n^k \times 2^k \times (2\times n - 2\times k)!\)，我们将它代入到上面的式子得：

\[\begin{aligned}
G_k &= \sum_{i=k}^n (-1)^{i-k} \times 2^i \times C_i^k \times C_n^i \times A_n^i \times (2\times n - 2 \times i)! \\&
= \sum_{i=0}^{n-k} (-1)^i \times 2^{i+k} \times C_{i+k}^k \times C_n^{i+k} \times A_n^{i+k} \times (2\times n - 2 \times k - 2\times i)! \\&
= \frac{2^k \times n! \times n!}{k!} \sum_{i=0}^{n-k} \frac{(-1)^i \times 2^i \times (2\times n- 2\times k-2\times i)!}{i! \times (n - k - i)! \times (n - k - i)!}
\end{aligned}\]

我们也只需要进行预处理就可以了，最后复杂度和上边是一样的。

Code

#include<bits/stdc++.h>

#define int long long

const int M = 2e3 + 7 , mod = 998244353;

int fac[M] , inv[M] , f[M] , pow2[M];

inline int Pow(int a , int b) {

	int ans = 1; for(;b; b >>= 1 , a= a * a % mod) if(b & 1) ans = ans * a % mod;

	return ans;

}

inline int C(int n , int m) {

	if(n < 0 || m < 0 || n < m) return 0;

	return fac[n] * inv[m] % mod * inv[n - m] % mod;

}

inline int A(int n , int m) {

	if(n < 0 || m < 0 || n < m) return 0;

	return fac[n] * inv[n - m] % mod;

}

signed main () {

	int t; std::cin >> t;

	pow2[0] = 1, inv[0] = fac[0] = 1; for(int i = 1; i <= 2e3; ++ i) fac[i] = fac[i - 1] * i % mod , inv[i] = Pow(fac[i] , mod - 2) , pow2[i] = pow2[i - 1] * 2 % mod;

	for(int i = 0; i <= 1e3; ++ i)

		for(int j = 0; j <= i; ++ j) (f[i] += ((j & 1) ? mod - 1 : 1) * inv[j] % mod * pow2[j] % mod * fac[i - j << 1] % mod * inv[i - j] % mod * inv[i - j] % mod) %= mod;

	while(t --) {

		int n; std::cin >> n;

		for(int i = 0; i <= n; ++ i) std::cout << (fac[n] * fac[n] % mod * pow2[i] % mod * inv[i] % mod * f[n - i] % mod) << '\n';

	}

}

巴特西

P4921 [MtOI2018]情侣？给我烧了！

前言

题目链接

解法

容斥

反演

最新文章

热门文章