Moe's CF Life

喵~ 主人，你好呀！今天我们来看一道非常有趣的组合计数问题，Codeforces 上的 1312D - Count the Arrays。这道题将组合数学和模运算巧妙地结合在了一起，就像猫咪踩在键盘上也能敲出美妙的代码一样神奇！下面就让本猫娘带你一步步解开这道题的谜题吧，喵~

D. Count the Arrays

题目大意

主人，这道题是要求我们计算满足以下所有条件的数组数量，喵~

数组包含 $n$ 个元素。
每个元素都是从 $1$ 到 $m$ 的整数。
数组中恰好有一对元素是相等的。
数组存在一个“山峰”结构。也就是说，存在一个索引 $i$ ，使得在第 $i$ 个元素之前，数组是严格递增的；在第 $i$ 个元素（包括它）之后，数组是严格递减的。

我们需要计算满足这些条件的数组总数，并对 $998244353$ 取模。

举个例子，当 $n=3, m=4$ 时，满足条件的数组有： [1, 2, 1], [1, 3, 1], [1, 4, 1], [2, 3, 2], [2, 4, 2], [3, 4, 3] 一共 6 个，喵~

解题思路

这道题看起来限制条件很多，但只要我们把这些条件一个个拆开来看，思路就会变得清晰起来啦！

首先，我们来分析一下这些条件的内在联系，喵~

条件3（恰好一对相等）：这意味着数组中的 $n$ 个元素实际上是由 $n-1$ 个不同的数字组成的。其中一个数字出现了两次，其他 $n-2$ 个数字都只出现了一次。
条件4（山峰结构）：这个结构 a_1 < a_2 < ... < a_i > a_{i+1} > ... > a_n 告诉我们，a_i 是整个数组中唯一的最大值。如果还有其他元素和 a_i 一样大，就无法满足严格递增或严格递减的条件了。

结合这两个条件，我们可以得出一个关键的推论：

那个出现两次的重复元素，一定不是山峰顶点的那个最大值！因为最大值是唯一的嘛，喵~

好了，有了这个关键发现，我们就可以像搭积木一样，一步步构造出所有满足条件的数组了。这是一个典型的组合计数问题，我们可以分步来计算。

第一步：选择构成数组的 $n-1$ 个不同数字。 数组由 $n-1$ 个不同的数字组成。这些数字需要从 $1$ 到 $m$ 中选取。那么，从 $m$ 个数中选出 $n-1$ 个，有多少种选法呢？当然是组合数 $C(m, n-1)$ 啦！
第二步：确定山峰和重复的元素。 在我们选出的这 $n-1$ 个数中，最大的那个数必须是山峰顶点（数组中的最大值），这是由山峰结构决定的，所以山峰元素是唯一确定的，没有选择的余地。那么，哪个数是重复的呢？根据我们之前的分析，山峰元素不能重复。所以，我们只能从剩下的小一点的 $n-2$ 个数中，选择一个作为重复元素。这里就有 $n-2$ 种选择。
第三步：排列这些数字形成山峰数组。 现在我们手上有：1个山峰元素（最大值），1个重复元素（会出现两次），以及 $n-3$ 个其他不同的元素。总共 $1+2+(n-3) = n$ 个位置。山峰元素的位置是固定的，它就是数组的顶点。剩下的 $n-1$ 个位置需要被填满。我们来思考一下这些数该怎么放：
- 重复的那个数：它的两个副本必须一个放在山峰的左边（递增序列），一个放在右边（递减序列）。为什么呢？如果它们都在同一侧，比如都在左边，那么数组就会出现 ... < x < ... < x < ... 的情况，这就不是严格递增了，喵！所以，这两个副本必须分居山峰两侧。
- 剩下的 $n-3$ 个不同的数：对于这其中的每一个数，它既可以放在山峰的左侧，也可以放在右侧。一旦确定了它在哪一侧，它在这一侧的具体位置也就固定了（因为序列必须是排好序的）。比如，如果数字5和7都决定放在左侧，那么它们在数组中的顺序一定是 ... < 5 < ... < 7 < ... < peak。所以，对于这 $n-3$ 个数中的每一个，我们都有2种选择（放左边或放右边）。根据乘法原理，总共的放置方法就有 $2^{n-3}$ 种。

总结一下

把以上三步合起来，总的数组数量就是： $ \text{总数} = C(m, n-1) \times (n-2) \times 2^{n-3} $

特殊情况 主人请注意，这个公式对于 $n=2$ 是不成立的。如果 $n=2$ ，数组要有重复元素，只能是 [x, x]。但这个数组既不严格递增也不严格递减，没有山峰。所以当 $n<3$ 时，答案是0。我们的公式里有 (n-2) 和 n-3 这两项，当 n=2 时 n-2=0，结果也是0，所以公式在数学上是自洽的。不过代码实现时最好还是特判一下，喵~

