题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2822
题意：求卡特兰数第 n 项。
写 SAM 写累了来写个压位玩一玩。详细题解这里懒得写了...luogu 那里提交了一发废话比较多的，不知道能不能通过...
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 1010 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; const int W=9; const int bit=1000000000; #define MAX_LEN 1000 struct big { int len; ll x[MAX_LEN]; ll& operator [](int a) {return x[a];} friend void operator *=(big &a,int b) { int len=a.len; for(int i=1;i<=len;i++)a[i]*=b; int now=1; while(now<=len) { if(a[now]>=bit)a[now+1]+=a[now]/bit,a[now]%=bit; if(now==len&&a[len+1])len++; now++; } a.len=len; } void print() { for(int i=len;i>=1;i--) if(i==len)printf("%lld",x[i]); else printf("%09lld",x[i]); } }ans; int c[N]; void add(int x,int v) { for(int i=2;i*i<=x;++i) while(x%i==0)x/=i,c[i]+=v; if(x!=1)c[x]+=v; } int main() { n=read(); for(int i=n+2;i<=n+n;++i)add(i,1); for(int i=1;i<=n;++i)add(i,-1); ans[1]=ans.len=1; for(int i=1;i<=n+n;++i) while(c[i])ans*=i,--c[i]; ans.print(); return 0; } |
Comments | NOTHING