EasyIntegration - 题解

标签与难度

标签: 数学, 组合数学, 微积分, 数论, 快速幂, 逆元, 费马小定理 难度: 1900

题目大意喵~

主人你好呀，喵~ 这道题是关于一个看起来有点复杂的定积分计算哦！

题目要求我们计算下面这个式子的值：

$$\int_{0}^1 (x - x^2)^n \mathrm{d} x$$

其中 $n$ 是给定的一个整数。

题目还告诉我们，这个积分的结果是一个有理数，可以表示成 $\frac{p}{q}$ 的形式。我们需要输出这个结果在模 $998244353$ 意义下的值，也就是 $(p \cdot q^{-1}) \pmod{998244353}$ 呐。

简单来说，就是算一个积分，然后求它对一个大质数取模的结果，喵~

解题思路分析

这个积分式子 $\int_{0}^1 (x - x^2)^n \mathrm{d} x$ 乍一看可能会让一些主人头疼，但别担心喵！跟着我的爪印一步步来，我们就能把它变成一个我们熟悉的样子！

第一步：简化积分表达式

首先，我们来观察一下积分里面的部分 $(x - x^2)^n$。我们可以把 $x$ 提取出来，对吧？

$$(x - x^2)^n = (x(1-x))^n = x^n (1-x)^n$$

这样一来，我们的积分就变成了：

$$I_n = \int_{0}^1 x^n (1-x)^n \mathrm{d} x$$

这个形式是不是看起来清爽多啦？喵~

第二步：寻找递推关系

这个 $x^a (1-x)^b$ 形式的积分，在数学里有一个非常响亮的名字，叫做贝塔函数 (Beta Function)，记作 $B(a+1, b+1)$。不过，就算不认识它也没关系，我们可以用更基础的分部积分法来解决它！

让我们定义一个更一般的积分形式：

$$I(a, b) = \int_{0}^1 x^a (1-x)^b \mathrm{d} x$$

我们要求的 $I_n$ 就是 $I(n, n)$。

现在，我们对 $I(a, b)$ 使用分部积分法。回忆一下公式：$\int u \mathrm{d}v = uv - \int v \mathrm{d}u$。 我们令：

• $u = (1-x)^b$
• $\mathrm{d}v = x^a \mathrm{d}x$

那么：

• $\mathrm{d}u = -b(1-x)^{b-1} \mathrm{d}x$
• $v = \frac{x^{a+1}}{a+1}$

代入分部积分公式：

$$I(a, b) = \left[ (1-x)^b \cdot \frac{x^{a+1}}{a+1} \right]_0^1 - \int_0^1 \frac{x^{a+1}}{a+1} \cdot (-b(1-x)^{b-1}) \mathrm{d}x$$

我们先看第一部分 $\left[ (1-x)^b \cdot \frac{x^{a+1}}{a+1} \right]_0^1$：

• 当 $x=1$ 时，$(1-x)^b = 0$，所以整个式子是 $0$。
• 当 $x=0$ 时，$x^{a+1} = 0$，所以整个式子也是 $0$。 所以，第一部分的值就是 $0 - 0 = 0$ 啦！

那么积分就只剩下第二部分了：

$$I(a, b) = - \int_0^1 \frac{-b}{a+1} x^{a+1} (1-x)^{b-1} \mathrm{d}x$$

把常数 $\frac{b}{a+1}$ 提出去：

$$I(a, b) = \frac{b}{a+1} \int_0^1 x^{a+1} (1-x)^{b-1} \mathrm{d}x$$

看，右边的积分不就是 $I(a+1, b-1)$ 吗？于是我们得到了一个漂亮的递推关系：

$$I(a, b) = \frac{b}{a+1} I(a+1, b-1)$$

第三步：求解递推式

现在我们用这个递推关系来求 $I(n, n)$：

$$I(n, n) = \frac{n}{n+1} I(n+1, n-1)$$

$$= \frac{n}{n+1} \cdot \frac{n-1}{n+2} I(n+2, n-2)$$

$$= \frac{n}{n+1} \cdot \frac{n-1}{n+2} \cdot \frac{n-2}{n+3} \cdots$$

一直递推下去，直到 $b$ 变成 $0$：

$$\cdots = \left( \frac{n}{n+1} \cdot \frac{n-1}{n+2} \cdots \frac{1}{2n} \right) I(2n, 0)$$

这个连乘的部分可以整理一下：

$$\frac{n \cdot (n-1) \cdots 1}{(n+1) \cdot (n+2) \cdots 2n} = \frac{n!}{\frac{(2n)!}{n!}} = \frac{n! \cdot n!}{(2n)!}$$

接下来，我们计算递推的终点 $I(2n, 0)$：

$$I(2n, 0) = \int_0^1 x^{2n} (1-x)^0 \mathrm{d}x = \int_0^1 x^{2n} \mathrm{d}x = \left[ \frac{x^{2n+1}}{2n+1} \right]_0^1 = \frac{1}{2n+1}$$

把两部分乘起来，就得到最终的公式啦！

$$I(n, n) = \frac{n! \cdot n!}{(2n)!} \cdot \frac{1}{2n+1} = \frac{(n!)^2}{(2n+1)!}$$

