2018-2019 ACM-ICPC, Asia Nanjing Regional Contest G.Pyramid（找规律 + k阶差分）

题目链接

题意：请看到题目那张图。一个n阶三角形，从中任选三个点，能构成三角形的方案数。

题解：先说说我找到的一个递推的规律：

首先对于一个n阶三角形，那么它内部存在三个（n-1）阶三角形，这三个三角形就会有重复的三个（n - 2）阶的三角形，根据容斥定理此时我们还要加上一个内部（n-3）阶三角形。最后还要加上i：n阶这个大三角形，n阶内部最大的倒三角形，以及题面给的那种能斜着放的三角形，其实最大倒三角形就是斜三角形的一种。具体看下图。

 

最后推出的式子就是 F【i】 = 3 * （F【i - 1】 - F【i - 2】） + F【i - 3】+ i；

交了一发矩阵快速幂，一发超时。 

用来打表 ：1 5 15 35 70 126 210 330 

进行差分得 ： 1 4 10 20 35 56 84 120

再差分 ：3 6 10 15 21 28 36

继续差分 ：3 4 5 6 7 8

最后得到一这玩意，冥冥中感觉有规律，可就是无法触及，看来我与这个公式注定无缘。

正在懵逼的时候，队友猜了一个公式直接AC，wtf？？？秀了我一脸，队友实在太强。

公式是n * (n + 1) * (n + 2) * (n + 3) / 24 。这个式子的推导过程请戳我。

代码就不贴了，注意要求逆元。