1.逆元求解组合数

目标：求出C(n,m)%p 这里p是一个素数！

方法：费马小定理求逆元

因为膜的性质并不对除法适用，比如(a/b)%c;

但是，当我们知道了b%c的逆元d时，问题可以转化为:(a*d)%c=((a%c)*(b%c))%c;

考虑费马小定理：

a^p-1=1(mod p)

显然有：

a*a^p-2=1(mod p)

那么a^p-2就是a膜p意义下的逆元

利用快速幂即可求出！

然后我们需要预处理出m!,(n-m)!，分别对他们求出逆元，再与n!乘并取模即可！

2.组合数常用公式：

C(n,m)=C(n,n-m);

C(n,m)=C(n-1,m-1)+C(n-1,m);

这样，所有的组合数都可以实现线性递推！
还需要注意预处理啊！

C(0,i)=C(1,1)=1;

C(0,0)=0;

P2822 组合数问题

#include<cstdio>
using namespace std;
const int N=2001,M=2001;
int c[N][M],ans[N][M],n,m,T,k;
inline int min(int x,int y)
{
return x<y?x:y;
}
int main()
{
scanf("%d%d",&T,&k);
c[0][0]=c[1][0]=c[1][1]=1;
for(int i=2;i<=2000;i++)
{
c[i][0]=1;
for(int j=1;j<=2000;j++)
{
c[i][j]=(c[i-1][j-1]+c[i-1][j])%k;
ans[i][j]=ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
if(!c[i][j]) ans[i][j]++;
}
ans[i][i+1]=ans[i][i];
}
for(int i=1;i<=T;i++)
{
scanf("%d%d",&n,&m);
if(m>n)
printf("%d\n",ans[n][n]);
else
printf("%d\n",ans[n][m]);
}
return 0;
}

知识点：逆元求组合数取模

原文：https://www.cnblogs.com/little-cute-hjr/p/11787646.html