$C_n^k\%M$

未分类

---

求$C_n^k\%M(1\leq n \leq 10^{18},0\leq k \leq 10^3,1\leq M \leq 10^{18})$

解析：

$$\begin{align*} C_n^k=\sum_{i=0}^{k}C_m^iC_{n-m}^{k-i} \end{align*}$$
这里令$m=\lfloor\frac{n}{2}\rfloor$.
设$f(n)=\{C_n^0,C_n^1,...,C_n^n\}$，求出$f(m),f(n-m)$之后可以用$O(k^2)$的时间计算$f(n)$.
如果$n$是奇数，$n-m$比$m$大1，可以根据$C_n^i=C_{n-1}^i+C_{n-1}^{i-1}$来由$f(m)$在$O(k)$的时间内求出$f(n-m)$，否则$f(n-m)=f(m)$，所以实际上只需求$f(m).$
考虑递归求解$f(m)$，可知递归最多$logn$层，每层回溯求解需要$O(k^2)$时间，所以总时间是$O(k^2logn)$，此处$M$较大，直接乘会溢出$long long$型$integer$，所以需要使用快速乘，复杂度是$O(k^2lognlogM)$.
$tips:$这里可以有个小优化，显然上述式子是一个卷积，所以可以使用$FFT$来优化，能把单次回溯的复杂度由$O(k^2)$降到$O(klogk)$，不过此处模数较大，使用$NTT$也还需要使用$CRT$合并，常数巨大.
综上，时间复杂度$O(k^2lognlogM)$，空间复杂度$O(k).$