22.4.18 考试小记

发布于 2018-04-23  4.59k 次阅读


这两天考得都是数学题。

T1

求出满足所有元素属于[1,n],长度为m且gcd为1的不下降序列个数。

显然我们可以容斥,枚举所有元素的gcd至少是d的倍数,然后乘上mu,只需要要求选出来的序列为不下降序列就好了。我们可以把这个过程看作是统计在数轴上[1,n/d]内放m个点,且允许重叠的方案数,乘组合数就好了。

 

T2

题意略。

首先,如果模数确定,我们可以O(logn)矩阵快速幂算出答案。

接着,我们发现必须要给g(x)模一个数这个题才是可做的,那么我们就来打表观察一下g的规律。

发现这破玩意有循环节,那么有循环节就意味着我们在矩阵自乘若干次后会出现单位矩阵,这样我们就可以用矩阵的BSGS来暴力寻找循环节了,这样,有了循环节的长度,我们就可以直接取模然后就可做了。

但是这个做法基本不可过(考拉直接这样写的,最后优化了半天才卡着时限过去),因为常数太大了。据出题人题解所述,出题人“打了三年的表”,找出了一些神奇的规律:1.我们可以把一个数质因数分解,然后答案就是每个部分的LCM。2.对于p^k,答案是f(p)*p^(k-1)。3.对于质数,我们应该直接计算答案,但是如果这个数的末尾是1或者9,直接返回x-1。

然后就能以非常优秀的常数通过这道题了。

 

T3

任意模数FFT+多项式多点求值(需要多项式取模等高端操作),好像目前还没有人能写出来这个玩意。

正解的做法也很恶心,反正我是不想再看到这个题了。


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