洛谷noip 模拟赛 day1 T3

T7983 大芳的逆行板载

题目背景

大芳有一个不太好的习惯：在车里养青蛙。青蛙在一个n厘米（11n毫米s）的Van♂杆子上跳来跳去。她时常盯着青蛙看，以至于突然逆行不得不开始躲交叉弹。有一天他突发奇想，在杆子上每1厘米为一个单位，瞎涂上了墨水，并且使用mOgic，使青蛙跳过之处墨水浓度增加x。当然，他还会闲着无聊滴几滴墨水再涂♂抹均匀。

他现在无时无刻都想知道，第l厘米到第r厘米墨水的浓度是多少？

哦不!等等，他现在找到了一个计算器，可以输入几个数字与x，计算他们的x次幂和，所以。。。他想知道的是第l厘米到第r厘米墨水的浓度的x次幂和是多少？

题目描述

大芳有3种~~舰长技能~~骚操作

续：把青蛙放到第l厘米处，戳青蛙使其跳至r。效果：第l厘米至第r厘米墨水浓度增加x
抚♂摸：擦干杆子某一部分，重新滴加墨水并抹匀。效果：使第l厘米至第r厘米墨水浓度都变成x

最后一种是：

压线逆行，将车流看做⑨弹幕找安定点，掏出计算器，大喊板载后计算：

第l厘米至第r厘米墨水浓度的x次幂和是几何？记得答案要

模100000000710000000071000000007

输入输出格式

输入格式：

第一行nnn和mmm，表示杆子长n厘米，大芳要进行m次骚操作。

第二行nnn个数字，表示初始墨水浓度。第i个数字为第i厘米墨水浓度

接下来每行4个数字，依次为：操作编号（1、2或3），lll,rrr,xxx

输出格式：

每次进行3操作，输出一行表示答案

记得膜模1000000007

输入输出样例

输入样例#1：

5 5

19844 14611 26475 4488 6967

2 1 3 15627

2 1 2 30113

2 3 5 14686

2 5 5 32623

3 1 2 8

输出样例#1：

466266421

说明

kkk表示询问的幂的大小，也就是操作3对应的xxx。

对于20%的数据，满足n,m≤1000n,m\leq 1000n,m≤1000

对于另外20%的数据，满足k≤1k\leq 1k≤1

对于另外20%的数据，满足k≤2k\leq 2k≤2

对于另外20%的数据，满足n,m≤50000n,m\leq 50000n,m≤50000

对于100%的数据，满足n,m≤100000,0≤k≤10n,m\leq 100000,0\leq k \leq 10n,m≤100000,0≤k≤10

操作1，2对应的x≤109+7x\le 10^9+7x≤109+7

比赛挂了.......闲着没事放下T2 来艹这个 T3

因为想到了二项式定理 (x+c)^n=sigma i=0..n (c^i)*C(n,i)*(x^(n-i))

然后就觉得可能可以写了...

果然代码能力不足写挂了赛后调了一个多小时发现时标记之间的关系弄错了............惨啊

——————————————————————————————————————————

这道题呢涉及到区间加区间覆盖区间幂求和

区间覆盖其实很好弄

主要在于区间加但是他求的幂只有（1——10）所以我们可以暴力维护一波（1——10）的幂 -用二项式定理

这个不懂的百度学学咯复杂度也就只有 100logn 能接受

当然推的时候注意先推幂的次数比较大的其他都是正常的线段树操作了

当然别忘了覆盖标记遇到加法标记要把加法标记清零啊

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define LL long long

using namespace std;

const int M=<<,mod=;

