CF1342E Placing Rooks

发表于2020-07-28更新于2023-09-17字数统计789阅读时长7分作者Shane

题目链接

Solution

要满足每个格子都能被共击，那么就要使每一行都有车，或者每一列都有车。以每一行都有车为例，设有 jj 列放了车。由于每多一列，能相互共击的车的对数就会减 1，因此放 jj 列车就有 n−jn-j 对车能相互共击。题目要求 kk 对车能相互共击，那么只能在 n−kn-k 列放置车 (显然 k⩾ nk\geqslant\ n时答案为 0)。从 nn 列选取 n−kn-k 列的方案数为 Cnn−kC_n^{n-k}。接下来考虑在 n−kn-k 列中放入 nn 个车，每列不空的方案数。

令 PiP_i 表示事件: 在这 n−kn-k 列中第 ii 列没有放车。由容斥原理有 ∣P1‾∩P2‾∩...∩Pn−k‾∣=N−∑1<=i<=n−k∣Pi∣+∑1<=i<j<=n−k∣Pi∩Pj∣|\overline{P_1} \cap \overline{P_2} \cap ...\cap \overline{P_{n-k}}|= N-\sum\limits_{1<=i<={n-k}}|P_i|+\sum\limits_{1<=i<j<={n-k}}|P_i\cap P_j| −∑1<=i<j<q<=n−k∣Pi∩Pj∩Pq∣+...+(−1)n−k∣P1∩P2∩...∩Pn−k∣-\sum\limits_{1<=i<j<q<={n-k}}|P_i\cap P_j\cap P_q|+...+(-1)^{n-k}|P_1\cap P_2 \cap ...\cap P_{n-k}|。

设一列下标集合 SS，大小为∣S∣(∣S∣<=n−k)|S|(|S|<=n-k)，这样的集合有Cn−k∣S∣C_{n-k}^{|S|}个。则满足 ∀i∈S\forall i \in S，第 ii 列没有放车的方案数为 (n−k−∣S∣)n(n-k-|S|)^n，即 nn 个车放在剩下 n−k−∣S∣n-k-|S| 列的任意一个中的方案数。根据前面的公式，容易得出每一行都有车且满足题目条件的方案数为 Cnn−k∑i=0n−k(−1)iCn−ki(n−k−i)nC_n^{n-k}\sum\limits_{i=0}^{n-k}(-1)^iC_{n-k}^{i}(n-k-i)^n。如果 kk 不等于 0，则每一行都有车和每一列都有车不等价，总的答案应该乘以 2，即 2Cnn−k∑i=0n−k(−1)iCn−ki(n−k−i)n2C_n^{n-k}\sum\limits_{i=0}^{n-k}(-1)^iC_{n-k}^{i}(n-k-i)^n。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int maxn = 2e5 + 5;
ll n, k, inv[maxn], fac[maxn], ans;

ll qpow(ll a, ll b) {
    ll ans = 1, base = a;
    while (b) {
        if (b & 1) ans = ans * base % MOD;
        b >>= 1, base = base * base % MOD;
    }
    return ans;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % MOD;
    for (int i = 0; i <= n; i++) inv[i] = qpow(fac[i], MOD - 2);
}

ll C(ll a, ll b) { return fac[a] * inv[b] % MOD * inv[a - b] % MOD; }

int main() {
    cin >> n >> k;
    if (k >= n) cout << 0, exit(0);
    init();
    for (int s = 0; s <= n - k; s++) {
        ans += (s & 1 ? -1 : 1) * C(n - k, s) * qpow(n - k - s, n) % MOD;
        ans %= MOD;
    }
    ans = ans * (!k ? 1 : 2) * C(n, n - k) % MOD;
    cout << (ans + MOD) % MOD;
    return 0;
}