无穷和式问题

绝地灬酷狼 2022-01-12 10:43 162阅读 0赞

![1399631-20190217215043225-2090971478.png][]

这个题就用到红线

![1399631-20190217215857068-1506324861.png][]

为啥是有理数一会就知道了

**$P(x)/Q(x)$可以裂项**

$\\frac\{P(x)\}\{Q(x)\}=\\sum \\frac\{Ci\}\{x+b\_i\}=\\frac\{P(x)\}\{\\Pi(x+b\_i)\}$

通分:$\\sum \\frac\{Ci\\frac\{\\Pi(x+b\_j)\}\{(x+bi)\}\}\{\\Pi(x+b\_j)\}=\\frac\{P(x)\}\{\\Pi(x+b\_i)\}$

由于$P(x)$是N-2次的，而分子是N-1次的，所以最高次项一定是0，也就是$\\sum C\_i=0$

所以x非常大的时候会消完，就是有理数了

大概就1e6(bi的范围)项

$\\sum Ci\\frac\{\\Pi(x+b\_j)\}\{(x+bi)\}=P(x)$

然后把$-b\_i$依次带入式子，$Cj$系数都是0了，就剩下$C\_i\*const1=const2$除过去就可以了

最后枚举每个分数对答案的贡献：  
找到最后一个不会被消去的n（大概在1e6(b的范围）），对$b\_i$排序，n从1开始枚举，不断加入一些Ci，每次计算即可。（可以线性预处理逆元）

Ci直接算是O(n^2)的

快速一些要多点求值：

1.$P(x)$多点求值

2.$Q'(x)=\\sum\_\{i=1\}^n \\frac\{\\Pi\_\{j=1\}^n(x+b\_j)\}\{(x+bi)\}$带入$-b\_i$之后恰好就是$C\_i$的系数，也多点求值

$P(x)/Q(x)$也不是什么时候都可以裂项的，，有的时候也会把$Q(x)$乘过去

[学习笔记\]整数划分数][Link 1]生成函数求法

转载于:https://www.cnblogs.com/Miracevin/p/10393030.html

[1399631-20190217215043225-2090971478.png]: /images/20220109/06c5bb71277f485cba37844170f62340.png
[1399631-20190217215857068-1506324861.png]: /images/20220109/27bdd565a5d149eab3a3ef381c54ded1.png
[Link 1]: https://www.cnblogs.com/Miracevin/p/10392750.html

发表评论取消回复

表情：

评论列表（有 0 条评论，162人围观）

还没有评论，来说两句吧...

相关阅读

相关 Java泛型：边界条件和隐式转换问题

在Java编程中，泛型是一种参数化类型，它可以让你的代码更具有灵活性和通用性。然而，当涉及到边界条件和隐式转换时，可能会遇到一些问题。 1. 边界条件：泛型通常是在其范围内的

爱被打了一巴掌/ 2024年09月17日 01:24/ 0 赞/ 24 阅读

相关算法无穷性是指什么

极限0和无穷算法这个2道题求解答详细 (5)改成，(1+2/k^2)^k，在k趋近于正无穷的极限，则打开，第一项为1，第二项为2k/k^2=2/k趋近于0，可见，后面都趋

本是古典何须时尚/ 2023年09月25日 08:55/ 0 赞/ 9 阅读

相关 java中的“我”不是“我”，NaN特殊标识以及正无穷+负无穷应该等于多少？

上文：[Java虚拟机规范.Java SE 8版中关于浮点类型的说明，Infinity和-Infinity][Java_.Java SE 8_Infinity_-Infinit

逃离我推掉我的手/ 2022年12月10日 12:28/ 0 赞/ 107 阅读

相关列式存储和行式存储

行式存储数据库和列式存储数据库，随着业务深入，技能增长，经常会碰到，今天来理解一下。列式存储（Clolumn-Based）和行式存储(Row-Based)都是相对于对方的，

墨蓝/ 2022年11月21日 01:18/ 0 赞/ 305 阅读

相关想发挥无穷力量——《广播》

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

本是古典何须时尚/ 2022年10月06日 12:48/ 0 赞/ 82 阅读

相关编程中无穷的表示

int不能表达真正的无穷大或者无穷小。在C语言中，int为整型类型，根据不同平台不同，有16位(2字节)和32位（4字节）两种，其中32位int为目前主流。无

深藏阁楼爱情的钟/ 2022年09月30日 14:57/ 0 赞/ 188 阅读

相关专升本高数学习总结——无穷级数

常数项级数正项级数的审敛法比较审敛法比值审敛法根值审敛法

妖狐艹你老母/ 2022年09月28日 13:01/ 0 赞/ 204 阅读

相关显式Intent和隐式Intent

Intent是各组件之间交互的一种重要方式，它不仅可以指明当前组件想要执行的动作，还可以在不同组件之间传递消息。一般被用于启动活动、启动服务以及发送广播等场景。主要分为

小鱼儿/ 2022年05月08日 07:10/ 0 赞/ 235 阅读

相关无穷和式问题

![1399631-20190217215043225-2090971478.png][] 这个题就用到红线 ![1399631-20190217215857068-15

绝地灬酷狼/ 2022年01月12日 10:43/ 0 赞/ 163 阅读

相关 JS隐式转换问题

JS隐式转换问题在写笔试题的时候，经常碰到涉及隐式转换的题目，例如 "1" + 2 obj + 1 [] == ![] [null] == false === 和 =...

红太狼/ 2020年06月22日 15:18/ 0 赞/ 675 阅读