[CSP-S 2019 江西] 和积和

知识点

区间贡献、前缀和、递推计数

解题思路

处理第r项前，令A、B分别为所有以r-1结尾区间的a和、b和之总和，C为这些区间两种和乘积的总和。追加ar、br时，每个旧区间乘积增加ar·旧b和+br·旧a和+ar·br，另有单点区间ar·br，因此C更新为C+ar·B+br·A+r·ar·br。随后A加r·ar、B加r·br，把新C加入答案。所有运算随时取模。

正确性说明

以r结尾的区间由以r-1结尾的每个区间追加新项，加上单点[r,r]构成，恰有r个。展开每个区间的乘积并求和，得到C的递推。A、B同理各追加r次新值。由归纳法状态正确，而每个区间按右端点恰被计入一次，最终累加正确。

易错点

计算C要使用更新前的A、B；r·ar·br分步取模，不能直接做三个大数的乘积；使用64位。

复杂度

时间O(n)，此实现为保存输入a使用O(n)空间，递推状态O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);const long long P=1000000007;int n;cin>>n;vector<long long>a(n+1);for(int i=1;i<=n;i++)cin>>a[i];long long A=0,B=0,C=0,ans=0;for(long long i=1;i<=n;i++){long long b;cin>>b;C=(C+a[i]*B%P+b*A%P+i*a[i]%P*b%P)%P;A=(A+i*a[i])%P;B=(B+i*b)%P;ans=(ans+C)%P;}cout<<ans<<'\n';}