我受不了了。
Catalan数第100项，30000项，50000项，cnm
这tm哪里是在考数学，分明是在考高精度，FFT......
有剧毒！
我只得写高精度，只能过100的那个题，两个进化版超时......
#include <cstdio>
#include <string>
using namespace std;
const int N = ; int p[N], tp, sum[N];
bool vis[N]; struct LL {
string n;
LL operator * (const long long &x) const {
int a[N];
int t = n.size();
for(int i = ; i < t; i++) {
a[t - i - ] = ((int)(n[i] - '')) * x;
}
for(int i = ; i < t; i++) {
if(a[i] > ) {
a[i + ] += a[i] / ;
a[i] %= ;
if(i + == t) t++;
}
}
string f = "";
for(int i = ; i < t; i++) {
f = (char)(a[i] + '') + f;
}
LL ans;
ans.n = f;
return ans;
}
void out() {
for(int i = ; i < n.size(); i++) {
putchar(n[i]);
}
return;
}
}; void getprime(int b) {
for(int i = ; i <= b; i++) {
if(!vis[i]) {
p[++tp] = i;
}
for(int j = ; j <= tp && p[j] * i <= b; j++) {
vis[p[j] * i] = ;
if(i % p[j] == ) {
break;
}
}
}
return;
} inline long long pow(int a, int b) {
if(b < ) {
printf("ERROR!!!\n");
return ;
}
long long ans = ;
while(b) {
if(b & ) {
ans = ans * a;
}
a = a * a;
b = b >> ;
}
return ans;
} int main() {
int n;
scanf("%d", &n);
getprime(n << );
int n2 = n << ; for(int i = ; i <= tp; i++) {
int _i = p[i];
while(_i <= n2) {
sum[i] += n2 / _i;
_i *= p[i];
}
}
for(int i = ; i <= tp && p[i] <= n; i++) {
int _i = p[i];
while(_i <= n) {
sum[i] -= n / _i;
_i *= p[i];
}
}
n++;
for(int i = ; i <= tp && p[i] <= n; i++) {
int _i = p[i];
while(_i <= n) {
sum[i] -= n / _i;
_i *= p[i];
}
} LL ans;
ans.n = '';
for(int i = ; i <= tp; i++) {
ans = ans * pow(p[i], sum[i]);
}
ans.out();
return ;
}
AC代码