LL read(){

    LL ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

LL C[][],c[],q[],num[M],w;

int h,n,m,L,R;

struct node{

    LL f,tag;

    LL m[];

}tr[M];

void calc_f(int x,int l,int r,LL v){

    LL sz=r-l+;

    tr[x].m[]=sz*v%mod;

    for(int i=;i<=;i++) tr[x].m[i]=(tr[x].m[i-]*v)%mod;

}

void push(int x,int k,LL v){

    LL sum=;

    for(int i=;i<=k;i++) sum=sum*v%mod,tr[x].m[k]=(tr[x].m[k]+sum*C[k][i]%mod*tr[x].m[k-i]%mod)%mod;

}

void calc_tag(int x,LL v){

    for(int i=;i>=;i--)

    push(x,i,v);

}

void up(int x){

    int l=x<<,r=x<<^;

    for(int i=;i<=;i++) tr[x].m[i]=(tr[l].m[i]+tr[r].m[i])%mod;

}

void down(int x,int l,int r){

    int ll=x<<,rr=x<<^;

    LL mid=(l+r)>>;

    if(tr[x].f!=-){

        tr[ll].f=tr[x].f; tr[rr].f=tr[x].f;

        calc_f(ll,l,mid,tr[x].f);

        calc_f(rr,mid+,r,tr[x].f);

        tr[x].f=-;    tr[ll].tag=tr[rr].tag=;

    }

    if(tr[x].tag){

        if(l==r) return ;

        calc_tag(ll,tr[x].tag);

        calc_tag(rr,tr[x].tag);

        tr[x<<].tag+=tr[x].tag; tr[x<<^].tag+=tr[x].tag; tr[x].tag=;

    }

}

void modify_tag(int x,int l,int r){

    if(L<=l&&r<=R){

        tr[x].tag+=w;

        if(l==r){

            tr[x].m[]+=w;

            for(int i=;i<=;i++) tr[x].m[i]=tr[x].m[i-]*tr[x].m[]%mod;

        }

        else calc_tag(x,w);

        return ;

    }

    down(x,l,r);

    int mid=(l+r)>>;

    if(L<=mid) modify_tag(x<<,l,mid);

    if(R>mid) modify_tag(x<<^,mid+,r);

    up(x);

}

void modify_f(int x,int l,int r){

    if(L<=l&&r<=R){

        tr[x].f=w;

        tr[x].tag=;

        calc_f(x,l,r,w);

        return ;

    }

    down(x,l,r);

    int mid=(l+r)>>;

    if(L<=mid) modify_f(x<<,l,mid);

    if(R>mid) modify_f(x<<^,mid+,r);

    up(x);

}

LL query(int x,int l,int r,int k){

    if(L<=l&&r<=R) return tr[x].m[k];

    down(x,l,r);

    LL mid=(l+r)>>;

    LL sum=;

    if(L<=mid) sum=sum+query(x<<,l,mid,k);

    if(R>mid) sum=sum+query(x<<^,mid+,r,k);

    return sum%mod;

}

void build(int x,int l,int r){

    tr[x].f=-;

    if(l==r){

        tr[x].m[]=;

        tr[x].m[]=num[l];

        for(int i=;i<=;i++) tr[x].m[i]=(tr[x].m[i-]*tr[x].m[])%mod;

        return ;

    }

    int mid=(l+r)>>;

    build(x<<,l,mid);

    build(x<<^,mid+,r);

    up(x);

}

void prepare(){

    q[]=; q[]=;

    for(int i=;i<=;i++) q[i]=q[i-]*i;

    for(int i=;i<=;i++)

     for(int j=;j<=i;j++)

      C[i][j]=q[i]/(q[j]*q[i-j]);

}

int main()

{

    prepare();

    n=read(); m=read();

    for(int i=;i<=n;i++) num[i]=read();

    build(,,n);

    for(int i=;i<=m;i++){

        h=read();

        if(h==){

            L=read(); R=read(); w=read();

            modify_tag(,,n);

        }

        else if(h==){

            L=read(); R=read(); w=read();

            modify_f(,,n);

        }

        else{

            L=read(); R=read();

            int k=read();

            printf("%lld\n",query(,,n,k));

        }//printf("[%lld]\n",tr[1].m[1]);

    }

    return ;

}

巴特西

洛谷noip 模拟赛 day1 T3

题目背景

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章