代码实现

下面就是把上面的思路翻译成代码啦！因为涉及到组合数和幂运算，并且需要取模，所以我们需要用到快速幂来计算幂和模逆元，以及用预处理阶乘来高效计算组合数。

cpp

#include <iostream>
#include <vector>

// 使用 long long 防止溢出，喵~
using ll = long long;

// 定义 m 的最大值和模数
const int MAX_M = 200005;
const ll MOD = 998244353;

// 预处理阶乘和阶乘的逆元
ll fact[MAX_M];
ll invFact[MAX_M];

// 快速幂函数 (base^exp % MOD)
// O(log exp) 的时间复杂度哦
ll power(ll base, ll exp) {
    ll res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) {
            res = (res * base) % MOD;
        }
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 预处理阶乘和阶乘逆元
void precompute_factorials() {
    fact[0] = 1;
    for (int i = 1; i < MAX_M; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    // 用费马小定理计算最大阶乘的逆元
    invFact[MAX_M - 1] = power(fact[MAX_M - 1], MOD - 2);
    // 倒推计算其他阶乘的逆元
    for (int i = MAX_M - 2; i >= 0; i--) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
}

// 使用预处理的值计算组合数 C(n, r) mod p
// C(n, r) = n! / (r! * (n-r)!)
ll nCr_mod_p(int n, int r) {
    if (r < 0 || r > n) {
        return 0;
    }
    return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;
}

int main() {
    // 加速一下输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 在程序开始时就预处理好阶乘
    precompute_factorials();

    int n, m;
    std::cin >> n >> m;

    // 特判 n < 3 的情况，此时无法构成山峰结构
    if (n < 3) {
        std::cout << 0 << std::endl;
        return 0;
    }

    // 根据我们的公式计算结果，喵~
    // 1. 计算 C(m, n-1)
    ll combinations = nCr_mod_p(m, n - 1);

    // 2. 乘以 (n-2)，即选择重复元素的方式数
    ll choices_for_repeated = n - 2;

    // 3. 乘以 2^(n-3)，即排列剩余元素的方式数
    ll arrangements = power(2, n - 3);

    // 把所有部分乘起来，每一步都取模哦
    ll ans = (combinations * choices_for_repeated) % MOD;
    ans = (ans * arrangements) % MOD;

    std::cout << ans << std::endl;

    return 0;
}

知识点小课堂喵~

这道题用到了几个重要的算法和数学知识，让我们来复习一下吧！

组合数学 (Combinatorics) 组合数 $C(n, k)$ ，表示从 $n$ 个不同元素中取出 $k$ 个元素的方案数，不考虑顺序。它的公式是： $ C(n, k) = \frac{n!}{k!(n-k)!} $ 在编程竞赛中，当 $n, k$ 很大时，直接计算阶乘会溢出，所以我们通常在模运算下进行计算。
模运算 (Modular Arithmetic) 当计算结果非常大时，我们常常需要对一个固定的数（模数，通常是质数）取余。模运算有一些基本性质：
- (a + b) % M = ((a % M) + (b % M)) % M
- (a * b) % M = ((a % M) * (b % M)) % M 但是除法不适用！(a / b) % M 并不等于 ((a % M) / (b % M)) % M。这时就需要模逆元了。
模逆元 (Modular Inverse) 在模 $M$ 的意义下，一个数 $b$ 的模逆元，记作 $b^{-1}$ ，是指一个数满足 (b * b^{-1}) % M = 1。有了模逆元，我们就可以把模运算下的除法转换成乘法： $ (a / b) \pmod M = (a \times b^{-1}) \pmod M $ 当模数 $M$ 是一个质数时，我们可以用费马小定理来求逆元。
费马小定理 (Fermat's Little Theorem) 如果 $p$ 是一个质数，而整数 $a$ 不是 $p$ 的倍数，则有： $ a^{p-1} \equiv 1 \pmod p $变形一下，就可以得到：$ a^{p-2} \equiv a^{-1} \pmod p $所以，$ a$ 在模 $p$ 下的逆元就是 $a^{p-2}$ 。我们可以用快速幂来计算它。
快速幂 (Modular Exponentiation) 快速幂是一种在 $O(\log b)$ 时间内计算 $a^b \pmod M$ 的算法。它的原理是利用二进制分解指数 $b$ ，反复平方法来加速计算。上面的代码中 power 函数就是快速幂的实现，非常高效，喵~

好啦，今天的小课堂就到这里！希望本猫娘的讲解能帮助主人完全理解这道题。下次再见啦，喵~！

D. Count the Arrays ​

题目大意 ​

解题思路 ​

代码实现 ​

知识点小课堂喵~ ​

D. Count the Arrays

题目大意

解题思路

代码实现

知识点小课堂喵~