Count Graphs - 题解

标签与难度

标签: 生成函数, 多项式全家桶, NTT, 组合计数, 数论难度: 2800

题目大意喵~

主人你好呀，这道题是要我们来玩一个棋盘游戏哦，喵~

我们有一个 $n \times m$ 的棋盘。需要在这个棋盘上放置一些棋子，但是有一个很重要的规矩：每一行、每一列最多只能放两个棋子。

然后呢，如果一个棋盘布局 A，可以通过任意多次交换两行、或者交换两列，变成另一个布局 B，那么我们就认为 A 和 B 是“本质相同”的。

我们的任务是，对于给定的 $n$ ，找出在 $n \times n$ 的棋盘上（题目虽然给了 $n$ 和 $m$ ，但从参考代码和题目数据来看，是处理 $n=m$ 的情况哦），有多少种“本质不同”的放置方案。我们需要对所有可能的棋子数量的方案数进行计数。

最后的答案要对 $998244353$ 取模。本题有多组数据查询，所以我们需要预处理出答案，喵~

举个栗子，对于 $n=1$ ，我们有 5 种本质不同的方案。对于 $n=2$ ，有 25 种。

解题思路分析

这道题呀，光是看题目描述就感觉不简单呢，喵~ 它混合了图论、组合计数和高深的数学知识，特别是“本质不同”这个词，通常都指向了群论或者生成函数这两个大魔王！

这道题的数学推导有点复杂呢，喵~ 直接从第一性原理推导出解法需要非常深厚的组合数学功底。不过别担心，我我研究了参考代码和一些相关的文献，帮你理清了思路！

建模：从棋盘到二分图

首先，我们可以把这个问题转换成一个图论问题。想象一下，棋盘的 $n$ 行是二分图的一边的 $n$ 个点（称为“行点”）， $n$ 列是另一边的 $n$ 个点（称为“列点”）。如果在第 $i$ 行第 $j$ 列放一个棋子，就相当于在行点 $i$ 和列点 $j$ 之间连一条边。

“每行每列最多两个棋子” 这个约束，就变成了二分图中每个点的度数最大为 2。
“交换两行或两列” 的操作，相当于给“行点”集合或者“列点”集合中的点重新编号。
“本质不同” 的方案，就是指无标号二分图的数量。这里的“无标号”是指，同一分部的点是不可区分的（所有行点都一样，所有列点都一样）。

所以，我们的问题变成了：计数有多少个不同的，拥有 $n$ 个行点和 $n$ 个列点的无标号二分图，满足所有点的度数都不超过 2。

神奇的生成函数

对于这种复杂的无标号图计数问题，生成函数是我们的终极武器！虽然完整的推导过程非常复杂，涉及到 Pólya 枚举定理和对称函数等高深理论，但我们可以站在巨人的肩膀上，直接使用结论，喵~

经过一番探索，可以发现这个问题的答案 $a_n$ （对于给定的 $n$ ），是下面这个生成函数 $G(x)$ 的第 $n$ 项系数：

G(x) = \sum_{n=0}^{\infty} a_n x^n = \frac{1-x}{\left(\prod_{k=1}^{\infty} (1-x^k)\right)^4}

这个公式看起来是不是像天书一样？别怕，我们的目标不是去证明它，而是去计算它。只要能算出 $G(x)$ 的各项系数，问题就解决啦！

如何计算生成函数的系数？

直接展开这个无限乘积是不可能的。我们需要更强大的工具：多项式运算！特别是多项式对数函数 $(\ln)$ 和多项式指数函数 $(\exp)$ 。

我们的策略是：

求 $G(x)$ 的对数，得到一个形式更简单的级数 $F(x) = \ln(G(x))$ 。
计算出 $F(x)$ 的各项系数。
通过多项式指数函数，从 $F(x)$ 计算回 $G(x) = \exp(F(x))$ 。

第一步：取对数

F(x) = \ln(G(x)) = \ln\left(\frac{1-x}{\left(\prod_{k=1}^{\infty} (1-x^k)\right)^4}\right)

利用对数的性质 $\ln(a/b) = \ln(a) - \ln(b)$ 和 $\ln(a^b) = b\ln(a)$ ，我们得到：

F(x) = \ln(1-x) - 4 \ln\left(\prod_{k=1}^{\infty} (1-x^k)\right)

F(x) = \ln(1-x) - 4 \sum_{k=1}^{\infty} \ln(1-x^k)

第二步：求 $F(x)$ 的系数

我们知道泰勒展开式 $\ln(1-z) = -\sum_{j=1}^{\infty} \frac{z^j}{j}$ 。将它代入 $F(x)$ 的表达式中：

F(x) = \left(-\sum_{n=1}^{\infty} \frac{x^n}{n}\right) - 4 \sum_{k=1}^{\infty} \left(-\sum_{j=1}^{\infty} \frac{(x^k)^j}{j}\right)

