题解：P17730 [SCP-J 2026] 数组 / array

ZHR100102 · 2026-10-18 15:12:43 · 题解

谴责这题出题人，太没素质了，怎么给 J 组小朋友考高阶差分模板题。

学过一点组合数学的应该知道高阶前缀和公式：

A_{k, i} = \sum_{j\le i} \binom{i - j+k-1}{k-1}A_{0, j}

组合意义可以考虑插板法，在 k 轮内，从 j 走到 i，且只能向后走的方案数为 \binom{i-j+k-1}{k-1}。

相应地，还有高阶差分公式，但是组合意义不好推，我们引入两个算子：

恒等算子 I，表示序列不变。
移位算子 E，表示序列向后移动一位，也就是对 1\le i \le n，同时执行 a_i\gets a_{i-1}。

因此，我们可以得到前缀和算子 P = (I+E) 和差分算子 P^{-1} = (I - E)，进而得到高阶差分公式：

P^{-k} = (I-E)^{k} = \sum_{0\le i\le k} \binom{k}{i}(-1)^i E^i

换为序列上，高阶差分公式即为：

A_{-k, i} = \sum_{0\le j \le k}\binom{k}{j}(-1)^j A_{0, i-j}

注意，该公式中下标越界的值全部视为 0。

因此这题就做完了。考虑只维护 A_0，将所有修改操作通过高阶差分还原至 A_0，将所有查询操作通过高阶前缀和公式进行计算：

对 x 阶前缀和进行区间加，等价于对 x-1 阶前缀和，在 l 处 +k，r+1 处 -k，进行单点修。注意对 x=0 进行特判。
对 x 阶前缀和进行区间查，等价于对 x+1 阶前缀和，查询 r 和 l-1 处的值。

时间复杂度 O(n(p+q)+n^2)，二项式系数可以通过 Pascal 公式递推得到。

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb(x) emplace_back(x)
#define pb(x) push_back(x)
#define ls(x) (tr[x].ls)
#define rs(x) (tr[x].rs)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ldb;
typedef __int128 i128;
using pi = pair<int, int>;
const int N = 605, mod = 1e9 + 7;
ll n, q1, q2, A[N];
ll binom[N][N];

void init() {
    binom[0][0] = 1;
    for(int i = 1; i < N; i++) {
        binom[i][0] = 1;
        for(int j = 1; j < N; j++) {
            binom[i][j] = (binom[i - 1][j] + binom[i - 1][j - 1]) % mod;
        }
    }
}

void alter(int x, int p, ll k) {
    for(int i = p; i <= n; i++) {
        A[i] = (A[i] + k * binom[x][i - p] % mod * (((i - p) & 1) ? (mod - 1) : 1) % mod) % mod;
    }
}

void solve1() {
    ll x, l, r, k; cin >> x >> l >> r >> k;
    k = (k % mod + mod) % mod;
    if(x == 0) {
        for(int i = l; i <= r; i++) {
            A[i] = (A[i] + k) % mod;
        }
    }
    else {
        alter(x - 1, l, k);
        alter(x - 1, r + 1, mod - k);
    }
}

ll getval(int x, int p) {
    ll res = 0;
    for(int i = 1; i <= p; i++) {
        res = (res + A[i] * binom[x - 1 + p - i][x - 1] % mod) % mod;
    }
    return res;
}

void solve2() {
    ll x, l, r; cin >> x >> l >> r;
    ll res = getval(x + 1, r) - getval(x + 1, l - 1);
    res = (res % mod + mod) % mod;
    cout << res << "\n";
}

int main()
{
    //freopen("sample.in", "r", stdin);
    //freopen("sample.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    cin >> n >> q1 >> q2;
    for(int i = 1; i <= n; i++) {
        cin >> A[i];
        A[i] = (A[i] % mod + mod) % mod;
    }
    for(int i = 1; i <= q1 + q2; i++) {
        int opt; cin >> opt;
        if(opt == 1) solve1();
        else solve2();
    }
    return 0;
}