火车进出栈问题
时间限制: 1 Sec 内存限制: 128 MB
题目描述
一列火车n节车厢，依次编号为1,2,3,…,n。每节车厢有两种运动方式，进栈与出栈，问n节车厢出栈的可能排列方式有多少种。
输入
一个数，n(n<=60000)
输出
一个数s表示n节车厢出栈的可能排列方式
样例输入
复制样例数据
3
样例输出
5 这道题目很烦，做对这道题目需要知道：
1.卡特兰数f的公式:
2.质因数分解。(几千位数，你一个个大数相乘就是在作死)
3.大数相乘。
一个整数，肯定是由多个素数组成，统计素数个数，然后用快速幂求各种素数乘积，最后每种素数再乘起来，就有了这个看似不会TL代码但TL了。哈哈。。。
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int n;
int f[60005][205];
int prim[11305], vis[120005], tot, num[120005], v[100005];
void get_prim(){
vis[1] = 1;
for (int i = 2; i <= 2 * n; i++){
if(!vis[i]) prim[tot++] = i;
for (int j = 0; j < tot && prim[j] * i <= 2 * n; j++){
vis[prim[j] * i] = 1;
if(i % prim[j] == 0) break;
}
}
}
void mul(int a[], int &num1, int b[], int &num2){
int c[100005];
memset(c, 0, sizeof(c));
for (int i = 0; i < num1; i++){
for (int j = 0; j < num2; j++){
c[i + j] += a[i] * b[j];
if(c[i + j] > 9) c[i + j + 1] += c[i + j] / 10, c[i + j] %= 10;
}
}
int len = num1 + num2;
while(c[len - 1] == 0) len--;
num1 = len;
for (int i = 0; i < len; i++) a[i] = c[i];
}
void pow_prim(int x[], int &cnt, int num){
int res[100005], len = 1;
//memset(res, 0, sizeof(res));
res[0] = 1;
while(num){
if(num & 1) mul(res, len, x, cnt);
mul(x, cnt, x, cnt);
num >>= 1;
}
cnt = len;
for (int i = 0; i < cnt; i++) x[i] = res[i];
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &n);
if(n == 1 || n == 0){
printf("1\n");
return 0;
}
get_prim();
for (int i = 2; i <= 2 * n; i++){
if(i == n + 1) continue;
if(i <= n){
if(!vis[i]) num[i]--;
else{
int t = sqrt((double) i);
int temp = i;
for (int j = 2; j <= t && j <= temp; j++){
if(vis[j]) continue;
while(temp % j == 0 && temp) num[j]--, temp /= j;
if(!vis[temp] && temp) num[temp]--, temp /= temp;
}
}
}else{
if(!vis[i]) num[i]++;
else{
int t = sqrt((double) i);
int temp = i;
for (int j = 2; j <= t && j <= temp; j++){
if(vis[j]) continue;
while(temp % j == 0 && temp) num[j]++, temp /= j;
if(!vis[temp] && temp) num[temp]++, temp /= temp;
}
}
}
}
int len = 1;
v[0] = 1;
for (int i = 0; i < tot; i++){
if(!num[prim[i]]) continue;
int t = prim[i];
int w[100005], cnt = 0;
while(t){
w[cnt++] = t % 10;
t /= 10;
}
pow_prim(w, cnt, num[prim[i]]);
mul(v, len, w, cnt);
}
for (int i = len - 1; i >= 0; i--) printf("%d", v[i]);
printf("\n");
return 0;
}
/**/
然后我在想，你即使用快速幂+大数相乘，但是你大数相乘为O(n^2)算法，是吃不消的。然后想到FFT，然后各种找资料，硬生生的没看懂，可能自己太菜了，（潜意识觉得O(nlogn)也过不了），然后我在想怎么把大数乘法降到O(n)，然后就想到一个int或者long long类型的数乘大数不就可以了吗，然后我担心超时，就直接弄了long long，降低大数相乘次数，虽然常数大，但是总比n^2快吧。。。然后就莫名其妙的过了。。。
/**/
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>
typedef long long LL;
using namespace std;
int n, tot, prim[66060], vis[120005], num[120005];
LL ans[50005];
void get_prim(){
for (int i = 2; i <= 2 * n; i++){
if(!vis[i]) prim[tot++] = i;
for (int j = 0; j < tot && prim[j] * i <= 2 * n; j++){
vis[prim[j] * i] = 1;
if(i % prim[j] == 0) break;
}
}
}
void mul(LL a[], LL num){
int len = a[0];
LL b[50005];
for (int i = 1; i <= 50000; i++) b[i] = 0;
for (int i = 1; i <= len; i++){
b[i] += a[i] * num;
if(b[i] > 9){
b[i + 1] += b[i] / 10;
b[i] %= 10;
}
}
while(b[len + 1]){
len++;
if(b[len] > 9){
b[len + 1] += b[len] / 10;
b[len] %= 10;
}
}
a[0] = len;
for (int i = 1; i <= len; i++) a[i] = b[i];
}
LL poww(LL x, int num){
LL res = 1;
while(num){
if(num & 1) res = res * x;
x *= x;
num >>= 1;
}
return res;
}
int main()
{
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
scanf("%d", &n);
get_prim();//先求出2*n内的素数
for (int i = 2; i <= 2 * n; i++){//然后统计每种素数的个数
if(i == n + 1) continue;
if(i <= n){
if(!vis[i]){
num[i]--; continue;
}
int t = sqrt((double) i), tt = i;
for (int j = 2; j <= t && j <= tt; j++){
if(tt % j != 0) continue;
while(tt % j == 0 && !vis[j]) num[j]--, tt /= j;
if(!vis[tt]) num[tt]--, tt /= tt;
}
}else{
if(!vis[i]){
num[i]++; continue;
}
int t = sqrt((double) i), tt = i;
for (int j = 2; j <= t && j <= tt; j++){
if(tt % j != 0) continue;
while(tt % j == 0 && !vis[j]) num[j]++, tt /= j;
if(!vis[tt]) num[tt]++, tt /= tt;
}
}
}
ans[0] = 1, ans[1] = 1;
for (int i = 0; i < tot; i++){
if(!num[prim[i]]) continue;
//cout << prim[i] << " " << num[prim[i]] << endl;
LL t = (1LL << 59) / prim[i];//以t个prim[i]为一组
LL tim = (LL)num[prim[i]] / t;
for (int i = 1; i <= tim; i++){
mul(ans, poww(prim[i], t));//用快速幂求出t个prim[i];
}
t = (LL)num[prim[i]] % t;//最后还剩下多少个prim[i]
mul(ans, poww(prim[i], t));
}
for (int i = ans[0]; i >= 1; i--) printf("%lld", ans[i]);
printf("\n");
return 0;
}
/**/
京公网安备 11010502036488号