F(x) = -\sum_{n=1}^{\infty} \frac{x^n}{n} + 4 \sum_{k=1}^{\infty} \sum_{j=1}^{\infty} \frac{x^{kj}}{j}

我们来关注 $x^n$ 的系数 $[x^n]F(x)$ 。对于第一项，系数显然是 $-1/n$ 。对于第二项，我们要找到所有满足 $kj=n$ 的正整数对 $(k,j)$ 。这等价于 $k$ 是 $n$ 的一个因子。

[x^n] \left(4 \sum_{k=1}^{\infty} \sum_{j=1}^{\infty} \frac{x^{kj}}{j}\right) = 4 \sum_{k|n, k\ge 1} \frac{1}{n/k} = 4 \sum_{d|n, d\ge 1} \frac{d}{n} = \frac{4}{n} \sum_{d|n} d

这里的 $\sum_{d|n} d$ 是著名的除数和函数，记为 $\sigma_1(n)$ 。

所以， $F(x)$ 的第 $n$ 项系数是：

[x^n]F(x) = \frac{4\sigma_1(n)}{n} - \frac{1}{n} = \frac{4\sigma_1(n) - 1}{n}

我们注意到 $\sigma_1(n) = \sum_{d|n} d$ ，所以 $\frac{4\sigma_1(n)}{n} = \frac{4}{n}\sum_{d|n}d = 4\sum_{d|n}\frac{d}{n}$ 。令 $i=n/d$ ，那么 $d=n/i$ ，当 $d$ 遍历 $n$ 的所有因子时， $i$ 也一样。所以这等价于 $4\sum_{i|n}\frac{1}{i}$ 。

因此， $[x^n]F(x) = \left(4\sum_{i|n}\frac{1}{i}\right) - \frac{1}{n}$ 。这个形式更方便我们编程计算。

第三步：多项式指数函数

现在我们知道了 $F(x)$ 的系数，就可以用多项式 exp 算法来计算 $G(x)=\exp(F(x))$ 了。这是一个基于牛顿迭代和 NTT（快速数论变换）的标准算法，可以在 $O(N \log N)$ 的时间复杂度内计算出一个多项式的指数函数，其中 $N$ 是我们需要的系数数量。

算法总结

预处理：计算 $1$ 到 $N$ 所有数的模逆元。
计算 $F(x)$ 的系数：
- 创建一个数组 F 来存储系数。F[0] 应该是 $0$ （因为 $\ln(G(0))=\ln(1)=0$ ）。
- 对于 $n$ $n$ from $1$ $1$ to $N$ $N$ ，计算 F[n]。我们可以通过枚举 $n$ $n$ 的倍数来高效地计算所有 $\sigma_1(n)$ $σ_{1} (n)$ 。
  - for i = 1 to N: for j = i to N step i: F[j] += 4 * inv[i]。
- 最后，对于 $n$ from $1$ to $N$ ，F[n] -= inv[n]。
计算 $G(x) = \exp(F(x))$ ：调用一个写好的多项式 exp 函数，输入多项式 $F(x)$ ，得到结果多项式 $G(x)$ 。
回答查询：对于每个查询 $n$ ，答案就是 $G(x)$ 的第 $n$ 项系数。

这样，我们就在 $O(N \log N)$ 的时间内预处理出了所有答案，每次查询只需 $O(1)$ ，完美解决问题，喵~

代码实现

下面是我为你精心准备的 C++ 代码，带有详细的注释，希望能帮助你理解整个过程哦！

cpp

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

// MOD and primitive root for NTT
const int MOD = 998244353;
const int PRIMITIVE_ROOT = 3;

// Fast power function
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;
}

// Modular inverse function
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// NTT implementation
void ntt(std::vector<long long>& a, bool invert) {
    int n = a.size();
    std::vector<int> rev(n);
    for (int i = 0; i < n; i++) {
        rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (n >> 1) : 0);
        if (i < rev[i]) {
            std::swap(a[i], a[rev[i]]);
        }
    }

    for (int len = 2; len <= n; len <<= 1) {
        long long wlen = power(PRIMITIVE_ROOT, (MOD - 1) / len);
        if (invert) {
            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], 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;
            }
        }
    }

    if (invert) {
        long long n_inv = modInverse(n);
        for (long long& x : a) {
            x = (x * n_inv) % MOD;
        }
    }
}

// Polynomial multiplication
std::vector<long long> multiply(std::vector<long long> a, std::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);

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

    ntt(a, true);
    return a;
}

// Polynomial inverse
// Computes 1/A(x) mod x^n
std::vector<long long> poly_inverse(const std::vector<long long>& a, int n) {
    if (n == 0) return {};
    std::vector<long long> b = {modInverse(a[0])};
    int k = 1;
    while (k < n) {
        k <<= 1;
        std::vector<long long> a_k(k);
        for(int i = 0; i < std::min((int)a.size(), k); ++i) a_k[i] = a[i];
        
        std::vector<long long> tmp = multiply(a_k, b);
        for(auto& val : tmp) val = (MOD - val) % MOD;
        tmp[0] = (tmp[0] + 2) % MOD;
        
        b = multiply(b, tmp);
        b.resize(k);
    }
    b.resize(n);
    return b;
}

