数学题刷题记录（数学、数论、组合数学）

• P5686 [CSP-S2019 江西] 和积和
  

简单题，直接将区间求和转换成前缀和，设 \(A_i = \sum_{i = 1}^n a_i,B_i = \sum_{i = 1}^n b_i\)，那么式子为：

\[\sum_{l = 1}^n \sum_{r = l}^n (A_r-A_{l-1})(B_r-B_{l-1})\]

\[=\sum_{l = 1}^n \sum_{r = l}^n A_rB_r-A_rB_{l-1}-A_{l-1}B_r+A_{l-1}B_{l-1}\]
很明显 \(O(n)\) 枚举右端点 \(r\)，式子变成：

\[\sum_{l = 1}^r A_rB_r-A_rB_{l-1}-A_{l-1}B_r+A_{l-1}B_{l-1}\]
如何快速算出这个式子？
我们有：

\[\sum_{l = 1}^r A_rB_r-A_rB_{l-1}-A_{l-1}B_r+A_{l-1}B_{l-1}=\sum_{l = 1}^r A_rB_r-\sum_{l = 1}^r A_rB_{l-1}-\sum_{l = 1}^r A_{l-1}B_r+\sum_{l = 1}^r A_{l-1}B_{l-1}\]
于是可以将四个单项式分类讨论。
\(A_rB_r\) 很好处理，直接算，由于 \(l\) 有 \(r\) 个取值，所以是 \(rA_rB_r\)。
\(A_rB_{l-1}\) 很明显 \(A_r\) 没有问题，但 \(B_{l-1}\) 需要预处理 \(B\) 的前缀和，也就是前缀和的前缀和。
\(A_{l-1}B_r\) 同理。
\(A_{l-1}B_{l-1}\) 很显然需要另外维护两前缀和之积的前缀和。
代码：

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int mod = 1e9+7;
4. const int N = 5e5+5;
5. int a[N],b[N];
6. long long suma[N],sumb[N],prea[N],preb[N],mul[N];
7. signed main()
8. {
9.         ios::sync_with_stdio(0);
10.         cin.tie(0);
11.         cout.tie(0);
12.         int n;
13.         cin >> n;
14.         for(int i = 1;i<=n;++i)
15.         {
16.                 cin >> a[i];
17.                 suma[i] = (suma[i-1]+a[i])%mod;
18.                 prea[i] = (prea[i-1]+suma[i])%mod;
19.         }
20.         for(int i = 1;i<=n;++i)
21.         {
22.                 cin >> b[i];
23.                 sumb[i] = (sumb[i-1]+b[i])%mod;
24.                 preb[i] = (preb[i-1]+sumb[i])%mod;
25.                 mul[i] = (mul[i-1]+1ll*suma[i]*sumb[i]%mod)%mod;
26.         }
27.         long long sum = 0;
28.         for(int i = 1;i<=n;++i)
29.         {
30.                 long long A = i*suma[i]%mod*sumb[i]%mod,B = suma[i]%mod*preb[i-1]%mod,C = sumb[i]%mod*prea[i-1]%mod,D = mul[i-1];
31.                 sum = (sum+(((A-B+mod)%mod-C+mod)%mod+D)%mod)%mod;
32.         }
33.         cout << sum;
34.         return 0;
35. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

感谢分享