almost 2 years ago

前言

昨天考了,今天来写一下咯。

分析

这里说明一下,对于还是有点限制的,被标题骗进来的我只能23333了。
,并且满足
考虑只用求出的值,剩下的用CRT合并就行了,以下简写为
首先我们知道:

我们可以把表示成的形式,其中,这样我们就能直接做阶乘的除法了。
比如说,那么有:

因为,因此我们可以直接求逆元。
现在考虑怎么把表示成的形式。
考虑把范围内不为的倍数的数给拿出来,因为这些数与肯定为 ,因此都可以直接算到的贡献里去,剩下的数为,都含有因子,因此我们可以提取出一个,给贡献,然后递归进去算的值。
算上CRT的复杂度,预处理阶乘我们就得出了的复杂度的算法。

← 2016-7-11 省队集训 2016-7-14省队集训 →
 
comments powered by Disqus