题意：把一个正多边形分成数个三角形或者四边形，问有多少种方案。
题解：
如果分出的全为三角形的话，那就是正多边形三角剖分问题。它的结果就是Catalan数。现在也可以划分出四边形的话，可以采用动态规划策略。具体如下：
将n边形的顶点按顺时针或逆时针编号为1,2,3....n(n>=3),设T(n)为最终的结果,E(i,j)为i号顶点和j号顶点连成的对角线(1<=i<j<=n),我们定义T(2)=1.分两种情况讨论：
(1)边E(1,n)为划分后一个三角形的一条边。i为该三角形的另外一个顶点(2<=i<=n-1),因此，对角线E(1,i)和对角线E(i,n)将n边形分为1个i边形,1个由顶点(1,i,n)组成的三角形,1个(n-i+1)边形;这种情况下，问题规模缩小为小i边形，和(n-i+1)边形的。此时的种数为:
a=∑T(i)*T(n-i+1) (2<=i<=n-1)
(2)边E(1,n)为划分后一个四边形的一条边。i,j为该四边形的另外两个顶点(2<=i<=n-2,i+1<=j<=n-1)。1,n,i,j四个顶点将n边形分为1个i边形,1个j-i+1边形，1个n-j+1边形和该四边形。我们可以继续将i边形,j-i+1,n-j+1边形继续划分，规模也将继续缩小。此时的种数为：
b=∑∑T(i)*T(j-i+1)*T(n-j+1); (2<=i<=n-2,i+1<=j<=n-1)
故T(n)=a+b=∑T(i)*T(n-i+1)+∑∑T(i)*T(j-i+1)*T(n-j+1);
此时的时间复杂度为O(n^3),会TLE,我们可以将上述表达式写成以下形式以降低时间复杂度
U(n)=∑T(i)*T(n-i+1);(2<=i<=n-1)
T(n)=U(n)+∑T(i)*U(n-i+1);(2<=i<=n-2)
这样我们可以获得O(n^2).
关于对结果的取余，unsigned long long是自动对2^64取余的。
#include <cstdio> using namespace std; const int maxn=5005; unsigned long long a[maxn],b[maxn]; unsigned long long n; void init() { for(int i=0;i<3;i++) { a[i]=1; b[i]=1; } for(int i=3;i<=5000;i++) { a[i]=0; for(int j=2;j<=i-1;j++) a[i]=a[i]+b[j]*b[i-j+1]; b[i]=a[i]; for(int j=2;j<=i-2;j++) b[i]=b[i]+b[j]*a[i-j+1]; } } int main() { init(); while(scanf("%llu",&n)!=EOF) printf("%llu ",b[n]); return 0; }