一些小学就该会的姿势

『所谓的命运，是借口的别名。为了隐瞒自己想撇清关系，把过错推卸给他人的心态所准备的，刻意渲染成任何人也无法忤逆的无穷力量，说穿了只是虚张声势的名词罢了。』

 

为了证明我没有浪费搞OI的最后时光，我决定来补习一些小学就该会的姿势。

last update:2.29

这里只记录多项式相关，有不少内容仍处于口胡状态...

分治+多项式乘法

大家都会就不说了...反正就是利用cdq分治的思想，用FFT计算左边对右边的贡献。

bzoj3456

补集转化一下可以得到递推式[tex]f(n)=2^{\binom{n}{2}}-\sum_{i=1}^{n-1} 2^{\binom{n-i}{2}}\times \binom{n-1}{i-1}\times f(i)[/tex]。把组合数拆成阶乘就可以直接分治了。

51nod 马拉松7 E

也是分治FFT裸题...懒得写递推式了...反正很好推。

下面开始进入正题

多项式球逆

对于一个多项式[tex]A(x)[/tex]，如果存在一个多项式[tex]B(x)[/tex]满足[tex]deg B\le deg A[/tex]且[tex]A(x)B(x)\equiv 1 \pmod {x^n}[/tex]。我们称[tex]B(x)[/tex]为[tex]A(x)[/tex]的逆元。

考虑如何球解。

当[tex]deg A=0[/tex]时，[tex]A(x)\equiv k \pmod x[/tex]，那么[tex]A^{-1}(x)=k^{-1}[/tex]。

假设在[tex]\mod x^{\frac{n}{2}}[/tex]意义下的逆元已球出为[tex]B_0(x)[/tex]。那么[tex]B(x)-B_0(x)\equiv 0 \pmod {x^{\frac{n}{2}}}[/tex]。

两边平方再乘上[tex]A(x)[/tex]，得[tex]B(x)\equiv 2B_0(x)-A(x)B_0^2(x) \pmod {x^n}[/tex]。来一发FFT直接算就好了。

每次将规模缩小一半，所以复杂度为[tex]O(n\log n)[/tex]。常数有多大你自己写写就知道。

这也证明了一个多项式有逆元当且仅当常数项有逆元。

bzoj3456

变个形可以得到：

[tex]F(x)=\sum_{i=1}^{n} \frac{f(i)}{(i-1)!}x^{i}[/tex]

[tex]G(x)=\sum_{i=0}^{n} \frac{2^{\binom{i}{2}}}{i!}x^i[/tex]

[tex]H(x)=\sum_{i=1}^{n} \frac{2^{\binom{i}{2}}}{(i-1)!}x^i[/tex]

所以[tex]F(x)\equiv G^{-1}(x)H(x) \pmod {x^{n+1}}[/tex]。

球个逆元就行了。

确实跑得比分治快(20s变成了7s)...事实上应该是我原来的分治写丑了...

多项式除法

给定[tex]A(x),B(x)[/tex]，球[tex]A(x)=D(x)B(x)+R(x)[/tex]，要求[tex]deg D\le deg A-deg B,deg R<deg B[/tex]。

定义多项式系数反转[tex]A^R(x)=x^nA(\frac{1}{x})[/tex]。

代入要求的式子，变成了[tex]A^R(x)=D^R(x)B^R(x)+x^{n-m+1}R^R(x)[/tex]，然后神奇的发现[tex]R^R(x)[/tex]的影响没了！

所以直接球逆元多项式乘法即可。时间复杂度[tex]O(n\log n)[/tex]。常数不用写也知道有多大。

多项式多点求值

提前剧透这场UR C题会是shanquan2的丧病多项式数据结构题→_→

给一个多项式[tex]A(x)[/tex]，我们要求所有的[tex]A(x_i)[/tex]，[tex]i=0,1...n-1[/tex]。

每次把要求的所有[tex]x_i[/tex]折半，用分治FFT搞出两部分点的多项式乘积，在原多项式中模掉，就得到了两部分点插值的多项式，递归下去就可以了。

时间复杂度[tex]T(n)=2T(n/2)+O(n\log n)=O(n\log^2n)[/tex]。常数不用写也知道大得飞起→_→

这东西有啥用呢？我目前只知道可以球大整数阶乘。大家敬请期待UR12。

UR12 C

http://jiry_2.blog.uoj.ac/blog/1375

我比较懒，大家直接看题解吧...

值得一提的是本来shanquan2跟我说这题时是打算支持区间取倒数，区间球和的...

但是最后只想到[tex]O(n\sqrt n \log^2 n)[/tex]的常数飞起的做法。不用想也知道跑得比暴力不知道慢到哪里去了...

当然如果只有区间询问的话应该是很好做的，大概就是你把分治结构建出来，一样询问就行了。

区间修改似乎除了分块直接捏多项式也没什么好做法？如果您有想法欢迎来和shanquan2或者我说哦>_<(其实是『这样就可以拿来出题了！』)

 

[取消回复评论]

昵称 登录 E-mail: *
Web:
Twitter:

当有新评论通过 E-mail 通知我

(输入验证码)

or Ctrl+Enter