卷积和求和

链接:https://ac.nowcoder.com/acm/contest/5633/C
卷积和求和

 

好像是数学公式样的,下次遇到这种题目可以想着打表找规律

 

 

维护sum[i]=\SigmaΣ a[i]*(n-i+1)
枚举第一列的 a[i]a[i] 那么每次乘上的数字就是(sum[n]-sum[i-1])*i。
所以

ans+=a[i]∗(sum[n]−sum[i−1])∗i

注意取模就行:

#include<bits/stdc++.h>
using namespace std;
int n;
long long a[200005];
int mod=1e9+7;
int sum[10];
int main()
{
    cin>>n;
    memset(a,0,sizeof(a));
    memset(sum,0,sizeof(sum));
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        sum[i]+=sum[i-1]+(n-i+1)*a[i];
    }
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=(ans+(a[i]*(sum[n]-sum[i-1])%mod)*i%mod)%mod;
    }
    ans=(ans+mod)%mod;
    cout<<ans<<endl;
} 

 

上一篇:最小费用最大流


下一篇:UVA11383 Golden Tiger Claw KM算法