随机棋盘(Easy Version) - 题解

标签与难度

标签: 组合数学, 期望, 容斥原理, Rook多项式, 多项式快速幂, NTT 难度: 2200

题目大意喵~

哈喵~！各位算法大师们，今天我们来挑战一个有趣的棋盘问题，喵~

题目要求我们计算在一个 $n \times n$ 的棋盘上，放置 $n$ 个互不攻击的“车”的方案数的期望值。不过呢，这个棋盘不是一个普通的棋盘，上面有一些格子是禁止放车的。

这些禁止格子的生成方式有点特别：

1. 设 $m = \lfloor n/2 \rfloor$。
2. 我们先随机生成一个 $\{1, 2, \dots, m\}$ 的排列 $p$。
3. 对于每个 $i$ 从 $1$ 到 $m$，我们会在棋盘上的三个位置打上禁止标记：
   • $(2 \cdot p_i - 1, 2 \cdot i - 1)$
   • $(2 \cdot p_i, 2 \cdot i - 1)$
   • $(2 \cdot p_i, 2 \cdot i)$

我们需要计算在所有可能的随机排列 $p$（一共有 $m!$ 种）下，合法放置方案数的平均值（也就是期望），结果对 $998244353$ 取模。

简单来说，就是：求在随机生成的禁区下，放置 $n$ 个互不攻击的车的方案数期望。

解题思路分析

这道题看起来好复杂呀，又是随机又是期望的，让人头大，喵~ 不过别怕，让我来带你一步步解开它的神秘面纱！

核心洞察：期望的线性性质与对称性

题目的核心是求期望。根据期望的线性性质，一个随机变量的和的期望等于它们各自期望的和。我们可以把总方案数这个随机变量 $X$ 分解成很多个小的指示随机变量的和。

$E[X] = E[\sum_{\pi} I_{\pi}] = \sum_{\pi} E[I_{\pi}]$

这里 $\pi$ 代表一种在无限制的 $n \times n$ 棋盘上的合法布阵方案（也就是一个排列），$I_{\pi}$ 是一个指示变量：如果布阵 $\pi$ 在当前随机生成的棋盘上是合法的（没有棋子在禁止格上），则 $I_{\pi}=1$，否则为 $0$。$E[I_{\pi}]$ 就是布阵 $\pi$ 合法的概率。

这个思路看起来还是好复杂，因为每个 $\pi$ 的合法概率都和 $\pi$ 的具体结构有关。

但是，我们可以换个角度思考！我们要求的是所有 $m!$ 种可能的棋盘的方案数之和，再除以 $m!$。

$$E[\text{方案数}] = \frac{1}{m!} \sum_{\text{所有排列 } p} \text{方案数}(p)$$

这里的 $\text{方案数}(p)$ 指的是由排列 $p$ 生成的棋盘所对应的合法方案数。

这时，一个关键的、让问题瞬间变简单的想法出现了：对于任何一个排列 $p$，它生成的棋盘的合法方案数都是一样的！ 也就是说，$\text{方案数}(p)$ 是一个与 $p$ 无关的常数。

为什么呢？喵？

我们可以通过一个巧妙的“重新标记”法来证明。假设我们有两个不同的排列 $p$ 和 $p'$。我们可以找到一种方式重新标记棋盘的行，使得由 $p$ 生成的禁止格位置，在新标记下，完全等同于由 $p'$ 生成的禁止格位置。

比如说，我们想把由任意排列 $p$ 生成的棋盘，变成由单位排列 $p_{id}$（即 $p_{id}(i)=i$）生成的棋盘。 我们可以定义一个行的置换 $\sigma$。对于任意行组 $R_k = \{2k-1, 2k\}$，我们把它映射到新的行组 $R_{p^{-1}(k)}$。这样一来，原来排列 $p$ 中 $C_j \to R_{p_j}$ 的禁止关系，在新的行标下就变成了 $C_j \to R_j$ 的关系，这不就和 $p_{id}$ 生成的棋盘一模一样了吗？

既然对于任何排列 $p$，方案数都相同，那我们只需要计算其中一个最简单情况的方案数就好啦！这个最简单的当然就是 $p$ 是单位排列，$p_i = i$ 的情况。

此时，期望值就等于单位排列 $p_{id}$ 所生成的棋盘的方案数。

$$E[\text{方案数}] = \frac{1}{m!} \sum_{p} \text{方案数}(p_{id}) = \frac{1}{m!} \cdot m! \cdot \text{方案数}(p_{id}) = \text{方案数}(p_{id})$$

转化为固定棋盘问题

当 $p_i=i$ 时，禁止的格子变成了： 对于所有 $j \in \{1, \dots, m\}$：

• $(2j-1, 2j-1)$
• $(2j, 2j-1)$
• $(2j, 2j)$

我们的问题就变成了：在一个有上述固定禁区的棋盘上，放 $n$ 个互不攻击的“车”有多少种方案？

