参考博客exLucas：求\(C_n^m\bmodd\)(\(d\)不一定为质数)1.将\(d\)质因数分解为\(d=p_1^{c_1}\timesp_2^{c_2}\times\cdots\timesp_k^{c_k}\)\(\foralli,j\in[1,k]\),\(p_i^{c_i}\)与\(p_j^{c_j}\)互质，所以可以构造出如下同余方程：\[\begin{cases}a_1\equivC_

恶心东西爬、、、我们要求解一个\(\binom{n}{m}\modM\)，\(M\)是不太大的正整数，\(n,m\)是可能比较大的正整数。首先我们分解\(M=\prod_{i=1}^kp_i^{x_i}\)，我们对于每一个\(i\in[1,k]\)求出\(\binom{n}{m}\modp_i^{x_i}\)，然后就会组成一个方程组，\(Ans\equiv\binom{n}{m}\p

\(EXLucas\)扩展卢卡斯定理·题意试求：\[C^{m}_n\modP\\\\\\\\\\\(P\inN^*)\]注意，\(P\)非整数。·转化可以给他进行质因数分解，成为：\[P=\prod_{i=1}^kp_i^{{\alpha}_i}\]\[\begin{cases}x\equivC^{m}_n(\modp_1^{{\

【模板】扩展卢卡斯定理/exLucas题目背景这是一道模板题。题目描述求\[{\mathrm{C}}_n^m\bmod{p}\]其中\(\mathrm{C}\)为组合数。输入格式一行三个整数\(n,m,p\)，含义由题所述。输出格式一行一个整数，表示答案。样例#1样例输入#1533样例输出#11样例#2

i128作为下标的时候会出现奇怪ub！所以要先强转！#include<bits/stdc++.h>#defineint__int128#definepbpush_back//#definei64longlong//#defineusingnamespa

Lucas内容\[\binom{ap+b}{cp+d}\equiv\binom{a}{c}\binom{b}{d}\pmod{p}\]其中\(p\)为素数，\(0\leb,d<p\)，\[\binom{n}{m}=\frac{n^{\underlinem}}{m!}\]推论（重要）