专栏首页小L的魔法馆2018 Wannafly summer camp Day8--区间权值

2018 Wannafly summer camp Day8--区间权值

区间权值 小Bo有nnn个正整数a1a1a_1……anana_n,以及一个权值序列w1w1w_1……wnwnw_n,现在她定义f(l,r)=(∑ri=la2i)∗wr−l+1f(l,r)=(∑i=lrai2)∗wr−l+1f(l,r)=(\sum_{i=l}^r a_i^2) *w_{r-l+1}。 现在他想知道∑nl=1∑nr=lf(l,r)∑l=1n∑r=lnf(l,r)\sum_{l=1}^n \sum_{r=l}^n f(l,r)的值,需要你来帮帮他,你只需要输出答案对109+7109+710^9+7取模后的值。 输入格式 第一行一个正整数nnn 第二行nnn个整数a1a1a_1……anana_n 第三行nnn个整数a1a1a_1……anana_n 输出格式 输出答案109+7109+710^9+7取模 样例输入 3 1 1 1 1 1 1 样例输出 10 数据范围 1<=n<=3∗1051<=n<=3∗1051<=n<=3*10^5 1<=ai<=1071<=ai<=1071<=a_i<=10^7 1<=wi<=1071<=wi<=1071<=w_i<=10^7

思路: 将f(l,r)=(∑ri=la2i)∗wr−l+1f(l,r)=(∑i=lrai2)∗wr−l+1f(l,r)=(\sum_{i=l}^r a_i^2) *w_{r-l+1}展开如下:

⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜a1w1(a1+a2)w2(a1+a2+a3)w3(a1+a2+a3+a4)w4……(a1+a2+……+an)wn……a2w1(a2+a3)w2(a2+a3+a4)w3……(a2+……+an)wn−1……a3w1(a3+a4)w2………………anw1⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟(a1w1……(a1+a2)w2a2w1……(a1+a2+a3)w3(a2+a3)w2a3w1……(a1+a2+a3+a4)w4(a2+a3+a4)w3(a3+a4)w2………………(a1+a2+……+an)wn(a2+……+an)wn−1……anw1)

\begin{pmatrix} a_1w_1 & ……\\ (a_1+a_2)w_2 & a_2w_1 & …… \\ (a_1+a_2+a_3)w_3 & (a_2+a_3)w_2 & a_3w_1 & ……\\ (a_1+a_2+a_3+a_4)w_4 & (a_2+a_3+a_4)w_3 & (a_3+a_4)w_2 \\ …… & …… & ……\\ (a_1+a_2+……+a_n)w_n & (a_2+……+a_n)w_{n-1} & …… & a_nw_1 \\ \end{pmatrix}

从第一列可以想到前缀和,所以先求出前缀和f[i](0<=i<=n)f[i](0<=i<=n)f[i](0<=i<=n)

⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜(f1−f0)w1(f2−f0)w2(f3−f0)w3(f4−f0)w4……(fn−f0)wn……(f2−f1)w1(f3−f1)w2(f4−f1)w3……(fn−f1)wn−1……(f3−f2)w1(f4−f2)w2………………(fn−fn−1)w1⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟((f1−f0)w1……(f2−f0)w2(f2−f1)w1……(f3−f0)w3(f3−f1)w2(f3−f2)w1……(f4−f0)w4(f4−f1)w3(f4−f2)w2………………(fn−f0)wn(fn−f1)wn−1……(fn−fn−1)w1)

\begin{pmatrix} (f_1-f_0)w_1 & ……\\ (f_2-f_0)w_2 & (f_2-f_1)w_1 & …… \\ (f_3-f_0)w_3 & (f_3-f_1)w_2 & (f_3-f_2)w_1 & ……\\ (f_4-f_0)w_4 & (f_4-f_1)w_3 & (f_4-f_2)w_2 \\ …… & …… & ……\\ (f_n-f_0)w_n & (f_n-f_1)w_{n-1} & …… & (f_n-f_{n-1})w_1 \\ \end{pmatrix}

然后将wiwiw_i相同的项合(可以相互消去)并描绘得到下面的东西,为了方便,我还是用矩阵表示

⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜(fn)w1(fn+fn−1−f1)w3(fn+fn−1+fn−2−f1−f2)w3(fn+fn−1+fn−2+fn−3−f1−f2−f3)w4…………(fn+fn−1+……−f1−f2−……fn−1)wn⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟((fn)w1(fn+fn−1−f1)w3(fn+fn−1+fn−2−f1−f2)w3(fn+fn−1+fn−2+fn−3−f1−f2−f3)w4…………(fn+fn−1+……−f1−f2−……fn−1)wn)

\begin{pmatrix} (f_n)w_1 \\ (f_n+f_{n-1}-f_1)w_3\\ (f_n+f_{n-1}+f_{n-2}-f_1-f_2)w_3\\ (f_n+f_{n-1}+f_{n-2}+f_{n-3}-f_1-f_2-f_3)w_4\\ ………… \\ (f_n+f_n-1+……-f_1-f_2-……f_{n-1})w_n \end{pmatrix}

现在敲是会TLE的,复杂度太高 所以再考虑一次fifif_i的前缀和gigig_i, 上面就可以将fifif_i转换成g[n]−g[n−i]−g[i−1]g[n]−g[n−i]−g[i−1]g[n]-g[n-i]-g[i-1], 还有一个问题,由于有减法,所以可能答案出现负数,所以最后需要加模再取模。

#include <cstdio>
#include <cstring>
#include <cmath>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
const ll mo=1e9+7;
const int maxn=3e5+5;
ll a[maxn],w[maxn],f[maxn],g[maxn],ans=0;
int main()
{
    int n;
    scanf("%d",&n);
    g[0]=f[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        f[i]=a[i]+f[i-1];
        g[i]=(f[i]+g[i-1])%mo;
    }
    for(int i=1;i<=n;i++)
        cin>>w[i];
    for(int i=1;i<=n;i++){
        ans=(ans+(g[n]-g[n-i]-g[i-1])*w[i]%mo)%mo;
    }
    cout<<(ans+mo)%mo<<endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Games101--Assignment2

    修改函数rasterize_triangle(const Triangle& t)。 该函数的内部工作流程如下:

    Enterprise_
  • Games101--Assignment2

    修改函数rasterize_triangle(const Triangle& t)。 该函数的内部工作流程如下:

    Enterprise_
  • 第十四届浙江财经大学程序设计竞赛重现赛--A-A Sad Story

    Enterprise_
  • Go语言调度器之创建main goroutine(13)

    上一节我们分析了调度器的初始化,这一节我们来看程序中的第一个goroutine是如何创建的。

    阿波张
  • select2无法输入搜索和宽度问题解决

    这时候select2的搜索框无法输入,一般有两方面的原因 1.检查下modal的div中是否有tabindex=”-1”,这个属性

    botkenni
  • finecms如何批量替换文章中的关键词?

      Finecms批量替换文章关键词要怎么操作呢,比如把关键词A换为B?Finecms是免费开源无商业限制的内容管理系统,个人在维护,但二次开发很灵活,我们可以...

    ytkah
  • 浙大版《C语言程序设计(第3版)》题目集 习题10-4 递归求简单交错幂级数的部分和

    其中题目保证传入的n是正整数,并且输入输出都在双精度范围内。函数fn应返回上述级数的部分和。建议尝试用递归实现。

    C you again 的博客
  • eclipse插件创建本地git仓库

    由于我的eclipse是写书时最新版本,eclipse4.7版本,自带git,无需安装。既然我们本地机器里还没有任何仓库,在eclipse中选择 一个项目,右键...

    马克java社区
  • Github进行fork后如何与原仓库同步

    实在是……有太多人同时在帮忙修订错别字或优化 xiaolai 的 the-craft-of-selfteaching 了。如果你提交的 pull request...

    刘娟娟PRESSone
  • 022-github 从fork的原代码更新repo

    玩过github的人一定会在你自己的账号上fork了一些github开源项目。这些开源项目往往更新比较活跃,你今天fork用到你自己的项目中去了,过几个星期这个...

    上善若水.夏

扫码关注云+社区

领取腾讯云代金券