当前位置: 首页 > news >正文

P5488 差分与前缀和

传送门:洛谷

前题提要:包含了简单的生成函数思想以及多项式乘法,是一道不可多得的多项式好题.故记录一下.

题意:给定一个长为 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_0=0,s_1=a_0+a_1,s_n=a_0+a_1+...+a_n s0=0,s1=a0+a1,sn=a0+a1+...+an
我们将其往多项式那边靠,不难发现,如果存在另一个序列 B B B ( 1 , 1 , 1...1 ) (1,1,1...1) (1,1,1...1),那么此时我们的 S = A ∗ B S=A*B S=AB,也就是 S S S序列是 A A A B B B的卷积系数结果.
所以一阶前缀和 S 1 = A 1 ∗ B 1 S1=A1*B1 S1=A1B1,那么二阶 S 2 = S 1 ∗ B 1 S2=S1*B1 S2=S1B1,因为多项式卷积满足结合律 k k k阶即为 S k = S 1 ∗ B 1 k Sk=S1*B1^k Sk=S1B1k.
此时如果多项式的科技比较强,直接套一个多项式快速幂就结束了.
但是显然我的科技树比较差,所以来讨论一下低科技的解法
因为我们无法进行多项式快速幂,所以我们考虑使用生成函数的方法将多项式转为一个函数然后在做考虑.那么此时我们的 B B B就是 1 + x + x 2 + . . . + x n 1+x+x^2+...+x^n 1+x+x2+...+xn,求一下和就是 ( 1 − x n ) / ( 1 − x ) (1-x^n)/(1-x) (1xn)/(1x),为了方便起见,我们此时不妨选择 x ∈ ( 0 , 1 ) x\in(0,1) x(0,1),那么此时我们的 B B B就是 1 / ( 1 − x ) 1/(1-x) 1/(1x),那么此时 B k = ( 1 − x ) − k B^k=(1-x)^{-k} Bk=(1x)k.
考虑使用扩展二项式定理: ( a + b ) n = a n ∗ ( 1 + b a ) n = a n ∗ ∑ i = 0 ∞ ( n i ) ∗ ( b a ) i (a+b)^n=a^n*(1+\frac{b}{a})^n=a^n*\sum_{i=0}^{\infty}{n\choose i}*(\frac{b}{a})^i (a+b)n=an(1+ab)n=ani=0(in)(ab)i
那么对于上述式子来说就是 B k = ∑ i = 0 ∞ ( − k i ) ∗ ( − 1 ) i ∗ x i B^k=\sum_{i=0}^{\infty}{-k\choose i}*(-1)^i*x^i Bk=i=0(ik)(1)ixi ( − k i ) = ( − k ) ∗ ( − k − 1 ) ∗ ( − k − 2 ) ∗ . . . ∗ ( − k − i + 1 ) i ! {-k\choose i}^=\frac{(-k)*(-k-1)*(-k-2)*...*(-k-i+1)}{i!} (ik)=i!(k)(k1)(k2)...(ki+1) = ( − 1 ) i ∗ k ∗ ( k + 1 ) ∗ ( k + 2 ) ∗ . . . ( k + i − 1 ) i ! =(-1)^i*\frac{k*(k+1)*(k+2)*...(k+i-1)}{i!} =(1)ii!k(k+1)(k+2)...(k+i1) = ( − 1 ) i ∗ C k + i − 1 i =(-1)^i*C_{k+i-1}^i =(1)iCk+i1i

对于 C k + i − 1 i C_{k+i-1}^i Ck+i1i,显然我们是递推来求和的(注意本题的 k k k很大,只能递推来求和,无法预处理), C k + i − 1 i = C k + i − 2 i − 1 ∗ ( k + i − 1 i ) C_{k+i-1}^i=C_{k+i-2}^{i-1}*(\frac{k+i-1}{i}) Ck+i1i=Ck+i2i1(ik+i1).

