搜索
简帛阁>技术文章>[AcWing 886] 求组合数 II

[AcWing 886] 求组合数 II

预处理 复杂度 $ O(n \cdot log(n)) $

总体复杂度 $ 10^{5} \times log(10^{9}) = 3 \times 10^{6} $


点击查看代码
#include<iostream>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10, mod = 1e9 + 7;
int fact[N], infact[N];

int qmi(int a, int k, int p)
{
    int res = 1;
    while (k) {
        if (k & 1)  res = (LL) res * a % p;
        k >>= 1;
        a = (LL) a * a % p;
    }
    return res;
}
int main()
{
    fact[0] = infact[0] = 1;
    for (int i = 1; i < N; i ++) {
        fact[i] = (LL) fact[i - 1] * i % mod;
        infact[i] = (LL) infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
    int n;
    cin >> n;
    while (n --) {
        int a, b;
        cin >> a >> b;
        printf("%d\n", (LL) fact[a] * infact[b] % mod * infact[a - b] % mod);
    }
    return 0;
}

  1. 先求出阶乘和阶乘的逆元,求逆元时用快速幂;
  2. 每当两个变量相乘就要取一次模;
预处理复杂度$O(n\cdotlog(n))$总体复杂度$10^{5}\timeslog(10^{9})3\times10^{6}$点击查看代码include<iostream>using
一、高斯消元对矩阵n*n*x列向量n枚举每一列(c+,r)1、找到当前列绝对值最大的行(如果为0则下一列)2、将当前行与1、中的行的元素交换3、将当前行的当前列元素化为14、利用当前行的元素,将后面行
1include<bits/stdc++h>2usingnamespacestd;34intmain()5{6intn,ans0;7cin>>n;8for(inti1;i<
1include<bits/stdc++h>2usingnamespacestd;3intdp[205][5050];4intv[205],w[205];5intn,k;6intmain(
目:从1∼n这n个整数中随机选出m个,输出所有可能的选择方案。输入格式:两个整数n,m,在同一行用空格隔开。输出格式:按照从小到大的顺序输出所有方案,每行1个。首先,同一行内的升序排列,相邻两个数
目链接题目描述从1∼n这n个整数中随机选出m个,输出所有可能的选择方案。输入格式两个整数n,m,在同一行用空格隔开。输出格式按照从小到大的顺序输出所有方案,每行1个。首先,同一行内的升序排列,相邻
AcWing93递归实现组合型枚举写在前面:AcWing是由北大一神级人物——“大雪菜”创办的算法交流社区,里面除了正常oj网站的功能之外,还提供单人训练、双人匹配、云端操作系统等模式,除此之外不定期
AcWing93递归实现组合型枚举题目描述从1∼n1∼n1∼n这nnn个整数中随机选出mmm个,输出所有可能的选择方案。输入格式两个整数n,mn,mn,m,在同一行用空格隔开。输出格式按照从小到大的顺
递归实现组合型枚举题目从1~n这n个整数中随机选出m个,输出所有可能的选择方案。输入格式两个整数n,m,在同一行用空格隔开。输出格式按照从小到大的顺序输出所有方案,每行1个。首先,同一行内的升序排列
试除法复杂度$O(\sqrt{n})$总体复杂度$100\times\sqrt{2^{31}}\approx46\times10^{6}$点击查看代码include<iostream>in