AcWing 886. 求组合数 II（预处理）

AcWing 886. 求组合数 II（预处理）

组合数模板二：O(a*log(mod))（a–组合数下界，mod–模数）

来自数论的常识

与组合数I不同的是，上一题是预处理所有c[a][b]的值，这一题是预处理中间的一步

由

那么 (b!)^(−1) 与 ((a−b)!)^(−1) 该如何求呢？

答案：利用之前学过的利用快速幂求逆元

推导：

快速幂求逆元

时间复杂度：O(a∗log(mod))（对滴，求逆元的时候快速幂的时间复杂度是log mod，此时mod-2就是几次幂）

//关键在预处理
//关键在预处理
#include

using namespace std;

#define int long long
const int mod=1e9+7,N=1e5+10;
int fac[N],infac[N];

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = res * a % p;
        a = a * a % p;
        k >>= 1;
    }
    return res;
}

signed main()
{
    int n;
    fac[0]=infac[0]=1;
    for(int i=1;i>n;
    while(n--)
    {
        int a,b;
        cin>>a>>b;
        cout<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5719017.html