前置知识

$Lucas$ 定理，中国剩余定理（$CRT$），费马-欧拉定理。

费马-欧拉定理

设 $a,m$ ∈ $N^+$，且 $gcd$（$a,m$）= $1$，则我们有： $a^φ$≡$1$($/mod m$)。

其中，φ($m$) 称为对模 $m$ 缩系的元素个数。

此外，$a$ 对模 $m$ 的阶必整除 $φ$($m$)。

证明如下：（自己度娘）

https://baike.baidu.com/item/%E6%AC%A7%E6%8B%89%E5%AE%9A%E7%90%86/891345

Lucas定理

中国剩余定理（CRT）

题面概述

存在一个整数 $N$，对于约数$d$（$d|N$），求 $C_d^n$ 对 $999911659$ 取模的值

思路

$O(N)$预处理，$O(1)$查询：

先求出模 $p$ 意义下的阶乘，逆元以及逆元阶乘（因为求逆元满足积性函数）。

对于任意一个小于p的组合数 $C_m^n$，可以直接用 $jc[m] /times invjc[n] /times invjv[m-n]求出，其中 $jc[i]$ 指到 $i$ 的阶乘, $invjc[i]$ 指到 $i$ 的阶乘逆元

代码就不贴了……

0ms，0Mid