组合数 2.1 2.2

 O(nlogn)预处理， O(1)查询

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;const int N = 100010, mod = 1e9 + 7;int n;
int fact[N], infact[N];int qmi(int a, int k)
{int res = 1;while(k){if(k & 1)res = (ll)res * a % mod;a = (ll)a * a % mod;k >>= 1;}return res;
}int C(int a, int b)
{return (ll)fact[a] * infact[b] % mod * infact[a - b] % mod;
}int main()
{IOScin >> n;fact[0] = infact[0] = 1;for(int i = 1; i < N; i ++){fact[i] = ((ll)fact[i - 1] * i) % mod;infact[i] = qmi(fact[i], mod - 2);}while(n --){int a, b;cin >> a >> b;cout << C(a, b) << endl;}return 0;
}

O(n)预处理，O(1)查询

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'using namespace std;typedef pair<int, int> PII;
typedef long long ll;
typedef long double ld;const int N = 100010, mod = 1e9 + 7;int n;
int fact[N], infact[N], inv[N];int C(int a, int b)
{return (ll)fact[a] * infact[b] % mod * infact[a - b] % mod;
}int main()
{IOScin >> n;fact[0] = fact[1]= infact[0] = infact[1] = inv[1] = 1;for(int i = 2; i < N; i ++){fact[i] = ((ll)fact[i - 1] * i) % mod;inv[i] = (ll)(mod - mod / i) * inv[mod % i] % mod;infact[i] = (ll)infact[i - 1] * inv[i] % mod;}while(n --){int a, b;cin >> a >> b;cout << C(a, b) << endl;}return 0;
}