Lucas定理

#include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; typedef long long LL; const int MAXN=1e4+5; const int MAX_P=1e4+5; const double eps=1e-8; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int extgcd(int a,int b,int& x,int& y) { int d=a; if(b!=0) { d=extgcd(b,a%b,y,x); y-=(a/b)*x; }else { x=1;y=0; } return d; } int mod_inverse(int a,int m) { int x,y; extgcd(a,m,x,y); return (m+x%m)%m; } int fact[MAX_P];//预处理n! mod p的表 O(p) //分解n!=ap^e,返回a mod p O(log_p n) int mod_fact(int n,int p,int& e) { e=0; if(n==0) return 1; //计算p的倍数的部分 int res=mod_fact(n/p,p,e); e+=n/p; //由于(p-1)!=-1,因此(p-1)!^(n/p)只需要知道n/p的奇偶性就可以计算了。 if(n/p%2!=0) return res*(p-fact[n%p])%p; return res*fact[n%p]%p; } //求C_n^k mod p O(log_p n) int mod_comb(int n,int k,int p) { if(n<0||k<0||n<k) return 0; int e1,e2,e3; int a1=mod_fact(n,p,e1),a2=mod_fact(k,p,e2),a3=mod_fact(n-k,p,e3); if(e1>e2+e3) return 0; return a1*mod_inverse(a2*a3%p,p)%p; } int main() { return 0; }