求组合数 I
组合数递推式
\(C^b_a\)的含义为在a个物品中选出b个物品的方案数，我们考虑将a个物品分为两部分，a-1个物品为一部分，剩下一个物品为另一部分，
现在我们有两种方案，选择剩下那个物品，则要从a-1中选择b个，对应\(C^b_{a-1}\)。若选择剩下那个，则要从a-1中选择b-1个，对应\(C^{b-1}_{a-1}\)，
总的方案数为两部分相加。
这也对应着杨辉三角中当前数等于其两肩数之和。
时间复杂度\(O(n^2)\)，可以通过本题数据。
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
const int p = 1e9 + 7;
int c[N][N];
void ini()
{
c[0][0] = 1;
for (int i = 1; i < N; ++i)
{
for (int j = i; j >= 0; --j)
{
if (!j)
c[i][j] = 1;
else
c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;
}
}
}
int main()
{
ini();
int t;
scanf("%d", &t);
while (t--)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", c[a][b]);
}
return 0;
}
求组合数 II
此时的数据达到\(10^5\)，\(O(n^2)\)已经过不了了。
考虑公式：
我们可以先预处理出所有数的阶乘，再代入上式计算结果，但问题就在于除法不满足取模运算的性质，即：
\[\frac{a}{b}\%p \neq \frac{a\%p}{b\%p}\%p \]这个时候计算对应的乘法逆元即可。
时间复杂度\(O(nlog(n))\)
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define ll long long
int fact[N]; //存储阶乘
int infact[N]; //存储阶乘逆元
const int p = 1e9 + 7;
int ksm(int a, int b)
{
ll ans = 1;
ll base = a;
while (b)
{
if (b & 1)
{
ans *= base;
ans %= p;
}
base *= base;
base %= p;
b >>= 1;
}
return ans;
}
void ini()
{
fact[0] = 1;
infact[0] = 1;
for (int i = 1; i < N; ++i)
{
fact[i] = (ll)fact[i - 1] * i % p;
infact[i] = ksm(fact[i], p - 2) % p;
//infact[i] = (ll)infact[i - 1] * ksm(i, p - 2) % p;
}
}
int main()
{
ini();
int t;
scanf("%d", &t);
while (t--)
{
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n", (ll)fact[a] * infact[b] % p * infact[a - b] % p);
}
return 0;
}
代码中的计算阶乘的逆元两个式子都可以，简单证明一下
\((x\%p)^{-1}\%p = (x\%p)^{p-2}\%p = (x\%p*x\%p\cdots x\%p)\%p = x^{p-2}\%p = x^{-1}\%p\)
\((x-1)^{-1}*x^{-1}\%p = (x-1)^{p-2}*x^{p-2}\%p = (x!)^{-1}\%p\)
\(x^{-1}\)表示x的乘法逆元
求组合数 III
a,b达到了\(10^18\)。而且p是质数，需要使用lucas定理
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
#define ll long long
int ksm(int a, int b, int p)
{
ll ans = 1;
ll base = a;
while (b)
{
if (b & 1)
ans = ans * base % p;
base = base * base % p;
b >>= 1;
}
return ans;
}
int C(int a, int b, int p)
{
ll ans = 1;
for (int i = 0; i < b; ++i)
{
ans = ans * (a - i) % p;
ans = ans * ksm(i + 1, p - 2, p) % p;
}
return ans;
}
int lucas(ll a, ll b, ll p)
{
if (b == 0)
return 1;
return (ll)lucas(a / p, b / p, p) * C(a % p, b % p, p) % p;
}
void work()
{
ll a, b, p;
scanf("%lld%lld%lld", &a, &b, &p);
printf("%d\n", lucas(a, b, p));
}
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
work();
}
return 0;
}
时间复杂度\(O(n*log_pa*p*logp)\)
求组合数 IV
既然题目说要用高精度了，那就肯定要写高精度了。
但是如果完全用高精度写的话，除法有点麻烦，复杂度也有点高。
对于组合数公式：
考虑对其质因数分解。及：
\[x = p_1^{k_1} * p_2^{k_2} * p_3^{k_3}\cdots p_i^{k_i} \]其中所有的p都是质数。
首先介绍线性筛
void get_p(int x)
{
for (int i = 2; i <= x; ++i)
{
if (!mark[i])
prime[p_cnt++] = i;
for (int j = 0; prime[j] * i <= x; ++j)
{
mark[prime[j] * i] = 1;
if (i % prime[j] == 0)
break;
}
}
}
其中mark用来标记合数，prime用来存储素数。其本质思想是所有的合数只被其最小的质因数筛掉，这样每个合数不会被重复判断，故叫线性筛。
关键代码为break那部分，如果i已经是当前质数(prime[j])的倍数，就不用继续判断合数了，因为prime[j+1]i的最小质因数不是prime[j+1]，而是prime[j]。
那么我们可以先用线性筛找到范围内的所有质数\(C_a^b\)中的分子分母进行质因数分解。
对于阶乘的质因数分解，我们可以这样来做。
例如要求8!=1*2*3*4*5*6*7*8中2的次数:
\(\frac{8}{2}=4\)表示2，4，6，8可分别提供一个2。
\(\frac{8}{4}=2\)表示4，8可分别提供2个2，但其中一个2已经计算过。
\(\frac{8}{8}=1\)表示8可以提供3个2，但其中2个2已经计算过。
故8!有4+2+1=7个2。
按照这种方法就可以求出阶乘中所有质因数的次数。
最后的答案就是\(\prod \limits_{i}p_i^{分子次数和-分母次数和}\)
参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10;
int ans[N], cnt;
void mul(int x)
{
int t = 0;
for (int i = 0; i < cnt; ++i)
{
ans[i] = ans[i] * x + t;
t = ans[i] / 10;
ans[i] %= 10;
}
if (t)
{
while (t)
{
ans[cnt++] = t % 10;
t /= 10;
}
}
}
int prime[N], p_cnt;
int tot[N];
bool mark[N];
void get_p(int x)
{
for (int i = 2; i <= x; ++i)
{
if (!mark[i])
prime[p_cnt++] = i;
for (int j = 0; prime[j] * i <= x; ++j)
{
mark[prime[j] * i] = 1;
if (i % prime[j] == 0)
break;
}
}
}
int get(int x, int p)
{
int ans = 0;
for (int i = p; x / i; i *= p)
{
ans += x / i;
}
return ans;
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
get_p(a);
for (int i = 0; i < p_cnt; ++i)
{
tot[i] = get(a, prime[i]) - get(b, prime[i]) -get(a - b, prime[i]);
}
ans[cnt++] = 1;
for (int i = 0; i < p_cnt; ++i)
{
for (int j = 0; j < tot[i]; ++j)
mul(prime[i]);
}
for (int i = cnt - 1; i >= 0; --i)
printf("%d", ans[i]);
return 0;
}