那么此时我们的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 (1x)k,使用二项式定理展开就是 ∑ i = 0 ∞ C k i ∗ ( − x ) k \sum_{i=0}^{\infty}C_k^i*(-x)^k i=0Cki(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 rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const int mod=1004535809;
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int f[maxn],g1[maxn],g2[maxn];
inline ll get_read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=(x*10%mod+ch-'0')%mod;return x*w;
}
int qpow(int a,int b) {int ans=1;while(b) {if(b&1) ans=ans*a%mod;b>>=1;a=a*a%mod;}return ans;
}
int rev[maxn];
void NTT(int *a,int n,int inv) {for(int i=0;i<=n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);for(int len=1;len<=(n>>1);len<<=1) {int gn=qpow(inv==1?3:qpow(3,mod-2),(mod-1)/(len<<1));for(int i=0;i<=n;i+=(len<<1)) {int g0=1;for(int j=0;j<=len-1;j++) {int x=a[i+j],y=a[i+j+len]*g0%mod;a[i+j]=(x+y)%mod;a[i+j+len]=((x-y)%mod+mod)%mod;g0=g0*gn%mod;}}}
}
signed main() {int n=read();int k=get_read();int t=read();for(int i=1;i<=n;i++) {f[i]=read();}int limit=1,len=0;while(limit<=2*n) limit<<=1,len++;for(int i=0;i<=limit;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(len-1));g1[0]=1;for(int i=1;i<=n;i++) {g1[i]=g1[i-1]*(k+i-1)%mod*qpow(i,mod-2)%mod;}g2[0]=1;for(int i=1;i<=n;i++) {g2[i]=(g2[i-1]*(k-i+1)%mod*qpow(i,mod-2)%mod*-1+mod)%mod;}if(t==0) {NTT(f,limit,1);NTT(g1,limit,1);for(int i=0;i<=limit;i++) {f[i]=f[i]*g1[i]%mod;}NTT(f,limit,-1);int inv=qpow(limit,mod-2);for(int i=0;i<=limit;i++) {f[i]=f[i]*inv%mod;}}else {NTT(f,limit,1);NTT(g2,limit,1);for(int i=0;i<=limit;i++) {f[i]=f[i]*g2[i]%mod;}NTT(f,limit,-1);int inv=qpow(limit,mod-2);for(int i=0;i<=limit;i++) {f[i]=f[i]*inv%mod;}}for(int i=1;i<=n;i++) {cout<<f[i]<<" ";}return 0;	
}
http://www.lryc.cn/news/180918.html

相关文章:

  • uboot启动流程-uboot内存分配
  • LeetCode 面试题 08.02. 迷路的机器人
  • 画CMB天图使用Planck配色方案
  • 成都瀚网科技有限公司:抖店精选联盟怎么用?
  • 第二章:最新版零基础学习 PYTHON 教程(第五节 - Python 输入/输出–如何在Python中打印而不换行?)
  • C++实现集群聊天服务器
  • 40 二叉树的直径
  • Thread.sleep(0)的作用是什么?
  • 浏览器指定DNS
  • 虚拟机安装 centos
  • 【计算机网络笔记九】I/O 多路复用
  • 踩坑日记 《正确的使用Vuex》基于 uniapp Vue3 setup 语法糖 vuex4 项目 太多坑了要吐了
  • Python无废话-办公自动化Excel修改数据
  • MySQL系统架构设计
  • Google vs IBM vs Microsoft: 哪个在线数据分析师证书最好
  • 数据链路层 MTU 对 IP 协议的影响
  • 一文拿捏基于redis的分布式锁、lua、分布式性能提升
  • 机器学习必修课 - 如何处理缺失数据
  • 阿里云服务器方升架构、自研硬件、AliFlash技术创新
  • 知识工程---neo4j 5.12.0+GDS2.4.6安装
  • BUUCTF reverse wp 81 - 85
  • 数据结构-哈希表
  • 深度学习在图像识别领域还有哪些应用?
  • 前端项目练习(练习-005-webpack-03)
  • 『力扣每日一题10』:字符串中的单词数
  • 初级篇—第三章多表查询
  • <Xcode> Xcode IOS无开发者账号打包和分发
  • vertx的学习总结2
  • 网络安全内网渗透之DNS隧道实验--dnscat2直连模式
  • 探索ClickHouse——连接Kafka和Clickhouse