这是一个经典的带禁区的排列计数问题，可以用容斥原理解决。而解决这类问题的有力工具，就是Rook多项式 (Rook Polynomials)，喵~

Rook多项式大法好！

Rook多项式是专门用来解决这类问题的组合工具。对于一个棋盘上的禁区 $B$，它的Rook多项式 $R(x, B)$ 定义为：

$$R(x, B) = \sum_{k=0}^{\infty} c_k x^k$$

其中 $c_k$ 是在禁区 $B$ 上放置 $k$ 个互不攻击的“车”的方案数。

根据容斥原理，在 $n \times n$ 棋盘上，避开禁区 $B$ 放置 $n$ 个互不攻击的“车”的方案数为：

$$\text{方案数} = \sum_{k=0}^{n} (-1)^k c_k (n-k)!$$

现在，我们来分析我们这个问题的禁区 $B$。它是由 $m$ 个互不相干的小块组成的。 每个小块 $B_j$（对应 $j=1, \dots, m$）的禁区都在行 $\{2j-1, 2j\}$ 和列 $\{2j-1, 2j\}$ 的交集上。具体来说，是 $(2j-1, 2j-1), (2j, 2j-1), (2j, 2j)$ 这三格。

由于这些禁区小块 $B_j$ 之间在行和列上都没有重叠，整个禁区 $B$ 的Rook多项式就是所有小块的Rook多项式的乘积！

$$R(x, B) = \prod_{j=1}^{m} R(x, B_j)$$

我们来计算一下一个小块 $B_j$ 的Rook多项式 $P(x) = R(x, B_j)$。这个小块的禁区可以看作是一个 $2 \times 2$ 棋盘上禁止了 $(1,1), (2,1), (2,2)$ 三个位置。

• $c_0$: 在禁区里放0个车，只有1种方法（什么都不放）。
• $c_1$: 在禁区里放1个车，有3个格子可以选，所以有3种方法。
• $c_2$: 在禁区里放2个互不攻击的车，只能放在 $(1,1)$ 和 $(2,2)$。但 $(2,1)$ 也被禁止了，所以只能放在 $(1,1)$ 和 $(2,2)$。哦，我看看，是 $(1,1)$ 和 $(2,2)$ 吗？不对，是 $(2j-1, 2j-1)$ 和 $(2j, 2j)$。啊哈，这两个格子在同一列 $2j-1$ 和 $2j$ 上，所以是可以的。不对，$(2j-1, 2j-1)$ 和 $(2j, 2j)$ 是可以的，但 $(2j, 2j-1)$ 和 $(2j, 2j)$ 不行。让我重新看看禁区：$(2j-1, 2j-1)$, $(2j, 2j-1)$, $(2j, 2j)$。 要放2个不互相攻击的车，只能是 $(2j-1, 2j-1)$ 和 $(?, 2j)$ 的组合。但列 $2j$ 只有一个禁区格 $(2j, 2j)$，所以只能是 $(2j-1, 2j-1)$ 和 $(2j, 2j)$。啊，这两个位置的行不同，列也不同，所以是互不攻击的！所以 $c_2=1$。
• $c_k=0$ for $k>2$。

所以，单个小块的Rook多项式是 $P(x) = 1 + 3x + x^2$。

那么，整个禁区的Rook多项式就是：

$$R(x, B) = (1 + 3x + x^2)^m$$

最后的计算

我们的任务就清晰了：

1. 计算多项式 $C(x) = (1 + 3x + x^2)^m = \sum_{k=0}^{2m} c_k x^k$。
2. 计算最终答案 $\sum_{k=0}^{2m} (-1)^k c_k (n-k)!$。

如何高效地计算多项式的 $m$ 次方呢？当然是用多项式快速幂啦！每次多项式乘法，我们用 NTT (Number Theoretic Transform) 来加速，它可以在 $O(D \log D)$ 的时间内完成两个度为 $D$ 的多项式乘法。 总的时间复杂度就是 $O(m \log m \cdot \log m)$，对于 $n \le 5000$ 来说，这完全足够了！

于是，解题步骤就是：

1. 确定 $m = \lfloor n/2 \rfloor$。
2. 预计算阶乘和阶乘的逆元。
3. 构造基础多项式 $P(x) = 1 + 3x + x^2$。
4. 使用NTT实现的快速幂，计算出 $C(x) = P(x)^m$ 的系数 $c_k$。
5. 根据公式 $\sum_{k=0}^{2m} (-1)^k c_k (n-k)!$ 计算最终答案。

这样，一个看起来很棘手的问题，就被我们一步步分解成熟悉的模块解决了，是不是很有成就感呢？喵~

代码实现

这是我根据上面的思路，精心重构的一份代码，注释超详细的哦，希望能帮到你理解，喵~

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

// 定义一个足够大的质数和NTT的原根
const int MOD = 998244353;
const int G = 3; // MOD的原根

