自动搬运

查看原文

来自洛谷，原作者为

	魁拔 None

搬运于2025-08-24 21:24:22，当前版本为作者最后更新于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一个数，因此除法不适用（当然也可以用某种复杂方法解决，这里不展开），所以建议用方法二。

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