题解：CF407C Curious Array

· · 题解

一阶差分和多维差分

一阶差分

注意到 $\sum_{i=1}^{i} b_i = a_i$，差分为前缀和的逆运算。 ::::info[应用]{open} 对数组 $a$ 的修改 $a_i \gets a_i + v, i\in [l,r]$ 可转化到差分数组 $b$ 上。 $b_l \gets b_l +v,b_{r+1}\gets b_{r+1} - v$。 :::: ## 多维差分 二维差分的定义类似一维差分。 $a_{i,j} = \sum_i \sum_j \Delta a_{i,j}

由容斥原理 \Delta a_{i,j} = a_{i,j} - a_{i-1,j}-a_{i,j-1} + a_{i-1,j-1}。

可以按维度差分，写起来更简单。

高阶差分

可以记 \Delta^{k} a 为数组 a 的 k 阶差分。

P4231 三步必杀

给区间 [l,r] 加上一个以 s 为首项，e 为末项的等差数列。

做两次差分，可以得到结论，一次操作相当于：

\Delta^2 a_l \gets \Delta^2 a_l + s,\Delta^2 a_{l+1} \gets \Delta^2 a_{l+1} + s - d\\ \Delta^2 a_{r+1} \gets \Delta^2 a_{r+1} -d - e,\Delta^2 a_{r+2} \gets \Delta^2 a_{r+2} + e

这样是正确的，但是操作了 4 次，而且每次的变化系数难以计算，不方便推广，下面是一个技巧。

一阶等差数列的二阶差分数组都为 0。

利用这个性质，在第 k 维时减去差分的贡献，再升到 k+1 维继续做是一个很好的技巧。

具体地

a_l \gets a_l + s,a_{l+1} \gets s+ d,\dots,a_r \gets e

可转化为

\Delta a_l \gets \Delta a_l + s,\Delta a_{l+1} \gets \Delta a_{l+1} + d,\dots,\Delta a_{r} \gets a_{r} + d,\Delta a_{r+1} \gets \Delta a_{r+1} - e

对于 \Delta a_l,\Delta a_{r+1} 可以做特殊的处理，保留在一阶差分内，这样再做二阶差分，最终将一阶差分与二阶差分的结果合并即可。

这样可以避免差分系数的计算，在高阶差分有明显的好处。

CF407C Curious Array

模拟赛题，手玩发现每次加的都是一个 k 阶等差数列，事实上也是如此。

\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}

这是组合数的递推公式，简单展开即可证得加的序列是一个 k 阶等差数列。

考虑一次操作序列：

+\binom{k}{k},+\binom{k+1}{k},+\binom{k+2}{k},\dots,+\binom{k+r-l}{k}

做一次差分，这里使用组合数公式展开即得：

+\binom{k-1}{k-1},+\binom{k}{k-1},\dots,+\binom{k+r-l-1}{k-1},-\binom{k+r-l}{k}

不难发现差分一次，等差数列就降了一阶，而且多出一个尾巴。

我们采用小技巧，把这个尾巴留在当前阶差分数组，剩下的继续差分做下去。

所以一次操作等价于 \Delta^{k+1} a_i + 1，再扣去每一阶差分的尾巴。

:::info[code]

#include <bits/stdc++.h>
#define int long long
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define db double
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f,mod=1e9+7;
const long long INFL=0x3f3f3f3f3f3f3f3f;
const double eps=1e-8;
il int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
il void chkmax(int &x,int y){x=(x<y)?y:x;}
il void chkmin(int &x,int y){x=(x>y)?y:x;}

const int N=1e5+105,M=105;
int n,m,a[N],diff[M][N];
void add(int &x,int y){
    if((x+=y)>=mod) x-=mod;
}
void sub(int &x,int y){
    if((x-=y)<0) x+=mod;
}
int inv[N],frac[N];
il ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int C(int n,int m){
    return 1ll*frac[n]*inv[m]%mod*inv[n-m]%mod;
}
signed main(){
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    cin>>n>>m;
    frac[0]=inv[0]=1;
    rep(i,1,n+100) frac[i]=1ll*frac[i-1]*i%mod;
    rep(i,1,n+100) inv[i]=qpow(frac[i],mod-2);
    rep(i,1,n) a[i]=read();
    rep(i,1,m){
        int l=read(),r=read(),k=read();
        add(diff[k+1][l],1);
        rep(j,1,k+1){
            sub(diff[j][r+1],C(k+r-l-j+1,r-l));
        }
    }
    per(j,101,1){
        rep(i,1,n){
            add(diff[j][i],diff[j][i-1]);
        }
        rep(i,1,n){
            add(diff[j-1][i],diff[j][i]);
        }
    }
    rep(i,1,n){
        cout<<(a[i]+diff[0][i])%mod<<" ";
    }
    puts("");
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}

::::