题意

$求\sum_{l=1}^{n}\sum_{r = l}^{n}f(l,r),其中f(l,r) = \sum_{i = l}^{r} a_i \cdot w_{l-r+1}$

思路：

$要求的答案ans = [ \ f(1,1) + f(1,2)+f(1,3) + .........................+f(1,n)\ ] +$
$\quad \quad \quad \quad \quad \quad \quad \ \ \ \ \ \ \ [f(2,2)+f(2,3)+f(2,4)....................f(2,n)] +$
$\quad \quad \quad \quad \quad \quad \quad \ \ \ \ \ \ \ [f(3,3)+f(3,4)+f(3,5)............f(3,n)] +$
$\quad \quad \quad \quad \quad \quad \quad \ \ \ \ \ \ \ .................................. +$
$\quad \quad \quad \quad \quad \quad \quad \ \ \ \ \ \ \ ............................... +$
$\quad \quad \quad \quad \quad \quad \quad \ \ \ \ \ \ \ ......$

$\quad \quad \quad \quad \quad \quad \quad \ \ \ \ \ \ \ [f(n-1,n-1)+f(n-1,n)]+$
$\quad \quad \quad \quad \quad \quad \quad \ \ \ \ \ \ \ [f(n,n)]$

$每个中括号里面的f(i,j)拆开，其中用sum[i]表示a_i的前缀和，那么就有$
$[(sum[1]-sum[0]) \cdot w_1 + (sum[2]-sum[0]) \cdot w_2 + .................+(sum[n] - sum[0]) \cdot w_n] +$
$[(sum[2]-sum[1]) \cdot w_1 + (sum[3]-sum[1]) \cdot w_2 + ..+(sum[n] - sum[1]) \cdot w_{n-1}] +$
.......
.......

$[(sum[n] - sum[n-1]) \cdot w_1]$

$之后将w_1的系数提取整理得到的是(sum[n] - sum[0])$
$w_2整理得到的是(sum[n]+sum[n-1]-sum[1]-sum[0])$
$w_3整理的到的是(sum[n] + sum[n-1]+sum[n-2] - sum[2] - sum[1] - sum[0])$
.... $w_{n-1}整理得到的是(sum[n]+sum[n-1] + .... + sum[2] - sum[n-2] - sum[n-3] - ... - sum[0])$
$w_{n} 整理得到的是(sum[n]+...+sum[1] - sum[n-1]-....sum[0])$

$仔细观察不难发现，对于sum[0],sum[1],sum[2],....,sum[n-1],sum[n]$
$w_i的系数就是用这个数组后i个的和减去这个数组前i个的和，那么我们用S_i表示sum[i]的前缀和$
$w_i的系数就是 (S_{n} - S_{n-i}) - (S_{i-1})$
$将每个w_i的贡献算出来，求和即可，注意减法运算取模要加上一个模数$

#include <cstdio>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 3e5 + 10;
int n;
ll S[N],w[N];
int main(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        ll x;scanf("%lld",&x);
        S[i] = (S[i-1] + x) % mod;
    }
    for(int i = 1;i <= n;i++){
        scanf("%lld",w + i);
    }
    for(int i = 1;i <= n;i++){
        S[i] = (S[i] + S[i - 1]) % mod;
    }
    ll ans = 0;
    for(int i = 1;i <= n;i++){
        ans = (ans + (S[n] - S[n - i] - S[i - 1] + mod) * w[i] % mod) % mod;
    }
    printf("%lld\n",ans);
    return 0;
}

【每日一题】区间权值

题意

思路：