青岛网站设计哪家便宜,非响应式网站优点,贵州省交通工程建设质监局网站,新上线的网站怎么做优化传送门:洛谷
前题提要:包含了简单的生成函数思想以及多项式乘法,是一道不可多得的多项式好题.故记录一下.
题意:给定一个长为 n 的序列 a#xff0c;求出其 k 阶差分或前缀和。结果的每一项都需要对 1004535809取模。
对于差分和前缀和我们分开来讨论.
先讨论前缀和部分: …传送门:洛谷
前题提要:包含了简单的生成函数思想以及多项式乘法,是一道不可多得的多项式好题.故记录一下.
题意:给定一个长为 n 的序列 a求出其 k 阶差分或前缀和。结果的每一项都需要对 1004535809取模。
对于差分和前缀和我们分开来讨论.
先讨论前缀和部分:
先列出 A A A序列: ( a 1 , a 2 , . . . , a n ) (a_1,a_2,...,a_n) (a1,a2,...,an),再列出前缀和 S S S序列: ( s 1 , s 2 , . . . , s n ) (s_1,s_2,...,s_n) (s1,s2,...,sn),为了等会的方便起见,我们将这两个序列扩展一下,分别加上一个 a 0 , s 0 a_0,s_0 a0,s0.(并且这两个值规定为0) 存在 s 0 0 , s 1 a 0 a 1 , s n a 0 a 1 . . . a n s_00,s_1a_0a_1,s_na_0a_1...a_n s00,s1a0a1,sna0a1...an 我们将其往多项式那边靠,不难发现,如果存在另一个序列 B B B为 ( 1 , 1 , 1...1 ) (1,1,1...1) (1,1,1...1),那么此时我们的 S A ∗ B SA*B SA∗B,也就是 S S S序列是 A A A与 B B B的卷积系数结果. 所以一阶前缀和 S 1 A 1 ∗ B 1 S1A1*B1 S1A1∗B1,那么二阶 S 2 S 1 ∗ B 1 S2S1*B1 S2S1∗B1,因为多项式卷积满足结合律 k k k阶即为 S k S 1 ∗ B 1 k SkS1*B1^k SkS1∗B1k. 此时如果多项式的科技比较强,直接套一个多项式快速幂就结束了. 但是显然我的科技树比较差,所以来讨论一下低科技的解法 因为我们无法进行多项式快速幂,所以我们考虑使用生成函数的方法将多项式转为一个函数然后在做考虑.那么此时我们的 B B B就是 1 x x 2 . . . x n 1xx^2...x^n 1xx2...xn,求一下和就是 ( 1 − x n ) / ( 1 − x ) (1-x^n)/(1-x) (1−xn)/(1−x),为了方便起见,我们此时不妨选择 x ∈ ( 0 , 1 ) x\in(0,1) x∈(0,1),那么此时我们的 B B B就是 1 / ( 1 − x ) 1/(1-x) 1/(1−x),那么此时 B k ( 1 − x ) − k B^k(1-x)^{-k} Bk(1−x)−k. 考虑使用扩展二项式定理: ( a b ) n a n ∗ ( 1 b a ) n a n ∗ ∑ i 0 ∞ ( n i ) ∗ ( b a ) i (ab)^na^n*(1\frac{b}{a})^na^n*\sum_{i0}^{\infty}{n\choose i}*(\frac{b}{a})^i (ab)nan∗(1ab)nan∗i0∑∞(in)∗(ab)i 那么对于上述式子来说就是 B k ∑ i 0 ∞ ( − k i ) ∗ ( − 1 ) i ∗ x i B^k\sum_{i0}^{\infty}{-k\choose i}*(-1)^i*x^i Bki0∑∞(i−k)∗(−1)i∗xi ( − k i ) ( − k ) ∗ ( − k − 1 ) ∗ ( − k − 2 ) ∗ . . . ∗ ( − k − i 1 ) i ! {-k\choose i}^\frac{(-k)*(-k-1)*(-k-2)*...*(-k-i1)}{i!} (i−k)i!(−k)∗(−k−1)∗(−k−2)∗...∗(−k−i1) ( − 1 ) i ∗ k ∗ ( k 1 ) ∗ ( k 2 ) ∗ . . . ( k i − 1 ) i ! (-1)^i*\frac{k*(k1)*(k2)*...(ki-1)}{i!} (−1)i∗i!k∗(k1)∗(k2)∗...(ki−1) ( − 1 ) i ∗ C k i − 1 i (-1)^i*C_{ki-1}^i (−1)i∗Cki−1i
对于 C k i − 1 i C_{ki-1}^i Cki−1i,显然我们是递推来求和的(注意本题的 k k k很大,只能递推来求和,无法预处理), C k i − 1 i C k i − 2 i − 1 ∗ ( k i − 1 i ) C_{ki-1}^iC_{ki-2}^{i-1}*(\frac{ki-1}{i}) Cki−1iCki−2i−1∗(iki−1).
那么此时我们的k阶前缀和就到此结束了,只要使用 N T T NTT NTT解决一下多项式乘法即可. 下面讲一下这道题的k阶差分部分.其实大体上的解决方案和前缀和是一样的. 同样考虑得出B序列为 ( 1 , − 1 , 0 , 0 , 0...0 ) (1,-1,0,0,0...0) (1,−1,0,0,0...0) [推导方式和上述一样,此处就不在赘述了]. 使用生成函数将 B k B^k Bk序列转化一下就是 ( 1 − x ) k (1-x)^k (1−x)k,使用二项式定理展开就是 ∑ i 0 ∞ C k i ∗ ( − x ) k \sum_{i0}^{\infty}C_k^i*(-x)^k ∑i0∞Cki∗(−x)k,同样递推一下即可.
最后也是拿 N T T NTT NTT做一下多项式乘法即可解决. 下面是具体的代码部分:
#include bits/stdc.h
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
inline void print(__int128 x){if(x0) {putchar(-);x-x;}if(x9) print(x/10);putchar(x%100);
}
#define maxn 1000000
#define int long long
const int mod1004535809;
const double eps1e-8;
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int f[maxn],g1[maxn],g2[maxn];
inline ll get_read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) x(x*10%modch-0)%mod;return x*w;
}
int qpow(int a,int b) {int ans1;while(b) {if(b1) ansans*a%mod;b1;aa*a%mod;}return ans;
}
int rev[maxn];
void NTT(int *a,int n,int inv) {for(int i0;in;i) if(irev[i]) swap(a[i],a[rev[i]]);for(int len1;len(n1);len1) {int gnqpow(inv1?3:qpow(3,mod-2),(mod-1)/(len1));for(int i0;in;i(len1)) {int g01;for(int j0;jlen-1;j) {int xa[ij],ya[ijlen]*g0%mod;a[ij](xy)%mod;a[ijlen]((x-y)%modmod)%mod;g0g0*gn%mod;}}}
}
signed main() {int nread();int kget_read();int tread();for(int i1;in;i) {f[i]read();}int limit1,len0;while(limit2*n) limit1,len;for(int i0;ilimit;i) rev[i](rev[i1]1)|((i1)(len-1));g1[0]1;for(int i1;in;i) {g1[i]g1[i-1]*(ki-1)%mod*qpow(i,mod-2)%mod;}g2[0]1;for(int i1;in;i) {g2[i](g2[i-1]*(k-i1)%mod*qpow(i,mod-2)%mod*-1mod)%mod;}if(t0) {NTT(f,limit,1);NTT(g1,limit,1);for(int i0;ilimit;i) {f[i]f[i]*g1[i]%mod;}NTT(f,limit,-1);int invqpow(limit,mod-2);for(int i0;ilimit;i) {f[i]f[i]*inv%mod;}}else {NTT(f,limit,1);NTT(g2,limit,1);for(int i0;ilimit;i) {f[i]f[i]*g2[i]%mod;}NTT(f,limit,-1);int invqpow(limit,mod-2);for(int i0;ilimit;i) {f[i]f[i]*inv%mod;}}for(int i1;in;i) {coutf[i] ;}return 0;
}
