这玩意不是卡特兰的经典模型吗……
我们设方案数为f(i)，则f(0)=1,f(1)=1，f(2)=2,f(3)=5，（其实到这里你再手模一个就出来了）我们把左上角的矩形删掉，则会变成下方和右方两个更小规模的问题（如果没有就是f(0)喽），拿样例举例f(3)=f(2)的一种情况*f(0)+f(2)的另一种情况*f(0)+f(1)*f(1)+f(0)*f(2)的一种情况+f(0)*f(2)的另一种情况，总结一下，f(3)=$∑_{i=0}^{2}f(i)*f(2-i)$，对所有情况进行归纳，则得到Cat数O(n^2)的那个递归的式子。
至于算的时候，直接O(n)唯一分解接高精就搞定了，（至于你不懂什么叫O(n)唯一分解，你可以去看代码或上一篇博客）。
#include<iostream> #include<algorithm> #include<cmath> #include<cstring> #include<cstdio> #include<vector> #include<queue> #include<stack> #include<set> #include<map> using namespace std; int n,prime[1000],prime_num; bool v[1050]; struct Bigint{ int a[10000],len; void clear(){ memset(a,0,sizeof(a)); len=1; a[1]=1; } friend void operator *(Bigint &x,int y){ int delta=0; for(int i=1;i<=x.len;i++){ x.a[i]=x.a[i]*y+delta; delta=x.a[i]/10; x.a[i]%=10; } while(delta>0){ x.a[++x.len]=delta%10; delta/=10; } while(x.a[x.len]==0&&x.len>1) --x.len; } void out(){ for(int i=len;i>=1;i--) printf("%d",a[i]); } }ans; void doprime(int x){ for(int i=2;i<=x;i++){ if(!v[i]) prime[++prime_num]=i; for(int j=1;j<=prime_num&&i*prime[j]<=x;j++){ v[i*prime[j]]=1; if(i%prime[j]==0) break; } } } int main(){ scanf("%d",&n); doprime(2*n+2);ans.clear(); for(int i=1;i<=prime_num;i++){ long long s=0; for(int j=2*n;j/=prime[i];) s+=j; for(int j=n;j/=prime[i];) s-=j; for(int j=n+1;j/=prime[i];) s-=j; for(int j=1;j<=s;j++) ans*prime[i]; } ans.out(); return 0; }
至此Cat三题吸收完毕。
原文：https://www.cnblogs.com/Yu-shi/p/11222580.html
