题解 P1375 【小猫】

魁拔 · 2013-07-13 18:06:46 · 题解

本题等同于多边形三角剖分问题，详情请见旧版人教版数学教科书七年级下册第86页

公式如下：a[n+1]:a[n]=4n-6:n(注：a[3]的值等于本题a[1]的值，以此类推)

递推式如下：a[i]:=a[i-1]*(4*i-2) div (i+1);

亦可用公式a[i]:=0.5*(∑(j:=3 to i-1) a[j]*a[i-j+2]);

从答案上也可以看出这题和栈是一样的，但考虑到数据非常大，要mod一个数，因此除法不适用（当然也可以用某种复杂方法解决，这里不展开），所以建议用方法二。

鉴于本人用的是第一种方法，第二种方法公式对不对就不保证了，可以试着自己推一推