组合数&杨辉三角&卢卡斯定理&费马小定理

谢睿迪666 · 2021-07-18 22:51:39 · 算法·理论

用于快速计算出组合数

1.组合数的计算——杨辉三角

题目：P1313 [NOIP2011 提高组] 计算系数 P2822 [NOIP2016 提高组] 组合数问题

#include<bits/stdc++.h>
using namespace std;
int k,n,m,f[2010][2010];
int main()
{
    scanf("%d%d%d",&k,&n,&m);
    for(int i=0;i<=k;i++)
    {
        f[i][0]=1;
        for(int j=1;j<=i;j++)
        {
            f[i][j]=f[i-1][j-1]+f[i-1][j];
        }
    }
    printf("%d",f[n][m]);
    return 0;
}

2.组合数的计算——卢卡斯定理&费马小定理

卢卡斯定理：C(n,m)%p=C(n%p,m%p)*C(n/p,m/p)%p

卢卡斯定理可用于计算组合数（快速计算）。

费马小定理：a^(p-1)%p=1 ---> a^(p-2)%p=1/a 【条件：p是质数且p与a互质】

费马小定理可支持在做除法时取模（把除法转为乘法）。

题目：P3807 【模板】卢卡斯定理/Lucas 定理

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll a[100010];
int t,n,m,p;
ll pow(ll y,int z,int p)
{
    y%=p;ll ans=1;
    for(int i=z;i;i>>=1,y=y*y%p)if(i&1)ans=ans*y%p;
    return ans;
}
ll C(ll n,ll m)
{
    if(m>n)return 0;
    return ((a[n]*pow(a[m],p-2,p))%p*pow(a[n-m],p-2,p)%p);
    //a^(p-1)%p=1 费马小定理 
}
ll Lucas(ll n,ll m)
{
    if(!m)return 1;
    return C(n%p,m%p)*Lucas(n/p,m/p)%p;
    //C(n,m)%p=C(n%p,m%p)*C(n/p,m/p)%p 卢卡斯定理
}
int main(){
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&m,&p);
        a[0]=1;
        for(int i=1;i<=p;i++) a[i]=(a[i-1]*i)%p;
        printf("%lld\n",Lucas(n+m,n));
    }
    return 0;
}

3.组合数的奇葩性质

①：C(n,1)+C(n,2)+C(n,3)+...+C(n,n)=2^(n-1)

题目：P3414 SAC#1 - 组合数

②：如果在C(n,k)中，(n&k)==k，则C(n,k)的结果为奇数

题目：P1869 愚蠢的组合数