P15729 [JAG 2024 Summer Camp #2] Add Add Add

ooliver 发布于 23 小时前 54 次阅读 OI

AI 摘要

你是否好奇，如何在O(1)内快速计算两个数组连续k项和的全部组合？一个巧妙的递推公式+前缀和优化，让复杂求和瞬间流畅。点击揭秘这个看似复杂却简洁高效的算法！

P15729 [JAG 2024 Summer Camp #2] Add Add Add

不难发现，当前答案应该是上一个答案加上 $i+j=k (i,j\le n)$ 的贡献，所以考虑求：

$$
\begin{aligned}
&\sum_{i+j=k(i,j\le n)} (A_i+B_j) \\
=&\sum_{i=\max(k-n,1)}^{min(k-1,n)} (A_i+B_{k-i}) \\
=&\sum_{i=\max(k-n,1)}^{min(k-1,n)} A_i +\sum_{i=\max(k-n,1)}^{min(k-1,n)} B_i
\end{aligned}
$$

前缀和即可。

代码：

C++
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=2e5+5;
int n,k,ans;
int a[N],b[N];

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],a[i]+=a[i-1];
    for(int i=1;i<=n;i++) cin>>b[i],b[i]+=b[i-1];
    for(int i=2;i<=2*n;i++) cout<<(ans+=a[min(n,i-1)]-a[max(i-n,1ll)-1]+b[min(n,i-1)]-b[max(i-n,1ll)-1])<<"\n";
    return 0;
}