太棒了！我们把一个复杂的积分问题转化成了一个组合数学问题，喵~

第四步：模运算

我们现在需要计算 $\frac{(n!)^2}{(2n+1)!} \pmod{998244353}$。 令 $p = (n!)^2$，$q = (2n+1)!$。我们需要计算 $(p \cdot q^{-1}) \pmod{M}$，其中 $M=998244353$ 是一个质数。

根据费马小定理，对于一个质数 $M$ 和一个整数 $q$（$q$ 不是 $M$ 的倍数），有 $q^{M-1} \equiv 1 \pmod{M}$。 所以，$q \cdot q^{M-2} \equiv 1 \pmod{M}$，这意味着 $q$ 在模 $M$ 意义下的逆元就是 $q^{M-2}$。

因此，我们的计算步骤是：

1. 预处理计算出所有需要的阶乘值，一直到 $(2n+1)!$。因为 $n$ 最大可达 $10^6$，所以我们需要预处理到 $2 \cdot 10^6 + 1$ 左右。
2. 计算分子 numerator = $(n!)^2 \pmod M$。
3. 计算分母 denominator = $(2n+1)! \pmod M$。
4. 使用快速幂算法计算分母的逆元 inv_denominator = $denominator^{M-2} \pmod M$。
5. 最终答案就是 (numerator * inv_denominator) % M。

这样，问题就完美解决啦！

代码实现

这是我根据上面的思路，精心为主人准备的代码~ 注释很详细的哦！

#include <iostream>
#include <vector>

// 使用 long long 防止中间计算溢出
using ll = long long;

// 我们的模数，喵~
const int MOD = 998244353;
// n 的最大值是 10^6，所以阶乘需要计算到 2*n+1，开大一点比较安全
const int MAXN = 2000010;

// 用于存储预处理的阶乘值
ll factorial[MAXN];

// 快速幂函数，用来计算 (base^exp) % mod
// a^b mod m
ll quick_power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        // 如果指数是奇数，就把当前的 base 乘到结果里
        if (exp % 2 == 1) {
            res = (res * base) % MOD;
        }
        // base 自乘，指数减半
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 预处理阶乘的函数
void precompute_factorials() {
    factorial[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        factorial[i] = (factorial[i - 1] * i) % MOD;
    }
}

int main() {
    // 设置cin/cout不与C风格IO同步，可以跑得更快哦
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 先把阶乘都算好，一劳永逸喵~
    precompute_factorials();

    int n;
    // 循环读入 n，直到文件结束
    while (std::cin >> n) {
        // 根据我们的公式 I_n = (n! * n!) / (2n + 1)!
        
        // 计算分子 (n!)^2 mod M
        ll numerator = (factorial[n] * factorial[n]) % MOD;
        
        // 计算分母 (2n+1)! mod M
        ll denominator = factorial[2 * n + 1];
        
        // 根据费马小定理，denominator 的逆元是 denominator^(M-2)
        ll inv_denominator = quick_power(denominator, MOD - 2);
        
        // 最终结果是 (分子 * 分母的逆元) mod M
        ll ans = (numerator * inv_denominator) % MOD;
        
        std::cout << ans << "\n";
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O(\max(N) + T \cdot \log M)$

  • 预处理阶乘的时间复杂度是 $O(\max(N))$，其中 $\max(N)$ 是 $n$ 可能的最大值，这里是 $2 \cdot 10^6$。
  • 对于每个查询，我们需要进行几次乘法和一次快速幂。快速幂的时间复杂度是 $O(\log M)$。
  • $T$ 是测试用例的数量。因为有预处理，所以总时间非常快！

• 空间复杂度: $O(\max(N))$

  • 我们需要一个数组 factorial 来存储预处理的阶乘值，其大小与 $n$ 的最大值的两倍成正比，所以空间复杂度是 $O(\max(N))$。

知识点总结

这道题虽然伪装成了一道微积分题，但它的核心其实是数学推导和数论呢，喵~

1. 微积分与组合数学的联系: 通过分部积分法，我们将一个定积分问题转化为了一个可以用阶乘表示的组合公式。那个 $I(a,b)$ 的积分其实就是贝塔函数 $B(a+1, b+1)$，它和伽马函数（阶乘的推广）有密切关系：$B(x,y) = \frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)}$。
2. 模块化算术 (Modular Arithmetic): 编程竞赛中常见的技巧，特别是处理可能非常大的数字时。
3. 模逆元 (Modular Inverse): 在模运算中实现除法的关键。当模数 $M$ 为质数时，可以使用费马小定理 $a^{M-2} \equiv a^{-1} \pmod M$ 来求逆元。
4. 快速幂 (Fast Exponentiation): 在 $O(\log N)$ 时间内计算 $a^N$ 的高效算法，是求模逆元的基础。
5. 预处理 (Precomputation): 对于需要多次查询且每次查询都依赖某些重复计算的问题（如此处的阶乘），预先计算好所有可能用到的值并存储起来，是一种非常有效的优化策略。

希望这篇题解能帮助到主人！如果还有不懂的地方，随时可以再来问我哦，喵~