// 快速幂函数，用于计算 a^b % MOD
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 模逆元函数，用于计算 a^{-1} % MOD
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// NTT核心实现
// is_inverse为false时是正变换(DFT)，为true时是逆变换(IDFT)
void ntt(vector<long long>& a, bool is_inverse) {
    int n = a.size();
    
    // Cooley-Tukey蝶形变换的位逆序置换
    for (int i = 1, j = 0; i < n; i++) {
        int bit = n >> 1;
        for (; j & bit; bit >>= 1) {
            j ^= bit;
        }
        j ^= bit;
        if (i < j) {
            swap(a[i], a[j]);
        }
    }

    // 迭代计算DFT
    for (int len = 2; len <= n; len <<= 1) {
        long long wlen = power(G, (MOD - 1) / len);
        if (is_inverse) {
            wlen = modInverse(wlen);
        }
        for (int i = 0; i < n; i += len) {
            long long w = 1;
            for (int j = 0; j < len / 2; j++) {
                long long u = a[i + j];
                long long v = (a[i + j + len / 2] * w) % MOD;
                a[i + j] = (u + v) % MOD;
                a[i + j + len / 2] = (u - v + MOD) % MOD;
                w = (w * wlen) % MOD;
            }
        }
    }

    // 如果是逆变换，需要乘以 1/n
    if (is_inverse) {
        long long n_inv = modInverse(n);
        for (long long& x : a) {
            x = (x * n_inv) % MOD;
        }
    }
}

// 多项式乘法 (a * b)
vector<long long> multiply(vector<long long> a, vector<long long> b) {
    int sz = 1;
    while (sz < a.size() + b.size()) sz <<= 1;
    a.resize(sz);
    b.resize(sz);

    ntt(a, false);
    ntt(b, false);

    vector<long long> c(sz);
    for (int i = 0; i < sz; i++) {
        c[i] = (a[i] * b[i]) % MOD;
    }

    ntt(c, true);
    return c;
}

// 多项式快速幂 (p^exp)
vector<long long> poly_pow(vector<long long> p, int exp) {
    vector<long long> res = {1};
    while (exp > 0) {
        if (exp % 2 == 1) res = multiply(res, p);
        p = multiply(p, p);
        exp /= 2;
    }
    return res;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    int m = n / 2;

    if (m == 0) {
        cout << 1 << endl; // n=1时，只有一种方案
        return 0;
    }

    // 预计算阶乘
    vector<long long> fact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    // 基础Rook多项式 P(x) = 1 + 3x + x^2
    vector<long long> p = {1, 3, 1};

    // 计算 C(x) = P(x)^m
    vector<long long> rook_poly_coeffs = poly_pow(p, m);

    // 根据容斥原理计算最终答案
    long long ans = 0;
    for (int k = 0; k < rook_poly_coeffs.size(); k++) {
        if (n - k < 0) break;
        long long term = (rook_poly_coeffs[k] * fact[n - k]) % MOD;
        if (k % 2 == 1) {
            ans = (ans - term + MOD) % MOD;
        } else {
            ans = (ans + term) % MOD;
        }
    }

    cout << ans << endl;

    return 0;
}

复杂度分析

• 时间复杂度: $O(n \log n + m \log m \cdot \log m)$

  • 预计算阶乘需要 $O(n)$。
  • 多项式快速幂需要进行 $O(\log m)$ 次多项式乘法。
  • 每次多项式乘法，我们需要将多项式扩展到长度为 $O(m)$ 的2的幂，然后进行NTT。NTT的复杂度是 $O(m \log m)$。
  • 所以，计算Rook多项式系数的总时间是 $O(m \log m \log m)$。
  • 最后计算总和需要 $O(m)$。
  • 整体复杂度由多项式快速幂主导。

• 空间复杂度: $O(m)$

  • 存储阶乘需要 $O(n)$ 的空间。
  • NTT和多项式乘法中，需要存储长度为 $O(m)$ 的多项式系数向量。所以空间复杂度为 $O(m)$。

知识点总结

这道题是一个非常漂亮的组合数学问题，把多个知识点巧妙地串联在了一起，喵~

1. 期望的线性性质: 它是我们简化问题的出发点，让我们能够将对随机过程的期望计算，转化为对单一确定性问题的求解。
2. 对称性分析: 发现问题解的数量与具体排列无关，是本题破局的关键！这大大降低了问题的复杂度。
3. 容斥原理与Rook多项式: 这是解决“带禁止区域的排列计数”问题的标准武器。理解Rook多项式的定义和它与容斥原理的关系，可以让我们系统地解决这类问题。
4. 多项式运算与NTT: 当组合问题涉及到递推或生成函数，且规模较大时，多项式运算（特别是卷积）就派上用场了。NTT是实现多项式乘法的高效算法。
5. 多项式快速幂: 这是将普通快速幂思想应用到多项式上，用于高效计算多项式的n次方。

通过这道题，我们可以深刻体会到组合数学的魅力，以及如何运用代数工具（多项式）来解决复杂的计数问题。希望大家都能从中学到新知识，喵~！