Problem C. Stack

问题描述

对于一个排列 P，定义 (f(P)) 如下：

1
2
3
4
5
6
7
function f(P):
    stack = []
    for element in P:
        while stack is not empty and stack.top() > element:
            stack.pop()
        stack.push(element)
    return the size of stack

给定一个整数 n，求所有长度为 n 的排列 P 的 $f(P)^3$的和，对 998244353 取模。

输入

本题有多组输入数据。 第一行输入一个正整数 ($T(1 \leq T \leq 10^5)$)，表示输入数据组数。 接下来的每组输入数据，输入一个正整数 ($n(1 \leq n \leq 5 \cdot 10^5)$)。

输出

对于每组输入数据，输出一行一个整数，表示答案。

思路

  1. 理解栈的行为：函数 (f(P)) 实际上是计算排列 P 经过类似 “单调栈” 处理后的栈大小。对于每个元素，我们弹出栈中所有比它大的元素，然后将其入栈，最终栈的大小就是 (f(P)) 的值。

  2. 数学期望与组合：由于需要计算所有排列的 ($(f(P))^3$) 之和，直接枚举所有排列是不可能的（n 最大为 ($5 \cdot 10^5$)。我们可以推出递推公式。

  3. 递推关系：

    • 设 (f_3(n)) 表示所有长度为 n 的排列的 ($(f(P))^3 $) 之和
    • 设 (f_2(n)) 表示所有长度为 n 的排列的 ($(f(P))^2$) 之和
    • 设 (f_1(n)) 表示所有长度为 n 的排列的 (f(P)) 之和

    通过分析可以得到递推公式：

    • (f_1(n) = f_1(n-1) + $\frac{f_1(n-1) + (n-1)!}{n}$)
    • (f_2(n) = f_2(n-1) + $\frac{2 \cdot f_2(n-1) + 2 \cdot f_1(n-1) + (n-1)!}{n}$)
    • (f_3(n) = f_3(n-1) + $\frac{3 \cdot f_2(n-1) + 3 \cdot f_1(n-1) + (n-1)!}{n}$)

  4. 预处理：我们预处理出所有可能的 n 对应的结果，然后直接返回。

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
using ll = long long;

ll mod = 998244353;
ll inv[500010], fact[500010];
ll f1[500010], f2[500010], f3[500010];

// 快速幂计算 a^b mod mod
ll mo(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return res % mod;
}

// 预处理阶乘、逆元和f1, f2, f3数组
void preprocess() {
    // 计算逆元
    inv[1] = 1;
    for (int i = 2; i <= 500000; i++) {
        inv[i] = mo(i, mod - 2);
    }
    
    // 计算阶乘
    fact[0] = 1;
    for (int i = 1; i <= 500000; i++) {
        fact[i] = fact[i - 1] * i % mod;
    }
    
    // 初始化f1, f2, f3
    f1[1] = 1;
    f2[1] = 1;
    f3[1] = 1;
    
    // 递推计算f1, f2, f3
    for (int i = 2; i <= 500000; i++) {
        f1[i] = (f1[i - 1] + inv[i] * (f1[i - 1] + fact[i - 1]) % mod) % mod;
        
        ll temp = (2 * f2[i - 1] + 2 * f1[i - 1] + fact[i - 1]) % mod;
        f2[i] = (f2[i - 1] + inv[i] * temp % mod) % mod;
        
        temp = (3 * f2[i - 1] + 3 * f1[i - 1] + fact[i - 1]) % mod;
        f3[i] = (f3[i - 1] + inv[i] * temp % mod) % mod;
    }
}

int main() {
    preprocess();
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        printf("%lld\n", f3[n]);
    }
    
    return 0;
}

解释

  1. 预处理：
    • 计算逆元：使用费马小定理，($inv[i] = i^{mod-2} \mod mod$)
    • 计算阶乘：($fact[i] = i! \mod mod$)
    • 计算 (f1, f2, f3)：根据递推公式，从 1 到 ($5 \cdot 10^5$) 预处理所有值
  2. 查询处理：对于每个查询，直接返回预处理好的 ($f3[n]$)
  3. 时间复杂度：
    • 预处理：($O(5 \cdot 10^5)$)
    • 每个查询：($O(1)$)
    • 总时间复杂度：($O(5 \cdot 10^5 + T)$)，能够满足题目要求