题解：P12374 「LAOI-12」Sigma

· · 题解

本题解会从最基础的开始讲，然后逐渐优化到满分做法。

以下内容中 V 均代表值域，即 \displaystyle\max_{i=1}^{n}{a_i}。

Subtask 1：我会模拟！

直接根据题目意思模拟，时间复杂度 O(V^n)。

期望得分：5 分。

Subtask 2：我会数学！

因为 n \le 5000，所以我们首先考虑枚举区间。然后思考对于每个区间怎么算这个和。下面设 m 为区间长度。

由于这里都是加法，那么每个求和符号之间实际上是相互独立的。那么，这里求和符号的顺序就可以随意交换。假设在一个式子中，第 j 个求和符号下界为 d_j，上界为 u_j。那么通过贡献法与乘法原理，不难发现，第 j 个求和符号对答案的贡献是：

\dfrac{(d_j+u_j)\times(u_j-d_j+1)}{2}\times\Big(\displaystyle\prod_{i=1,i\not=j}^{m}(u_i-d_i+1)\Big)

直接对着这个式子算即可，时间复杂度 O(n^4)。

期望得分：35 分。

Subtask 3 & 4：我会逆元！

将上面式子写成另外一种形式：

\dfrac{(d_j+u_j)\times(u_j-d_j+1)}{2}\times\dfrac{\displaystyle\prod_{i=1}^{m}(u_i-d_i+1)}{(u_j-d_j+1)}

于是 u_j-d_j+1 消掉了，变成了：

\dfrac{(d_j+u_j)}{2}\times\displaystyle\prod_{i=1}^{m}(u_i-d_i+1)

于是这个式子中所有式子都可以在循环的过程中算出来。由于要取模，所以需要用到 2 在模 998244353 意义下的逆元 499122177。将除以 2 换成乘 499122177 即可。时间复杂度 O(n^2)。至此，我们通过了这道题。

注意精细取模。

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed a[5005], c[5005];
const int mod = 998244353;
signed main() {
    int n, ans = 0; scanf("%d", &n);
    for(int i = 1;i <= n;i++) scanf("%d", &a[i]);
    for(int i = 1;i <= n;i++) {
        int sum = 1, ssum = 0;
        for(int j = i;j <= n;j++) {
            if(a[j] < (j-i+1)) break;
            c[j] = (1ll * (j-i+1+a[j]) * 499122177) % mod;
            sum = (sum * (a[j]-j+i)) % mod; ssum = (ssum + c[j]) % mod;
            ans = (ans + (sum * (ssum % mod)) % mod) % mod;
        } 
    } printf("%d\n", ans);
    return 0;
}