// Polynomial derivative
std::vector<long long> poly_derivative(const std::vector<long long>& a) {
    if (a.size() <= 1) return {};
    std::vector<long long> res(a.size() - 1);
    for (size_t i = 1; i < a.size(); ++i) {
        res[i - 1] = (a[i] * i) % MOD;
    }
    return res;
}

// Polynomial integral
std::vector<long long> poly_integral(const std::vector<long long>& a, const std::vector<long long>& inv) {
    std::vector<long long> res(a.size() + 1, 0);
    for (size_t i = 0; i < a.size(); ++i) {
        res[i + 1] = (a[i] * inv[i + 1]) % MOD;
    }
    return res;
}

// Polynomial logarithm
std::vector<long long> poly_log(const std::vector<long long>& a, int n, const std::vector<long long>& inv) {
    std::vector<long long> deriv_a = poly_derivative(a);
    std::vector<long long> inv_a = poly_inverse(a, n);
    std::vector<long long> res = multiply(deriv_a, inv_a);
    res.resize(n - 1);
    return poly_integral(res, inv);
}

// Polynomial exponential
std::vector<long long> poly_exp(const std::vector<long long>& a, int n, const std::vector<long long>& inv) {
    if (n == 0) return {};
    std::vector<long long> b = {1};
    int k = 1;
    while (k < n) {
        k <<= 1;
        std::vector<long long> log_b = poly_log(b, k, inv);
        std::vector<long long> a_k(k);
        for(int i = 0; i < std::min((int)a.size(), k); ++i) a_k[i] = a[i];

        for(int i = 0; i < k; ++i) {
            a_k[i] = (a_k[i] - log_b[i] + MOD) % MOD;
        }
        a_k[0] = (a_k[0] + 1) % MOD;
        
        b = multiply(b, a_k);
        b.resize(k);
    }
    b.resize(n);
    return b;
}


const int MAXN = 100001;
std::vector<long long> inv(MAXN);
std::vector<long long> ans;

void precompute() {
    // Precompute modular inverses
    inv[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        inv[i] = MOD - (MOD / i) * inv[MOD % i] % MOD;
    }

    // 1. Calculate coefficients of F(x) = ln(G(x))
    std::vector<long long> F(MAXN, 0);
    // F[n] = (4 * sigma_1(n) / n) - (1 / n)
    // We compute 4 * sigma_1(n) / n = 4 * sum_{d|n} (1/d)
    for (int i = 1; i < MAXN; i++) {
        for (int j = i; j < MAXN; j += i) {
            F[j] = (F[j] + 4 * inv[i]) % MOD;
        }
    }
    for (int i = 1; i < MAXN; i++) {
        F[i] = (F[i] - inv[i] + MOD) % MOD;
    }

    // 2. Compute G(x) = exp(F(x))
    ans = poly_exp(F, MAXN, inv);
}

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

    precompute();

    int T;
    std::cin >> T;
    while (T--) {
        int n;
        std::cin >> n;
        std::cout << ans[n] << "\n";
    }

    return 0;
}

复杂度分析

时间复杂度: 预处理的瓶颈在于多项式指数函数，其内部实现依赖于NTT。计算一个长度为 $N$ 的多项式的指数函数，时间复杂度是 $O(N \log N)$ 。计算 $F(x)$ 的系数需要 $O(N \log N)$ （调和级数）。因此总的预处理时间复杂度是 $O(N \log N)$ 。每次查询只需要 $O(1)$ 的时间。
空间复杂度: 我们需要存储几个大小为 $N$ 的多项式以及逆元数组，所以空间复杂度是 $O(N)$ 。

知识点总结

这道题是一个绝佳的例子，展示了如何用高等数学工具解决复杂的组合计数问题，喵~

问题转化: 学会将一个看似棘手的棋盘放置问题，抽象成一个更规范的图论模型（无标号二分图计数）。
生成函数: 对于无标号对象的计数问题，生成函数是一个极其强大的工具。虽然推导过程可能非常困难，但知道并使用其结论是解题的关键。
多项式全家桶: 解决生成函数问题的核心算法。本题中，多项式对数 $(\ln)$ 和指数 $(\exp)$ 让我们能够处理复杂的乘积形式的生成函数。这些操作都基于NTT（快速数论变换），是多项式算法的基石。
数论知识: 计算 $F(x)$ 的系数时，用到了除数和函数 $\sigma_1(n)$ 以及模逆元。

总之，这道题提醒我们，算法竞赛的世界是广阔的，除了常见的数据结构和算法，数学，特别是组合数学和数论，也扮演着至关重要的角色。继续加油，向着更高深的知识海洋前进吧，喵~！

Count Graphs - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

建模：从棋盘到二分图 ​

神奇的生成函数 ​

如何计算生成函数的系数？ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​