P5686 [CSP-S2019 江西] 和积和

简要题意

给定两个 个元素的序列 ，求下面这个式子对 取模的结果：

策略分析

如果直接模拟那么时间复杂度是爆炸级的 ，显然正常人都不会这么做，正常人会选择可爱的前缀和，所以最后一层括号复杂度变成 ，总复杂度 ，比刚刚好了很多，但依然是过不去的，所以我们考虑对前缀和进行优化。

设 的前缀数组为 ， 的前缀数组为 。那么上面的式子显然可以写成： 这样看我们求解还不是很方便，因为存在前面的求和符号，我们不便于对整体的式子进行观察，所以我们用一个 较小的式子看一下，比方说令 ，那么我们按照这个式子带进去展开化简得到： 那么前面系数为 的那个式子我们就可以 求了，关键转移到了如何求后面这一坨东西。我们把 和 按照下标放到矩阵里看一看： 我们发现这不就是 每一项去乘 每一项吗，唯一的遗憾是对角线全是 。我们期望能够对这个式子进行因式分解使其变成两个只包含 或 的式子相乘，那么其实想办法把这个对角线给它补齐就行了，我们发现对角线的 下标相等，那么就和刚刚系数为 的那个式子一模一样了，所以我们在这多减一遍，前面多加一遍，整个式子的值不变，式子变成这样： 然后把这个结论归纳到 项得： 图中三个求和符不存在嵌套，所以每一个都可以拿出来单独计算，时间复杂度降低到了 ，于是这道题就做完了。做题的时候要注意，本题给定的数都特别大，所以在求解的过程中不要忘记时刻取模。

参考代码

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
#include <iostream>
#include <cstdio>
#define LL long long
using namespace std;

namespace SHAWN {
    const LL N = 5e5 + 7, mod = 1e9 + 7;
    LL n, ans, A, B;
    LL a[N], b[N];
    int work()
    {
        cin >> n;
        for (int i = 1; i <= n; ++i) { 
            cin >> a[i];
            a[i] = (a[i] + a[i - 1]) % mod;// 求a的前缀
        }
        for (int i = 1; i <= n; ++i) {
            cin >> b[i];
            b[i] = (b[i] + b[i - 1]) % mod;// 求b的前缀
        }
        for (int i = 1; i <= n; ++i) {
            ans = (ans % mod + ((n + 1) * a[i]) % mod * b[i] % mod) % mod;
            // 处理第一个求和符
            A = (A + a[i]) % mod;
            // 处理第二个求和符
            B = (B + b[i]) % mod;
            // 处理第三个求和符
        }
        ans = ((ans - (A * B % mod)) + mod) % mod;
        // 将三个求和符号按照推出来的式子加到一块
        cout << ans % mod << '\n';
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}