C

已知多校某题的思路，就变成签到了

D

找规律

像是被脑筋急转弯卡住了脑子。

题意：给定一个n乘m的矩阵，每个位置表示九宫格内有几个雷（包括自己的位置），问总共有几个雷

解：

当时想了各种方法，都被自己X了，比如高斯消元、网络流、单纯形、贪心……

结果是个sb题。显然某一个点的值表示九宫格内有几个雷，那么只要找到一些九宫格，使得它们之间互不重复、它们覆盖了整个棋盘，答案就是这些九宫格的中心之和。

教训：

当对某道题的方向迷茫，但是又有不少人A的时候，应当从小数据开始，尝试发现一些自己脑子被门夹的地方

题意：求
$$
S = (a + \sqrt b)^n + (a - \sqrt b)^n
$$
解：

将$x+y\sqrt{b}$表示成$(x,y)$的形式，那么$n=1$时显然左边为$(a,1)$右边为$(a,-1)$。

因为$(x_1,y_1)\cdot (x_2,y_2)=(x_1x_2+y_1y_2b,x_1y_2+x_2y_1),(x_1,y_1)+(x_2,y_2)=(x_1+x_2,y_1+y_2)$，利用快速幂直接计算即可。

感觉我自己以前是用过一模一样的方法A过题目的…但是最近脑子确实是不够活

题解：
$$
由通项公式知，递推公式为S_n=2aS_{n-1}+(b-a^2)S_{n-2}
$$
怎么推的待补

需要常系数线性递推相关知识吗？

题意：给定n，p，q以及n个点，选出两个点使得斜率最接近(p/q)

解：显然按照与某条斜率p/q的直线的距离排序，斜率最接近的必然是相邻的两个点