Gym 101981G – Pyramid

题目链接:Gym – 101981G

这道题是去年南京区预赛的题,现场没有推出公式,到现在仍然不知道公式怎么推,但是最近从其他的推公式的题中得到了一些启发,总结了一些打表找规律的方法。

首先我们可以先建立一个平面直角坐标系,假设边长为$n$的三角形中有$d$个点,我们把$d$个点暴力枚举出来,然后$O({\rm C}_{n}^{3})$枚举多少个组合能构成等边三角形。

打表程序如下:

然后我们可以根据前几项的结果进行猜想,可以往三个方向考虑:

  • 多次差分之后为等差数列的,通项公式为多项式
  • 多次差分之后增长规律几乎不变并为指数级增长的,可能是齐次线性递推
  • 否则可能是非齐次线性递推

这里我们发现多次差分之后是一个等差数列,考虑待定系数求解多项式的系数,这里可以使用高斯消元的方法:

接着通过前七项解出了系数$(0, \frac{1}{4}, \frac{11}{24}, \frac{1}{4}, \frac{1}{24}, 0, 0, 0)$,得到:

$$f(x) = \frac{1}{4} x + \frac{11}{24} x^2 + \frac{1}{4} x^3 + \frac{1}{24} x^4 $$

最后通过多算几项验证正确性后,得到了最终的程序:

 

 

说点什么

avatar
50
  Subscribe  
提醒