临沂做网站企业,鹤壁海绵城市建设官方网站,网站seo推广软件,帝国cms王猛微博题目大意 对于一个很大的$n,m,p$如何求$C_{nm}^m\mod p$#xff1f; Lucas定理 若$n_i,m_i$分别是$n,m$在$p$进制下第$i$位的数字#xff0c;则有 $$C_n^m\mod p\prod_{i0}^{\log_p m}C_{n_i}^{m_i}\mod p$$ 求法 按照定理式一个一个求组合数即可。 组合数并不用批量求。故预…题目大意 对于一个很大的$n,m,p$如何求$C_{nm}^m\mod p$ Lucas定理 若$n_i,m_i$分别是$n,m$在$p$进制下第$i$位的数字则有 $$C_n^m\mod p\prod_{i0}^{\log_p m}C_{n_i}^{m_i}\mod p$$ 求法 按照定理式一个一个求组合数即可。 组合数并不用批量求。故预处理出各项阶乘值然后运用 $$C_n^m\frac{n!}{m!(n-m)!}$$ 因为取模P运用乘法逆元、快速乘工具求解即可。 注意事项 MAX_N应当为n,m的范围*2因为nm。求组合数时若mn返回0。 #include cstdio
#include iostream
#include cstring
#include algorithm
using namespace std;#define ll long long
#define inv(a) Inv(a, P)
#define mult(a, b) Mult(a, b, P)const int MAX_N 200010;
ll Fact[MAX_N];
ll P;void GetFact(int n, ll* Fact, ll p)
{Fact[0] 1;for (int i 1; i n; i)Fact[i] Fact[i - 1] % p * i % p;
}ll Exgcd(ll a, ll b, ll x, ll y)
{if (b 0){x 1;y 0;return a;}ll d Exgcd(b, a%b, x, y);ll tx x;x y;y tx - a / b * y;return d;
}ll Inv(ll a, ll p)
{ll x, y;Exgcd(a, p, x, y);return (x % p p) % p;
}ll Mult(ll a, ll b, ll p)
{ll ans 0;while (b){if (1 b)ans (ans a) % p;a (a a) % p;b 1;}return ans;
}ll Comb(ll n, ll m)
{if (m n)return 0;return mult(Fact[n], inv(mult(Fact[m], Fact[n - m])));
}ll Lucas(ll n, ll m, ll p)
{if (m 0)return 1;return Comb(n % p, m % p) * Lucas(n / p, m / p, p) % p;
}int main()
{int caseCnt;scanf(%d, caseCnt);while (caseCnt--){ll n, m;scanf(%lld%lld%lld, n, m, P);GetFact(n m, Fact, P);printf(%lld\n, Lucas(n m, m, P));}return 0;
}转载于:https://www.cnblogs.com/headboy2002/p/9126156.html
