19.4.18 考试小记

发布于 2018-04-19  4.74k 次阅读


换用Linux之后的第一场考试,感觉还算比较顺利,最起码gedit适应的还好,有空可以再试试vim。对拍没出什么问题,diff看起来比fc好用。

T1

考场上写了60,但最后<=1e4的部分分T了一个点,直接来说正解。

首先,对于n2的限制,我们可以直接搞掉,所以问题就转换成了处理第一部分的限制。

看到n1很小,也就是说我们可以容斥来转换成第二个问题,之后问题就又变成了快速计算任意模数的组合数问题。

之前的搞法都是利用不同题目式子的特殊性或者只能搞分解以后都是质数的情况,而且时间复杂度也不是很优秀,今天再来说一种对于一部分情况比较优秀的方法,先上个链接:中国剩余定理与扩展 Lucas定理与扩展 学习笔记

首先,大体思路还是先把模数分解成p^k的乘积,然后分别对于每部分求解,最后一次CRT。由于我们还是要利用逆元,所以可以把阶乘除去p的因子的答案算出来,再考虑p的因子带来的影响,直接上变形之后的式子(就是找规律弄出来的):

$$ n ! = \lfloor \frac {n}{p} \rfloor ! * S(n) * p ^{\lfloor \frac {n}{p} \rfloor }$$

其中S(n)的定义就是[2,n]中与p互质部分的乘积,观察可以发现,这部分其实是循环的(p^k),那么我们可以只算一段,之后再搞零散的。另外,对于p的因子的次数,可以直接用O(log(p,n))的复杂度算出来,所以算法的步骤就比较明确了,先预处理S(n),复杂度是O(最大的p^k),然后递归log(n)层求出阶乘,每层的快速幂如果没有使用黑科技的话会多一个log,所以求阶乘的复杂度是O(log(p,n)*log(2,n))的。那么对于单次求组合数,复杂度就是2个log。如果最大的因数比较小,使得预处理的复杂度可以接受,那么这种做法是十分优秀的。

 

T2

FWT裸题,主要的困难在于p很大。考虑到模数很小,以至于我们可以倍增处理出每个数经过一些操作后的结果,那么我们就可以先把原序列FWT,之后对于每个元素,求出变换后的值,然后IFWT回去。

至于如何倍增,具体还是看代码吧。

 

T3

还没改完,但是实在不太想写了。出题人把题面写错了,导致考试浪费了一些时间理解题意,考完发现题解好像也写错了= =。


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974