自动搬运

查看原文

来自洛谷，原作者为

	Eason_cyx Play like you never did before?

搬运于2025-08-24 23:15:03，当前版本为作者最后更新于2025-04-28 12:57:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

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

以下内容中 $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;
}