88 lines
2.3 KiB
C++
88 lines
2.3 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
const int N = 100010;
|
||
int a[N], b[N]; // 两个整数数组保存高精度计算的结果
|
||
|
||
// 欧拉筛
|
||
int primes[N], cnt;
|
||
bool st[N];
|
||
void get_primes(int n) {
|
||
for (int i = 2; i <= n; i++) {
|
||
if (!st[i]) primes[cnt++] = i;
|
||
for (int j = 0; primes[j] * i <= n; j++) {
|
||
st[primes[j] * i] = true;
|
||
if (i % primes[j] == 0) break;
|
||
}
|
||
}
|
||
}
|
||
|
||
// 计算n！中包含质数p的个数
|
||
int get(int n, int p) {
|
||
int s = 0;
|
||
while (n) s += n / p, n /= p;
|
||
return s;
|
||
}
|
||
|
||
// 高精乘低精
|
||
void mul(int a[], int &al, int b) {
|
||
int t = 0;
|
||
for (int i = 1; i <= al; i++) {
|
||
t += a[i] * b;
|
||
a[i] = t % 10;
|
||
t /= 10;
|
||
}
|
||
while (t) {
|
||
a[++al] = t % 10;
|
||
t /= 10;
|
||
}
|
||
}
|
||
|
||
// 高精减高精
|
||
void sub(int a[], int &al, int b[]) {
|
||
for (int i = 1, t = 0; i <= al; i++) {
|
||
a[i] -= t + b[i];
|
||
if (a[i] < 0)
|
||
a[i] += 10, t = 1;
|
||
else
|
||
t = 0;
|
||
}
|
||
while (al > 1 && !a[al]) al--;
|
||
}
|
||
|
||
// C(a,b)的结果，高精度保存到c数组，同时，返回c数组的长度len
|
||
void C(int a, int b, int c[], int &cl) {
|
||
// 高精度的基底，乘法的基数是1
|
||
c[1] = 1;
|
||
cl = 1; // 由于高精度数组中只有一位，是1，所以长度也是1
|
||
|
||
for (int i = 0; i < cnt; i++) { // 枚举区间内所有质数
|
||
int p = primes[i];
|
||
/*
|
||
C(a,b)=a!/(b! * (a-b)!)
|
||
a!中有多少个质数因子p
|
||
减去(a-b)!的多少个质数因子p,
|
||
再减去b!的质数因子p的个数，就是总个数
|
||
s记录了p这个质数因子出现的次数
|
||
*/
|
||
int s = get(a, p) - get(b, p) - get(a - b, p);
|
||
while (s--) mul(c, cl, p); // 不断的乘p,结果保存到数组c中。len将带回c的有效长度
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
int n, m;
|
||
cin >> n >> m;
|
||
// 筛质数
|
||
get_primes(2 * n);
|
||
int al, bl;
|
||
C(n + m, m, a, al); // C(n+m,m)，将高精度结果记录到a数组中,返回数组有效长度al
|
||
C(n + m, m - 1, b, bl); // C(n+m,m-1)，将高精度结果记录到b数组中
|
||
|
||
sub(a, al, b); // 计算a-b的高精度减法
|
||
|
||
// 输出结果，注意是倒序
|
||
for (int i = al; i; i--) printf("%d", a[i]);
|
||
return 0;
|
||
} |