出了两道题到bzoj上

出水题攒rp好了=-=

标题分别为XOREQU和PYXFIB……应该算是两道数学题吧……

XOREQU是一道水题……具体就不说了……大家都明白怎么做吧……我太弱……yy了好久怎么做……所以传到bzoj上了……其实就是noip难度……

PYXFIB也是一道水题……只是推广一个东西……矩阵的二项式定理……也算是推广傅里叶变换吧……

说一下PYXFIB的idea来源吧……这其实和poj挑战赛长郡邀请赛的最后一题做法一样,poj挑战赛那道guidepost在openjudge上除了出题人Picks和验题人我ac这题外,只有杜教和另一位不明的id为"Orzzzzzz"的神犇(这id绝对是祈使人家orz他吧)ac了这题……我觉得毕竟是一道挺好的题目……没人做太可惜……

而poj挑战赛的题目似乎有版权= =……Picks表示他似乎已经没有guidepost的版权了……所以bzoj上就没有poj 长郡邀请赛的题目了……

因为guidepost那题的做法是可以推广的

于是我就出了另一种形式的题目(其实idea依旧来自Picks)……

然后因为fib数列可以用矩阵的若干次幂表示……所以我们就可以用guidepost类似的做法来搞了=-=

我的做法是Picks yy出来的原始做法=-=手动傅立叶变换后矩阵快速幂……

xudyh对于guidepost的做法应该是常数比较小的另一种做法……我曾要过代码……可惜未曾仔细看过……至今不是很懂=-=

我是不会贴题解的啦……

可以去找poj挑战赛题解……大概就会这题了……

其实这题也不是特别难——Picks

众神请轻虐


xorequ果然是大水题……祝大家经验++

pyxfib水题的本质也被发现了,jcvb已经切掉这题……说明我的数据应该是没有错的……

但由于数据随机,比较弱……可能卡不掉乱搞做法

现在说明pyxfib原始做法:

考虑fib数列转移矩阵,设为G

那么我们考虑如下式子:

上式的1可以理解为单位矩阵

我们把所有G的幂为k的倍数的矩阵提出来,然后加起来,就能轻松得到答案,

怎么提取考虑单位根

我们设1的k次单位根为r=a+bi

那么

把这样的复数矩阵做快速幂,得到的实部构成的矩阵就是我们要分离出的矩阵

考虑我们中间计算涉及的虚数,都可以用如下方式表示

这样的数是一个数域,显然里面的数做加减乘除得到的数都可以这样表示

我们看这种数字的乘法

接下来的推导容易发现A与B的乘法就是一个循环卷积的形式,因为r是k次单位根,所以A*B依旧可以看成一个k维向量

这样数域里的两个数相乘就可以O(k^2)的时间内完成,那么本题就得到了一个单次O(lgn*2^3*k^2)的做法

由于k很大,我们要考虑优化

看到卷积就要想到傅里叶变换优化

但是fft不适合用来优化这个循环卷积

所以我们要考虑更优秀的做法,

我们注意到普通的傅里叶变换是对n个单位根,每次O(n)多项式求值(n为多项式的阶)

而这题

我们注意到

这个矩阵里的数,看成k维向量后,只可能第1维和第0维非0,其它高维一定是0

把这个k维向量看成多项式后,显然可以O(1)求值

那么我们把k个复根分别带入这个多项式,进行手动傅里叶变换

然后在做矩阵乘法的时候,每次O(k)的向量相乘

就能得到最后答案矩阵的傅里叶变换形式

因为我们只需要用到答案矩阵的O(1)项,那么我们利用算导中介绍的逆傅里叶变换矩阵,直接进行单次O(k)的逆傅里叶变换

就能得到答案

至于题目里面的那个

只是为了方便弄出模P意义下的k次单位根而已,没有深意

单组数据O(lgn*k*2^3)

这个做法比较暴力,常数相对大一点……我已经打算卡掉了……

代码略

人学过fft之类的东西之后就容易想复杂 ——fotile

其实我给主席做这题的时候,他yy出的大概就是杜教的做法……
至于杜教的做法,常数要更好一点,而且也更好理解……我就不说了……

至于jcvb的做法,我现在不明……

Comments

comments powered by Disqus