洛谷P5488 差分与前缀和题解

题意：

给定一个长为 $n$ 的序列 $a$，求出其 $k$ 阶差分或前缀和。

结果的每一项都需要对 $1004535809$ 取模。

输入格式：

第一行三个整数 $n,k,t$，若 $t=0$ 表示求前缀和，$t=1$ 表示求差分。

第二行 $n$ 个整数，表示序列 $a$。

输出格式：

输出一行 $n$ 个整数，表示 $a$ 的 $k$ 阶差分或前缀和。

数据范围：

$1 \le n \le 10^5,~0 \le a_i \le 10^9,~1\le k \le 10^{2333}, k \not \equiv 0 \pmod{1004535809}$

$\mathcal{Part}\ 1$

设 $F(x) = \sum_{n \ge 0} a_nx^n$ 是序列 $a$ 的生成函数。

众所周知，它的前缀和就是 $F(x)\times G(x)$ ，其中 $G(x)=\sum_{n\ge 0}x^n$ ，因为

$\begin{aligned} F(x)\times G(x) &= \sum_{n \ge 0} x^n \sum_{i=0}^n a_ib_{n-i} \\[6pt]&= \sum_{n \ge 0} x^n \sum_{i=0}^n a_i \end{aligned}$

可以发现后面的 $\sum_{i=0}^n a_i$ 就是我们要的前缀和。

因为 $G(x)=\frac{1}{(1-x)}$ ，并且卷积是有结合律的，所以做 $k$ 次前缀和就是

$\begin{aligned} F(x)\times G^k(x) &= F(x) \times \frac{1}{(1-x)^k} \\[6pt] &= F(x) \times \sum_{n \ge 0} (-1)^k\binom{-k}{n}x^n \\[6pt] &= F(x) \times \sum_{n \ge 0} \binom{n+k-1}{n}x^n \end{aligned}$

又因为

$\binom{n+k-1}{n} = \binom{n+k-1}{n - 1} \times \frac{k}{n}$

所以这个东西是可以递推的。那么只需要一个 NTT 就可以搞定了

$\mathcal{Part}\ 2$

差分也是一样的，不过我也不晓得差分的 $G(x)$ 是啥，干脆推一下吧

定义 $a_{-1}=0$ ，则

$\sum_{n \ge 0} x^n \sum_{i=0}^n a_ib_{n-i} = \sum_{n \ge 0} (a_n - a_{n-1})x^n$

可以发现，$b_0=1,\,b_1=1,\,b_{i}=0(i > 2)$ ，所以差分的 $G(x) = 1-x$ ，

那做 $k$ 次就是 $G^k(x) = (1-x)^k$ ，如下

$\begin{aligned} F(x)\times G^k(x) &= F(x) \times (1-x)^k \\[6pt] &= F(x) \times \sum_{n \ge 0} (-1)^k\binom{k}{n}x^n \end{aligned}$

这里的递推式是这样的

$\binom{k}{n}=\binom{k}{n-1} \times \frac{k-n+1}{n}$

那么这道题就做完了

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int P = 1004535809;
const int G = 3, Gi = 334845270;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(4e5 + 15)) // 一定要开 len 的两倍！！！

int qpow(int a, int b)
{
    int r = 1;
    for(; b; b >>= 1, a = a * a % P)
        if(b & 1) r = r * a % P;
    return r;
}
char K[N];
int l, limit, r[N], a[N], b[N];
void init(int len)
{
    for(limit = 1, l = 0; limit <= len; limit *= 2, ++l);
    for(int i = 0; i < limit; i++)
        r[i] = (r[i >> 1] >> 1) | ((i & 1) << (l - 1));
}
void NTT(int *A, int type)
{
    for(int i = 0; i < limit; i++) if(i < r[i]) swap(A[i], A[r[i]]);
    for(int mid = 1; mid < limit; mid *= 2)
    {
        int Wn = qpow((type == 1 ? G : Gi), (P - 1) / (mid * 2));
        for(int j = 0; j < limit; j += (mid * 2))
        {
            int w = 1;
            for(int k = 0; k < mid; k++, w = (w * Wn) % P)
            {
                int x = A[j + k], y = w * A[j + k + mid] % P;
                A[j + k] = (x + y) % P; A[j + k + mid] = (x - y + P) % P;
            }
        }
    }
    if(type != 1) {
        const int Inv = qpow(limit, P - 2);
        for(int i = 0; i < limit; i++) A[i] = A[i] * Inv % P;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, type, k = 0; cin >> n >> (K + 1) >> type; b[0] = 1; --n;
    for(int i = 1; K[i]; i++) k = (k * 10 + (K[i] - '0')) % P;
    for(int i = 0; i <= n; i++) cin >> a[i], a[i] = (a[i] + P) % P;
    if(type == 0) { 
        for(int i = 1; i <= n + 1; i++)
            b[i] = b[i - 1] * (k + i - 1) % P * qpow(i, P - 2) % P;
    }else {
        for(int i = 1; i <= n + 1; i++)
            b[i] = (P - b[i - 1] * (k - i + 1 + P) % P * qpow(i, P - 2) % P) % P;
    }
    init(n + n + 1); NTT(a, 1); NTT(b, 1);
    for(int i = 0; i < limit; i++) a[i] = a[i] * b[i] % P;
    NTT(a, -1); for(int i = 0; i <= n; i++) cout << a[i] << " \n"[i == n];
    return 0;
}