---	预期	实际	delta
A	100	55	-45
B	100	0	-100
C	100	100	0
D	100	100	0
E	100	10	-90
F	0	0	0
G	0	0	0
H	0	25	+25
总计	500	290	-210

A 亲密数对

数据范围较小，可以枚举每个数验证，\(O(n\sqrt n)\)，枚举因数的时候注意\(\sqrt n\)只能算一次需要特判

B 吉祥数

模拟(万万没想到竟然真的有函数叫pow，直接编译错误爆零)

C 二叉树输出

和前两天先序中序求后序的题异曲同工，需要特别关注有无左右子树的判断

D 关系网络

BFS板子

E Fibonacci 前n项和

前期推导有点耗时，写矩阵挺快，就是数组不开long long ，亲人两行泪
可以用累加法
\(f_{n}=f_{n-1}+f_{n-2}\)
\(f_{n-1}=f_{n-2}+f_{n-3}\)
\(\vdots\)
\(f_{3}=f_{2}+f_{1}\)
左右两边加起来得到\(f_{n}=f_{1}+...+f_{n-2}+1\)即\(f_{n}=S_{n-2}+1\)
故本题相当于求\(f_{n+2}-1\)，矩阵快速幂即可

好了，接下来是本次考试的重灾区

F 数三角形

容斥的思想， \(C_{(m+1)*(n+1)}^3\)的合法方案减去横着，竖着，斜着的共线的不合法方案
重点在于求斜着不合法的方案数，由于上下对称，我们只求向右上方倾斜的方案数，最后乘2

• 需要知道一个结论：对于两个纵坐标差i，横坐标差j的点，它们中间的斜线会经过\(\gcd(i,j)-1\)个整点
• 而对于每一对确定的i,j,都有(n-i+1)(m-j+1)种摆放方式，所以一共会造成(n-i+1)(m-j+1)*(\(\gcd(i,j)-1\))种方案的贡献
• 于是总共斜着不合法方案数是：

\[\displaystyle \sum^{n}_{i = 1}\displaystyle \sum^{m}_{j = 1}(n-i+1)*(m-j+1)*(\gcd(i,j)-1) \]

到这里算是个\(O(n*m\log n)\)的算法，过这道题是相当轻松，然而精益求精的巨巨们求出了\(O(n)\)的算法，需要涉及到一些数学知识

根据我们小学二年级就学过的欧拉函数的性质: \(∑ _{d∣n}φ(d)=n\)

于是原式可以改为

\[\displaystyle \sum^{n}_{i = 1}\displaystyle \sum^{m}_{j = 1}(n-i+1)*(m-j+1)*(∑ _{d∣\gcd(i,j)}φ(d)-1) \]

再利用φ(1)=1,又可化为

\[\displaystyle \sum^{n}_{i = 1}\displaystyle \sum^{m}_{j = 1}(n-i+1)*(m-j+1)\displaystyle \sum^{d\neq1}_{d∣\gcd(i,j)}φ(d) \]

那么这样有什么好处呢？

观察\(d∣\gcd(i,j)\) ，这个式子的意思就是d是i与j 的因数，所以可以将d提出来，i变为\(i\ast d\)，j变为\(j\ast d\),原式变为

\[\displaystyle \sum^{\min(n,m)}_{d=2}φ(d) \displaystyle \sum^{⌊n/d⌋}_{i = 1}\displaystyle \sum^{⌊m/d⌋}_{j = 1}(n-i\ast d+1)*(m-j\ast d+1) \]

\[=\displaystyle \sum^{\min(n,m)}_{d=2}φ(d) \displaystyle \sum^{⌊n/d⌋}_{i = 1}(n-i\ast d+1)\displaystyle \sum^{⌊m/d⌋}_{j = 1}(m-j\ast d+1) \]

其中\(\displaystyle \sum^{⌊n/d⌋}_{i = 1}(n-i\ast d+1)\)是个等差数列求和，其值为

\[((n-d+1)+(n-⌊n/d⌋\ast d+1))*⌊n/d⌋=0.5\ast (n+1-d+n\mod d+1)*⌊n/d⌋ \]

这个式子是可以\(O(1)\)求的，对m做相同处理，最终式子如下

\[\displaystyle \sum^{\min(n,m)}_{d=2}φ(d)\ast 0.5\ast (n+1-d+n\mod d+1)*⌊n/d⌋\ast 0.5\ast (m+1-d+m\mod d+1)*⌊m/d⌋ \]

其中欧拉函数用线性筛预处理是\(O(n)\)，总复杂度\(O(n)\)

G 加工生产调度

安排的顺序对后面产品的加工没有影响，我们可以仿照国王游戏的方式用临项交换的方式考虑贪心(其实有一道和这道很像的题：皇后游戏)

假设先后加工第i与第i+1件产品，总用时\(a_{i}+\max(b_{i},a_{i+1})+b_{i+1}\)，交换后总用时
\(a_{i+1}+\max(b_{i+1},a_{i})+b_{i}\)，即\(sum-\min(b_{i},a_{i+1})\)与\(sum-\min(b_{i+1},a_{i})\)

如果不交换有\(sum-\min(b_{i},a_{i+1})<sum-\min(b_{i+1},a_{i})\)，移项得到\(\min(b_{i},a_{i+1})>\min(b_{i+1},a_{i})\)

其实这个式子已经可以贪了，但它用来排序本身是错误的，后面这一块我不是太懂，直接把讲得好的巨佬的链接挂上来：点这

H 灯泡

数学22题 这题主要是要考虑定义域，设人与灯泡的水平距离为d,总影长y

• 当影子直接投到地上时，\(y_1=\frac{hd}{H-h}\)，由\(d+y_1<=D\)得出这一段的定义域\(0\leq d\leq \frac{D(H-h)}{H}\),最大值\(\frac{hD}{H}\)

• 当影子有部分在墙上时 投在地上的影子长度\(y_3=y_1+d-D\)，墙上影长用相似算的是\(y_4=\frac{y_3}{y_1}h\),化简出来\(y_2=y_3+y_4=H+D-[\frac{D(H-h)}{d}+d]\)，定义域\(\frac{D(H-h)}{H}\leq d\leq D\)

• 中括号里面是对勾函数，当且仅当\(d=\sqrt{D(H-h)}\)取等

• 于是

\[\left\{ \begin{aligned} y_{2max}&=D-(H-h)\frac{D}{H} \ \ (\sqrt{D(H-h)}\leq H)\\ y_{2max}&=H+D-2\sqrt{D(H-h)} \ \ (\frac{D(H-h)}{H}<\sqrt{D(H-h)}\leq D)\\ y_{2max}&=h \ \ (D\leq \sqrt{D(H-h)}) \end{aligned} \right. \]

结合以上两个函数求解即可，参考题解(有精美配图) :点这