排列组合CNK模P

2019-04-13 17:17发布

站内文章 / 模拟电子
15761 0 1690
#include using namespace std; int fact[100]; 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; }//d = gcd(a, b); int mod_inverse(int a,int m){//求modp意义下a的逆元 int x,y; extgcd(a,m,x,y); return (m+x%m)%m; } int mod_fact(int n,int p,int& e){ e=0; if(n==0)return 1; int res=mod_fact(n/p,p,e); e+=n/p; if(n/p%2!=0) return res*(p-fact[n%p])%p; return res*fact[n%p]%p; }//第一个不懂的地方就是为什么要乘个RES int mod_comb(int n,int k,int p){//求CNK模P if(n<0||k<0||ne2+e3) return 0;//如果e1>e2+e3就表明除完之后还有P，所以MODP必为0 return a1*mod_inverse(a2*a3%p,p)%p;//求[a1/(a2*a3)]%p }//第二个不懂的地方就是e2+e3-e1多余的p到了哪里？等等，真的全有多吗？不会的！ int main(){ int n,k,p; cin>>n>>k>>p;//输入,N,K,P int ji=1;fact[0]=0; for(int i=1;iP就可以直接0了 #include using namespace std; int fact[100]; int mod_fact(int n,int p,int& e){ e=0; if(n==0)return 1; int res=mod_fact(n/p,p,e); e+=n/p; if(n/p%2!=0) return res*(p-fact[n%p])%p; return res*fact[n%p]%p; } void solve(){ int n,p,e; cin>>n>>p; //预处理1到P范围中N的阶乘模P int ji=1; for(int i=1;i  

热门文章