首页 > 其他分享 >短多项式快速幂

短多项式快速幂

时间:2024-03-09 22:03:36浏览次数:23  
标签:系数 kF 多项式 sum times 各项 求导 快速

求 \((x^1+x^2+...+x^k)^n\) 的各项系数,要求复杂度 \(\Theta(nk)\)。


前置知识

  • 复合函数 \(f[g(x)]\) 的求导:

    \(f[g(x)]'=f'[g(x)]g'(x)\)

  • “左乘右导,右乘左导”:

    \([f(x)g(x)]'=f(x)g(x)'+f(x)'g(x)\)


做法

设 \(F(x)=x^1+x^2+...x^k\),那么要求的就是 \(F(x)^k\)。

有 \(F(x)^{k+1}=F(x)^kF(x)\),两边求导,得到:

\[(k+1)F(x)^kF'(x)=F(x)^kF'(x)+[F(x)^k]'F(x) \]

\[kF(x)^kF'(x)=[F(x)^k]'F(x) \]

我们取出 \(x^n\) 的系数,可以得到:

\[k\sum_{i=0}^n F(x)^k[i] \times F'(x)[n-i]=\sum_{i=0}^n [F(x)^k]'[i] \times F(x)[n-i] \]

\[k\sum_{i=0}^n F(x)^k[i] \times F'(x)[n-i]=\sum_{i=0}^n (i+1) \times F(x)^k[i+1] \times F(x)[n-i] \]

把右边 \(i=n\) 的部分分离出来后,可以得到:

\[k\sum_{i=0}^n F(x)^k[i] \times F'(x)[n-i]-\sum_{i=0}^{n-1} (i+1) \times F(x)^k[i+1] \times F(x)[n-i]=(n+1) \times F(x)^k[n+1] \times F(x)[0] \]

不难发现 \(F(x),F'(x)\) 都是可以预处理的,所以这就是一个 \(F(x)^k\) 各项系数的递推式。

设 \(f_i\) 表示 \(F(x)\) 的各项系数,\(g_i\) 表示 \(F'(x)\) 的各项系数,\(h_i\) 表示 \(F(x)^k\) 的各项系数,那么可以写成:

\[k \sum_{i=0}^n h_i \times g_{n-i} - \sum_{i=0}^{n-1} (i+1) \times h_{i+1} \times f_{n-i}=(n+1) \times h_{n+1} \times f_0 \]

标签:系数,kF,多项式,sum,times,各项,求导,快速
From: https://www.cnblogs.com/tx-lcy/p/18063437

相关文章

  • Hanoi问题及其相关快速算法
    Hanoi问题抽象hanoi(n,x,y,z)step1:hanoi(n-1,x,z,y)step2:move(x,z)step3:hanoi(n-1,y,x,z)递归部分实现代码voidhanoi(intn,charx,chary,charz){​ if(n==1){ // 递归出口​ move(x,z);​ }​ else{​ hanoi(n-1,x,z,y);​ move(x,z);​ hanoi(n......
  • 中考英语首字母快速突破001-2021上海宝山英语二模
    PDF格式公众号回复关键字:ZKSZM001原文Whatislaughter?Laughterisnaturalforpeople.Westarttolaughataboutfourmonthsofage.Westarttolaughevenbeforewestarttospeak!Laughterissocial.Itconnectsuswithotherpeople.Welaughmorewhenw......
  • 多项式
    目录多项式多项式基础数域的定义多项式的定义与基本性质多项式带余式除法形式幂级数的定义幂级数的导数和不定积分常见幂级数展开多项式插值多项式插值的定义多项式插值的方法拉格朗日插值法重心拉格朗日插值法加法卷积加法卷积的定义加法卷积的变换快速傅里叶变换(FFT)快速数论变换......
  • 快速排序
    快速排序-V1一、代码实现1.大致思路假如有一个数,这个数组自然有序假如有2个数,我们选第一个数为标准,比它小的数排它前面,比它大排后面,那么这两个数将有序。假如有3个数,我们选第一个数为标准,比它小的数排它前面,比它大排后面。假如有4个数,我们选第一个数为标准,比它小的数排它前......
  • 白菜GPT | 快速上手
    白菜GPT旨在提供稳定高效且免费的OpenAIAPI转发服务,帮助国内GPT应用学习相关爱好者及从业者,提供便捷、低成本、长期稳定的GPT中转服务,免费提供中转API_KEY,从而降低各位学习成本,提高OpenAI学习应用效率,更多学习文档,请参阅官方教程本教程面向第一次接触白菜GPT的用户,仅需四步,即可......
  • [Redis] 01-Redis快速入门
    一、Redis简介Redis属于键值对(key-value)数据库Redis中所有的数据都是以key-value的形式存储在内存中的所以读写Redis非常的快,在高并发的场景下,性能非常的好二、Redis服务端(redis-server)的安装省略。建议使用docker安装。Docker安装redis(保姆级教程&图文并茂)-腾讯......
  • FMS设备监察系统无线传输模块及网关快速应用教程
    设备监察系统又叫做FMS(Facilities  Monitoring  System),该FMS系统由 GUI(配置上位机)、FMS网关和lora无线模块节点三部分组成。亿佰特上市的E53-470FMS22S、E53-DTU(470FMS22)产品是基于LoRa扩频技术开发的设备监察系统无线传输模块及网关,其强大的抗干扰能力,让无线通信在工业现......
  • 快速制定、分解、落地OKR的框架,建议你认真看!
    制定OKR(ObjectivesandKeyResults,目标与关键成果)并没有一套固定的公式,因为每个组织、团队或项目的具体情况和目标都是独特的。然而,有一些通用的步骤和考虑因素可以帮助你制定有效的OKR。以下是一个指导性的框架:一、明确组织或团队的战略目标确定长期和短期目标:明确组织或团......
  • 在Docker中,怎么快速查看本地的镜像和容器?
    在Docker中,查看本地的镜像和容器分别可以通过以下两条命令来快速实现:1.查看本地镜像要查看本地计算机上存储的所有Docker镜像,可以使用dockerimages命令。这个命令会列出所有可用的镜像,包括镜像的存储库名称、标签、镜像ID、创建时间和所占用的空间。dockerimages输出示例:......
  • 瀚高V9的快速安装部署与注意事项
    瀚高V9的快速安装部署与注意事项介质使用上传文件mkdir-p/highgo/opt/highgouseraddhighogochownhighgo/opt/highgo/highgo-Rchmod700/highgo-Rsu-highgo进行执行./bin安装选择路径/opt/highgo输入密码Testxxxxxxxx?!兼容性选择postgresql定......