题解 P5488 【差分与前缀和】
Nemlit
2019-11-30 22:53:48
~~Karry怒骂此题是多项式板子？？？~~
你要是看出这道题是多项式了也就不麻烦了
$ps:$本题解均用0为数组下标，以方便多项式运算，所以公式可能和其他题解略有不同
首先先考虑前缀和：
考虑前缀和的定义式：$c_k=\sum_{i=0}^ka_i$
把他变下型，我们有：$c_k=\sum_{i+j=k}a_i*b_j$（其中$b_j=1$）
不难发现这是一个等价的形式，于是我们可以利用$NTT$进行优化，于是现在问题就转化成求$b_i$
对于$k=1$的情况，那$b$是一个系数全部为1的多项式，由于卷积满足结合律，所以我们可以求出b这个多项式的k次方后与a数组卷起来
考虑每一位的贡献，用手玩一下，会发现这其实是一个斜着的杨辉三角，可以用数学归纳法证明，打出来的表如下：
```
1 1 1 1 1 1
1 2 3 4 5 6
1 3 6 10 15 21
1 4 10 20 35 56
1 5 15 35 70 126
1 6 21 56 126 252
```
于是我们可以得出递推式：对于第i位对k维前缀和的贡献为$\dbinom{k+i-1}{i}$
由于k很大，但是我们需要求得项不多，我们可以用递推求出上式，读入k的时候取个膜就行了
然后考虑差分（其实没有本质区别）：
考虑差分定义式：$c_k=a_k-a_{k-1}$
还是转化一下：$c_k=\sum_{i+j=k}a_i*b_j$（$b_0=1, b_1=-1$）
还是可以用卷积优化，还是打一个表，对于第i位对k维前缀和的贡献为$\dbinom{k}{i}*(-1)^i$，用递推求解即可
## $Code:$
```
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define re register
#define int long long
#define mod 1004535809
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, x %= mod, c = getchar();
return x * f;
}
#define rep(i , a , b) for(int i = (a) , i##Limit = (b) ; i <= i##Limit ; ++ i)
#define maxn 500005
int n, k, opt, a[maxn], b[maxn], inv, lim, r[maxn];
il int qpow(int a, int b) {
int r = 1;
while(b) {
if(b & 1) r = (r * a) % mod;
a = (a * a) % mod, b >>= 1;
}
return r;
}
il int mul(int a, int b) { return a * b % mod; }
il void NTT(int*a, int f) {
rep(i, 0, (1 << lim) - 1) if(r[i] > i) swap(a[i], a[r[i]]);
for(re int mid = 1; mid < (1 << lim); mid <<= 1) {
int base = qpow(f == 1 ? 3 : inv, (mod - 1) / (mid << 1));
for(re int p = mid * 2, j = 0; j < (1 << lim); j += p) {
int w = 1;
for(re int k = 0; k < mid; ++ k, w = mul(w, base)) {
int x = a[j + k], y = mul(w, a[j + k + mid]);
a[j + k] = (x + y) % mod, a[j + k + mid] = (x - y + mod) % mod;
}
}
}
}
signed main() {
n = read(), k = read(), opt = read(), inv = qpow(3, mod - 2), b[0] = 1;
rep(i, 0, n - 1) a[i] = read();
if(opt == 0) rep(i, 1, n - 1) b[i] = mul(mul(b[i - 1], qpow(i, mod - 2)), k + i - 1);
else rep(i, 1, n - 1) b[i] = mul(mul(b[i - 1], qpow(i, mod - 2)), k - i + 1);
if(opt == 1) for(re int i = 1; i < n; i += 2) b[i] = -b[i];
rep(i, 1, n - 1) b[i] = (b[i] + mod) % mod;
while((1ll << lim) < n * 2) ++ lim;
rep(i, 0, (1 << lim) - 1) r[i] = (r[i >> 1] >> 1) | ((i & 1) << (lim - 1));
NTT(a, 1), NTT(b, 1);
rep(i, 0, (1 << lim) - 1) a[i] = mul(a[i], b[i]);
NTT(a, -1), inv = qpow((1 << lim), mod - 2);
rep(i, 0, n - 1) printf("%lld ", (mul(a[i], inv) + mod) % mod);
return 0;
}
```