about 4 years ago

$$一如既往,[condition]的意思是,如果方括号内的条件为真,则值为1,反之为0.$$

首先要感谢Picks和Foreseeable97大牛给我提供的帮助


单位根真是太神奇了!

这标题看起来有点13.... 不过单位根真的很有用,能用来化简一类等差循环和式 (不确定这个名词是否存在....)
先给出公式吧,证明后面会讲。


$$\omega 是k次单位根$$
不清楚单位根的可以自行wiki
先给出两道题目题目的链接。。方便各位去切题
PYXFIB

Guideposts


进入正题。

先从PYXFIB开始好了。我介绍的是一种相对来说好理解的做法,也可以很方便推广到Guideposts上 (这种做法我是看hza的blog时发现的,orz...)
照例,先来看看我们要求的式子,然后进行初步化简。

我们先把k|i的约束放在一边。 先来解决一个子问题(也可以理解成k=1时的情况)

这就有点棘手了。 但是因为我们可以通过矩阵乘法快速计算出Fibonacci数列的第n项,所以尝试写出Fibonacci数列的转移矩阵G。
这样整个式子可以变成下面的形式:

看看前面的组合数系数,是不是有点类似二项式系数。 其实二项式定理在矩阵的运算中也是成立的, 因此我们有:

其中1为单位矩阵。

这样当k=1的时候,我们就可以用矩阵乘法快速幂求出答案了。


keep going!

接下来我们考虑[k|i]这个条件。
注意开头提到的那个式子

我们可以把它带入开始的式子。

嗯... 现在这个式子看上去就蛮可做的样子。
再结合刚刚的矩阵的形式。

$$现在我们就可以枚举t,对于每个t,用矩阵乘法快速幂求出 \left ( G \omega ^t +1 \right )^n,最后再除以k就行了$$
$$这样总共的复杂度就是O(k*logn*2^3)$$


然后是Guideposts这题,做法几乎和PYXFIB一模一样。
稍微了解一点图论的同学都知道,求图中一点走k步后到达另一点的方案数只要将这个图的邻接矩阵自乘k次,然后矩阵中的数就是两点间路径的方案数。
更多有关内容参见YHC大牛的论文

$$应用上题的方法我们得到了一个O(k*logn*m^3)的做法$$


看到这里大家应该都会做了。。 后面我来自娱自乐一下。讲一些和这两题有关的细节问题。

两题都要求取模,那么我们一般意义上的单位根(定义在复数域中的)可能会遇到很多问题。 首先是中间不能取模,以及精度的问题难以解决。 那应该怎么办呢?
我们可以使用数论变换(NTT)中的单位根(定义在mod P的剩余系下)。

其中G为P的一个原根

这样我们就可以利用它来完成上述的算法了。


最后,证明一下开头的那个公式

当n是k倍数的时候

当n不是k倍数的时候


至于代码。。 写的太丑了,我就不贴了。 hza博客中有python写的PYXFIB,做法和我这个应该是一样的

← [Ahoi2009]chess 中国象棋 SRM 622 DiV 1 简要题解 →
 
comments powered by Disqus