专栏文章

高阶差分

vvanueber
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5im6n
此快照首次捕获于
2025/12/01 20:54
3 个月前
此快照最后确认于
2025/12/01 20:54
3 个月前
查看原文

一阶差分和多维差分

一阶差分

bi=ai−ai−1b_i = a_i - a_{i-1}，定义 bb 为 aa 的差分数组。
注意到 ∑i=1ibi=ai\sum_{i=1}^{i} b_i = a_i，差分为前缀和的逆运算。
应用
对数组 aa 的修改 ai←ai+v,i∈[l,r]a_i \gets a_i + v, i\in [l,r] 可转化到差分数组 bb 上。
bl←bl+v,br+1←br+1−vb_l \gets b_l +v,b_{r+1}\gets b_{r+1} - v。

多维差分

二维差分的定义类似一维差分。
ai,j=∑i∑jΔai,ja_{i,j} = \sum_i \sum_j \Delta a_{i,j}
由容斥原理 Δai,j=ai,j−ai−1,j−ai,j−1+ai−1,j−1\Delta a_{i,j} = a_{i,j} - a_{i-1,j}-a_{i,j-1} + a_{i-1,j-1}。
可以按维度差分，写起来更简单。

高阶差分

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

P4231 三步必杀

给区间 [l,r][l,r] 加上一个以 ss 为首项，ee 为末项的等差数列。
做两次差分，可以得到结论，一次操作相当于：
Δ2al←Δ2al+s,Δ2al+1←Δ2al+1+s−dΔ2ar+1←Δ2ar+1−d−e,Δ2ar+2←Δ2ar+2+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
这样是正确的，但是操作了 44 次，而且每次的变化系数难以计算，不方便推广，下面是一个技巧。
一阶等差数列的二阶差分数组都为 00。
利用这个性质，在第 kk 维时减去差分的贡献，再升到 k+1k+1 维继续做是一个很好的技巧。
具体地
al←al+s,al+1←s+d,…,ar←ea_l \gets a_l + s,a_{l+1} \gets s+ d,\dots,a_r \gets e
可转化为
Δal←Δal+s,Δal+1←Δal+1+d,…,Δar←ar+d,Δar+1←Δar+1−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
对于 Δal,Δar+1\Delta a_l,\Delta a_{r+1} 可以做特殊的处理，保留在一阶差分内，这样再做二阶差分，最终将一阶差分与二阶差分的结果合并即可。
这样可以避免差分系数的计算，在高阶差分有明显的好处。

CF407C Curious Array

模拟赛题，手玩发现每次加的都是一个 kk 阶等差数列，事实上也是如此。
(nm)=(n−1m−1)+(n−1m)\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}
这是组合数的递推公式，简单展开即可证得加的序列是一个 kk 阶等差数列。
考虑一次操作序列：
+(kk),+(k+1k),+(k+2k),…,+(k+r−lk)+\binom{k}{k},+\binom{k+1}{k},+\binom{k+2}{k},\dots,+\binom{k+r-l}{k}
做一次差分，这里使用组合数公式展开即得：
+(k−1k−1),+(kk−1),…,+(k+r−l−1k−1),−(k+r−lk)+\binom{k-1}{k-1},+\binom{k}{k-1},\dots,+\binom{k+r-l-1}{k-1},-\binom{k+r-l}{k}
不难发现差分一次，等差数列就降了一阶，而且多出一个尾巴。
我们采用小技巧，把这个尾巴留在当前阶差分数组，剩下的继续差分做下去。
所以一次操作等价于 Δk+1ai+1\Delta^{k+1} a_i + 1，再扣去每一阶差分的尾巴。
codeCPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...