大组合数取膜模板C_n^m%p

本文主要是介绍大组合数取膜模板C_n^m%p，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【模板代码】

【模板一】

#include<iostream>
#include<stdio.h>
using namespace std;
int pow_mod(int a,int n,int p)
{int ans=1,t=a;while(n){if(n&1)ans=(long long)ans*t%p;t=(long long)t*t%p;n>>=1;}return ans;
}
int cal(int n,int m,long p)
{if(m>n-m) m=n-m;int ans=1;for(int i=1;i<=m;i++){ans=(long long)ans*(n-i+1)%p;int a=pow_mod(i,p-2,p);ans=(long long)ans*a%p;}return ans;
}int com_mod(int n,int m,long p)
{if(n<m)return 0;return cal(n,m,p);
}int lucas(int n,int m,long p)
{int r=1;while(n&&m&&r){r=(long long)r*com_mod(n%p,m%p,p)%p;n/=p;m/=p;}return r;
}int main()
{int t;scanf("%d",&t);while(t--){int n,m,p;scanf("%d%d%d",&n,&m,&p);printf("%d\n",lucas(n,m,p));<span style="white-space:pre">	</span>//求组合数C n m ，然后对 p 取膜}
}

【模板二】

#include<stdio.h>long long  min(long long  a,long long  b)
{if(a>b)return b;else return a;
}long long  ext_gcd(long long  a,long long  b,long long  &x,long long  &y)
{if(b==0){x=1,y=0;return a;}long long  res=ext_gcd(b,a%b,y,x);y-=a/b*x;return res;
}long long  retx(long long  a,long long  b,long long  n)
{long long  res,x,y,t;res=ext_gcd(a,b,x,y);if(n%res==0){x=x*n/res;t=b/res;if(t<0)t=-t;x=(x%t+t)%t;return x;}return -1;
}long long Cfun(long long n,long long m,long long p)
{long long  up=n,all=1,i;long long  down=m;for(i=1;i<=m;i++){all=all*up;all=all%p;if(all%down==0)all=all/down;elseall=retx(down,p,all);down--;up--;}return all;
}int main()
{long long  n,m,p,t,i;scanf("%lld",&t);while(t--){scanf("%lld%lld%lld",&n,&m,&p);m=min(m,n-m);printf("%lld\n",Cfun(n,m,p));}
}

这篇关于大组合数取膜模板C_n^m%p的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---