codeforces 407C Curious Array

codeforces 407C Curious Array

题目传送们

题意：

给出一个长度为\(n\)序列，每次给出三个值\(l\)，\(r\)，\(k\)，表示给区间\([l,r]\)中的每一个数\(a_j(l \leq j \leq r)\)加上\(\tbinom{j-l+k}{k}\)，求\(m\)次操作之后每个位置上的值对\(10^9+7\)取模的结果。
\((1 \leq n,m \leq 10^5 , 1 \leq a_i \leq 10^9 , 1 \leq l_i,r_i \leq n,0 \leq k \leq 100 )\)

题解：

考虑到题目中的\(k\)比较的小，所以我们大致往这个方向入手。我们先从简单的开始考虑，如果\(k=0\)，则相当于在\([l,r]\)区间中每个数都加上1，只需要差分一下，然后修改完之后前缀和一下即可。然后我们继续考虑\(k=1\)的情况，那么我们就是在第一个位置上加1，第二个位置上加2...然后每个位置加的数字都相差1。于是我们很容易就想到将加的操作前缀差分一下，那么转化成了\(k=0\)的情况。根据这个，我们就可以大胆的推断出\(k=x\)的情况下前缀差分一下就可以转化成\(k=x-1\)的情况。经过检验发现确实是这样的。实际上这是因为组合数的公式\(\tbinom{n}{m}=\tbinom{n-1}{m-1}+\tbinom{n-1}{m}\)，这个满足前缀差分的性质，所以可以把这个操作转化成\(k\)阶差分。
然后我们会发现一个情况，以给长度为四的区间加上2的贡献时，如果我们只在一层前缀和之中差分，会出现这样的情况：
先进行差分：0 1 0 0 0 -1 \(\to\) 进行前缀和一次：0 1 1 1 1 0 （到这里都是对的） \(\to\) 再次进行前缀和： 0 1 2 3 4 5 \(\to\) 0 1 3 6 10 15
我们会发现，虽然中间长度为4的区间确实加上了2的贡献，但是最后的一个区间却多加了贡献。所以我们仅在第一层中进行差分是不够的，还需要在之后的几层中进行差分，并且每一层差分减去的组合数刚好是\(C[\)层数\(-1+k][k]\)，这样我们再次进行前缀和之后就可以消除多余的贡献了。总共的复杂度为\(O(nk)\)。

Code:

#pragma GCC optimize (2,"inline","Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
const int N=1e5+500;
const int Md=1e9+7;
const int K=103;
int n,m;
struct mo {
    int l,r,k;
}q[N];
int C[N][K],tmp[N][K],res[N][K],a[N];
/*==================Define Area================*/
int Add(const int &x,const int &y) {return (x+y)>=Md?(x+y-Md):(x+y);}
int Sub(const int &x,const int &y) {return (x-y<0)?(x-y+Md):(x-y);}

void Init() {
    C[0][0]=1;
    for(int i=1;i<N-450;i++) {
        C[i][0]=1;
        for(int j=1;j<=min(i,K-1);j++) {
            C[i][j]=Add(C[i-1][j-1],C[i-1][j]);
        }
    }
}

int main() {
    read(n);read(m);
    for(int i=1;i<=n;i++) read(a[i]);
    Init();
    for(int i=1,l,r,k;i<=m;i++) {
        read(l);read(r);read(k);
        tmp[l][k+1]++;
        for(int j=k+1;j;j--) {
            tmp[r+1][j]=Sub(tmp[r+1][j],C[k-j+1+r-l][k-j+1]);
        }       
    }
    for(int i=101;~i;i--) {
        for(int j=1;j<=n;j++) res[j][i]=Add(res[j][i],res[j][i+1]);
        for(int j=1;j<=n;j++) res[j][i]=Add(res[j][i],res[j-1][i]);
        for(int j=1;j<=n;j++) res[j][i]=Add(res[j][i],tmp[j][i]);
    }
    for(int i=1;i<=n;i++) {
        printf("%d ",Add(res[i][0],a[i]));
    }
    puts("");
    return 0;
}