求解组合数

一

给定n组询问，每组询问给出两个整数a,b 求C(a,b)mod1e9+7的值

1<=n<=1e5

1<=b<=a<=2000

用递推公式打表即可

C(a,b)=C(a-1,b-1)+C(a-1,b)

代码：

#include
using namespace std;
const int N=2010,mod=1e9+7;
int n;
int c[N][N];
void pre()
{
    for(int i=0;i
     for(int j=0;j<=i;j++)
     {
        if(!j) c[i][j]=1;
        else c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
     }
}
int main()
{
    pre();
    cin>>n;
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",c[a][b]);
    }
 
 
    return 0;
}

二

给定n组询问，每组询问给出两个整数a,b 求C(a,b)mod1e9+7的值

1<=n<=1e5

1<=b<=a<=1e5

a,b的范围变大了，开二维数组会爆

考虑:

C(a,b)=a!/b!/(a-b)!

预处理出阶乘和阶乘的逆元，带入公式计算

代码：

#include 
using namespace std;
const int N=100010,mod=1e9+7;
typedef long long ll;
int f[N],nf[N];//阶乘的逆元
int ksm(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(ll)res*a%mod;
        a=(ll)a*a%mod;
        b/=2;
    }
    return res;
}
int main()
{
    int n;
    cin>>n;
    f[0]=nf[0]=1;
    for(int i=1;i
    {
        f[i]=(ll)f[i-1]*i%mod;
        nf[i]=(ll)nf[i-1]*ksm(i,mod-2)%mod;
        //nf[i]=f[i]*ksm(i,mod-2)
    }
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        printf("%d\n",(ll)f[a]*nf[b]%mod*nf[a-b]%mod);
    }
    return 0;
}

三

给定n组询问，每组询问给出三个整数a,b,p 求C(a,b)modp的值

1<=n<=20

1<=b<=a<=1e18

1<=p<=1e5

Lucas定理:C(a,b)=C(amodp,bmodp)*C(a/p,b/p) 同余

强转为long long，防止中间运算时爆int

代码：

//Lucas定理
#include 
using namespace std;
typedef long long ll;
int p;
int ksm(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) res=(ll)res*a%p;
        a=(ll)a*a%p;
        b>>=1;
    }
    return res;
}
int C(int a,int b)   //按定义求
{
    int res=1;
    for(int i=1,j=a;i<=b;i++,j--)
    {
        res=(ll)res*j%p;
        res=(ll)res*ksm(i,p-2)%p;
    }
    return res;
}
int lucas(ll a,ll b)
{
    if(areturn C(a,b);
    return (ll)C(a%p,b%p)*lucas(a/p,b/p)%p;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        ll a,b;
        cin>>a>>b>>p;
        cout<<lucas(a,b)<<"\n";
    }
    return 0;
}