BZOJ2822 [AHOI2012]树屋阶梯

求卡特兰数，h[i]=C(2n,n)/(n+1)

1 #include<bits/stdc++.h> 2 using namespace std; 3 int v[1005],p[1005],num[1005],n,cnt; 4 void pri() 5 { 6 for(int i=2;i<=n*2;++i) 7 { 8 if(!v[i])p[++cnt]=i; 9 for(int j=1;j<=cnt&&i*p[j]<=n*2;++j) 10 { 11 v[j]=1;if(i%p[j]==0)break; 12 } 13 } 14 } 15 void add(int x,int f) 16 { 17 int j=1; 18 while(x!=1) 19 { 20 while(x%p[j]==0)num[j]+=f,x/=p[j]; 21 j++; 22 } 23 } 24 struct node{ 25 int v[305],l; 26 node operator *(int x) 27 { 28 for(int i=1;i<=l;++i)v[i]=v[i]*x; 29 for(int i=1;i<=l;++i) 30 { 31 v[i+1]+=v[i]/10; 32 v[i]%=10; 33 if(v[l+1])++l; 34 } 35 return *this; 36 } 37 void print(){ 38 for(int i=l;i;--i) 39 printf("%d",v[i]); 40 } 41 }ans; 42 int main() 43 { 44 scanf("%d",&n); 45 pri(); 46 for(int i=n*2;i>n;--i)add(i,1); 47 for(int i=1;i<=n+1;++i)add(i,-1); 48 ans.v[1]=1;ans.l=1; 49 for(int i=1;i<=cnt;++i) 50 while(num[i]--)ans=ans*p[i]; 51 ans.print(); 52 return 0; 53 }

 

转载于:https://www.cnblogs.com/nbwzyzngyl/p/8361075.html

总结

以上是生活随笔为你收集整理的BZOJ2822 [AHOI2012]树屋阶梯的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。