题意:

给你一个序列,每次给出一个区间l,r和一个数字k,有i\in [l,r] ,a[i] += \binom{i-l+k}{k} ,然后让你输出最后的序列…..

数据范围(原题):

n,m \leqslant 100000,k\leqslant 100

分析:

我们发现我们每次操作就是给序列的一段区间加上杨辉三角一列…
假设我们有杨辉三角….(只需要处理100位,因为k\leqslant 100)
1
1 \ 1
1 \ 2 \ 1
1 \ 3 \ 3 \ 1
1 \ 4 \ 6 \ 4 \ 1
1 \ 5 \ 10 \ 10 \ 5 \ 1
1 \ 6 \ 15 \ 20 \ 15 \ 6 \ 1
我们每次操作的本质就是k=1我们就加上第二列就是1,2,3,4,5…
然后我们发现列和列之间的关系是原序列和前缀和的关系,比如第二层求一个前缀和就可以变成第三层…..最好自己打表找规律
那么对于一次操作,比如我们修改l,r 时,我们在l处打一个tag,在r+1处打一个抵消标记,然后求前缀和
举例子:现在有l=2,r=5

原序列:

0,0,0,0,0,0,0,0,0,0,0,0

tag :

0,1,0,0,0,-1,0,0,0,0,0,0

求一次前缀和,变成

0,1,1,1,1,0,0,0,0,0,0,0
然后我们得到了k=0的答案,然后求k=1

tag:

0,0,0,0,0,-4,0,0,0,0,0,0

求一次前缀和,变成

0,1,2,3,4,0,0,0,0,0,0,0
然后我们得到了k=1的答案,然后以此类推…..
我们发现除了第一次要在l处打+1tag,其余的我们在只要在r+1处打上消除标记就好了…..
第i次我们打的消除标记是\binom{r-l+1}{i}
然后我们得到了O(nk^2)的做法,我们对于每一种k,O(n)打标记,然后做k次前缀和…..
但是我们发现这样过不了,会TLE,怎么优化…
我们在这里提出一种做法,我们倒着做,先让k=100,然后减小k,逐层打入标记,然后这样就只要枚举O(nk)就好了,详细自己看代码(挺高妙的)

好题自己多想想

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
const LL N=1e5+1000;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m;
LL ans[N],C[N][110],tag[N],yuan[N];
inline void init()
{
    C[0][0]=1;
    for(int i=1;i<=n+210;i++){C[i][0]=1; for(int j=1;j<=min(i,100);j++)C[i][j]=((C[i-1][j-1]+C[i-1][j])%mod+mod)%mod;}
    for(int i=1;i<=101;i++) for(int j=1;j<=n;j++) C[j][i]=C[j+i-1][i];
}
void add(LL &a,LL b){a+=b; while(a>=mod) a-=mod;}
struct Edge{int l,r,k;}len[N];
int main()
{
    read(n),read(m);init();
    for(int i=1;i<=n;i++) read(yuan[i]);
    for(int i=1;i<=m;i++) read(len[i].l),read(len[i].r),read(len[i].k);
    for(int i=102;i>=0;i--)
    {
        memset(tag,0,sizeof(tag));
        for(int j=1;j<=m;j++)
        {
            if(len[j].k+1>=i) tag[len[j].r+1]=(tag[len[j].r+1]+mod-C[len[j].r-len[j].l+1][len[j].k-i])%mod;
            if(len[j].k==i) (tag[len[j].l]+=1)%=mod;
        }
        for(int j=1;j<=n;j++) add(ans[j],((ans[j-1]+tag[j])%mod+mod)%mod);
    }
    for(int i=1;i<=n;i++) printf("%lld ",((ans[i]+yuan[i])%mod+mod)%mod);puts("");
    return 0;
}

2 Comments

发表评论

电子邮件地址不会被公开。 必填项已用*标注