中科院的难题题解

一、题目：

二、思路：

首先这道题目描述有几处错误，应该要输入原数列。而且将【问题描述】的第三行(a_n)改为(a_i)。

然后言归正传。

这道题感觉很像差分模型，但会发现每次区间加的不是一个常数。

于是引入高阶差分。

我不太喜欢用题目中的组合数形式，我们转回常用式(C_n^m)。

原本要加的数列：

(C_k^k,C^k_{k+1},...,C^k_{r-l+k}).

可以写成

(C_k^0,C_{k+1}^1...C_{r-l+k}^{r-l})

一次差分：

第一项应该是(C_k^0=C_{k-1}^0)

第二项由公式：(C_k^0+C_k^1=C_{k+1}^1)得：(C_{k+1}^1-C_{k}^0=C_{k}^1)

以此类推，一次差分后的数列为：(C_{k-1}^0,C_k^1,C_{k+1}^2...C_{r-l+k-1}^{r-l})

二次差分：

特别地，第一项(C_{k-1}^0)我们写成(C_{k-2}^0)
二次差分后的数列为：

[C_{k-2}^0,C_{k-1}^1,C_{k}^2...C_{r-l+k-2}^{r-l} ]

j次差分：

[C_{k-j}^0,C_{k-j+1}^1,C_{k-j+2}^2,...C_{r-l+k-j}^{r-l} ]

转化一下：(C_{k-j}^{k-j},C_{k-j+1}^{k-j},C_{k-j+2}^{k-j}...C_{r-l+k-j}^{k-j})

那么我们取(j=k)，原式变成：

[1,1,1...1 ]

再差分一遍，原式变成：

[1,0,0...0 ]

类比一阶差分。一阶差分时，我们在l加一，在r+1减一，目的是为了消除差分序列的前缀和的变化对后面的影响。想一想，对吧？

那么对于本道题来说，l处加一，r处不一定减一。因为对于([l,r])来说，一阶差分的前缀和数组(sum[lsim r])都只增加了一，而对于高阶差分来说，倒数第一层和一阶差分一样，它的前缀和数组——也就是倒数第二层差分数组——(sum'[lsim r])都增加了一。那么如果还是在(sum'[r+1])减一，推广到倒数第三层，就不能消除这种变化对后面的影响。所以，一般地，我们要在第j层差分数组的r+1项减去l到r的和。

即我们要求(C_{k-j}^{k-j}+C_{k-j+1}^{k-j}+C_{k-j+2}^{k-j}+...+C_{r-l+k-j}^{k-j})

它等于(C_{k-j+r-l+1}^{k-j+1})

证明如下：

完结撒花。

三、代码：

这不是我本人写的代码，所以可能有点丑，大家将就着看。

#include<iostream>
#include<cstdio>

#define FILE "kotori"

#define FILEIN(s) freopen(s".in","r",stdin)
#define FILEOUT(s) freopen(s".out","w",stdout)

#define LL long long

using namespace std;
inline LL read(void){
    LL x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return f*x;
}

const int maxn=100010,maxk=105,mod=1e9+7;

int n,m,a[maxn];

int fac[maxn<<1],inv[maxn<<1],s[105][maxn];

inline int mul(int a,int b){return 1LL*a*b%mod;}

inline int pow(int a,int b){
    int ret=1;
    for(;b;b>>=1){
        if(b&1)ret=mul(ret,a);
        a=mul(a,a);
    }
    return ret;
}

inline int add(int a,int b){return (a+b)%mod;}
inline int sub(int a,int b){return a-b<0?(a-b+mod):(a-b);}
inline int C(int a,int b){
    return mul(fac[a],mul(inv[b],inv[a-b]));
}

int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
    n=read();m=read();
    for(register int i=1;i<=n;++i)a[i]=read();
    int N=200000;fac[0]=1;
    for(register int i=1;i<=N;++i)fac[i]=mul(fac[i-1],i);
    inv[N]=pow(fac[N],mod-2);
    for(register int i=N-1;i>=0;--i)inv[i]=mul(inv[i+1],i+1);
    for(register int i=1;i<=m;++i){
        int l=read(),r=read(),K=read();
        s[K+1][l]=add(s[K+1][l],1);
        for(register int j=1;j<=K+1;++j){
            s[j][r+1]=sub(s[j][r+1],C(K-j+r-l+1,K-j+1));
        }
    }
    for(register int k=100;k>=0;--k){
        int cnt=0;
        for(register int i=1;i<=n;++i){
            cnt=add(cnt,s[k+1][i]);
            s[k][i]=add(s[k][i],cnt);
        }
    }
    for(register int i=1;i<=n;++i)printf("%d ",add(a[i],s[0][i]));
    return 0;
}

中科院的难题 题解