吉林大学ACM集训队选拔赛-Pair Complex

题目来源：https://ac.nowcoder.com/acm/problem/206678

可以逐步分析.用数组k来表示b的前缀和，a和b的下标从1开始，那么第一个sum的式子可以表示为

a[l]+k[r]-k[l-1]+a[l+1]+k[r]-k[l]+....a[r]+k[r]-k[r-1]

我们只需要将上面的式子代入第二个sum(前缀和数组k只是为了简写式子，代入时请直接用b[1],b[2],b[3]....)

不难发现，对于每个b[i],总共是出现了n-i+1次

我们可以将数组b进行处理，来表示b[i]的贡献：b[i]=b[i]*(n-i+1)

我们对处理后的b数组进行一次前缀和，前缀和数组为s，并将上面的式子代入第二个sum里，经过整理可以得到

a[1]×(s[n]-s[0])+2×a[2]×(s[n]-s[1])+.....

所以答案显而易见

核心代码：

const int maxn = 1e6 + 50;
ll mod=998244353;
ll a[maxn],b[maxn],s[maxn],ans;
int main() {
    ll n;
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(ll i=1;i<=n;i++) scanf("%lld",&b[i]);
    for(ll i=1;i<=n;i++) b[i]=(b[i]*(n-i+1))%mod;
    for(ll i=1;i<=n;i++) s[i]=(s[i-1]+b[i])%mod;
    for(ll i=1;i<=n;i++) ans=(ans+(((i*a[i])%mod)*(s[n]-s[i-1])%mod)%mod)%mod;
    printf("%lld",ans);
    return 0;
}

吉林大学ACM集训队选拔赛-Pair Complex

原文：https://www.cnblogs.com/sssyk/p/13270259.html