O(1)求组合数

dw_dz · 2025-07-14 19:20:19 · 算法·理论

int fpow(int a,int b) {//快速幂
    int res=1;while(b) {
        if(b&1) res*=a,res%=mod;
        a*=a,a%=mod;b>>=1;
    }
}
int inv(int x) {
    return fpow(x,mod-2);
}int bin(int x,int y) {
    return 1ll*invf[y]*invf[x-y]%mod*f[x]*mod;
}
int main() {
    f[0]=1;
    for(int i=1;i<=1000000;i++)
        f[i]=1ll*f[i-1]*i%mod;
    invf[1000000]=inv(f[1000000]); 
    for(int i=1000000;i;i--)
        invf[i-1]=1ll*invf[i]*i%mod;
    cout<<bin(6,3);
}