Topcoder乱做
清华集训2013 BZOJ3581 扑克牌

一些小学就该会的姿势

Recursion posted @ 2016年2月24日 22:16 in 题解 with tags 多项式 , 910 阅读

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

 

为了证明我没有浪费搞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或者我说哦>_<(其实是『这样就可以拿来出题了!』)

 

Avatar_small
bx2k 说:
2016年2月25日 16:48

咋在右下角搞出一个夏娜炭啊……

Avatar_small
Recursion 说:
2016年2月25日 18:11

@bx2k: 这是夏娜(小说某卷封面),不是夏娜炭
跟你一样直接设置背景图即可。不过我不会让图贴紧右下角,所以比例不对的屏幕可能会出点偏差...

Avatar_small
bx2k 说:
2016年2月26日 13:51

@Recursion: 灼眼的夏娜炭~

pear 说:
2016年2月27日 07:23

小学生Recursion太神了!

Avatar_small
Recursion 说:
2016年2月27日 10:22

@pear: 别闹,这是梗→_→

pear 说:
2016年2月29日 17:28

话说这里大整数阶乘指的是可以让乘法快一点吧。。并没有办法避免把所有数都乘一遍?(也就是如果允许取模的话那么这个算法并没有优化什么?

Avatar_small
Recursion 说:
2016年2月29日 20:20

@pear: 并不是...可以做到O(sqrt n log^2 n)...
就是我们假设n是完全平方数(不是可以暴力乘不影响复杂度)。
构造多项式f(x)=(x+1)(x+2)...(x+sqrt n)。
那么把x=sqrt n,2sqrt n,...n-sqrt n带进去乘起来就是答案。
所以就是一个多项式多点球值问题...可以分治+多项式除法搞...

pear 说:
2016年3月01日 13:44

卧槽!阶乘居然可以优于线性。。。了

Avatar_small
bx2k 说:
2016年3月02日 14:31

@Recursion:
woc好厉害……
以前一直认为卷积是[\tex]$\Omega(n^2)$的……直到看到fft……
以前一直认为阶乘是[\tex]$\Omega(n)$的……直到看到这篇blog……

Avatar_small
Recursion 说:
2016年3月02日 20:55

@bx2k: 你在干嘛...

pear 说:
2016年3月03日 07:09

@Recursion: ta zai chi fan..

shanquan2 说:
2016年5月05日 13:00

我连小学生应该会的都不会,没救了。。。

Avatar_small
absi2011 说:
2016年5月10日 22:24

@shanquan2: 我也不会啊...gg


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter