本期还是《计算之魂》主题赛——不得不说，该系列比赛的编程题质量都还不错。本期两道编程题，至少对我来说，还是挺难的。
前面选择题就不说了，本期问哥特意花了点时间翻书——我就不信找不到答案了。
填空题再次出现，一个月后围观打脸。
但是，C站还是延续了填空题必出妖的传统，标准答案给的 44，明显错了。如果大家能够读懂题意的话，本题其实就是上台阶（斐波那契数列）的进阶版。“加到”某个数，可以理解为到达某层台阶 n，而到达的上一步可以是 3 步（n - 3）之前、2步（n - 2）之前、1步（n - 1）之前。这三个地方都可以 1 步到达台阶 n。于是可以把问题转化为到达这三个地方的递归求解，最后将所有方案汇总，于是可列递归代码如下：
def fun(n):
if n == 1: return 1
if n < 1: return 0
return fun(n-3)+fun(n-2)+fun(n-1)我注意到讨论群中有人在争论 fun(1) 应该等于 0，理由是题目是“从1开始”，所以“加到”1的方法数是0。我只想说，这里的 return 1 和 return 0 其实可以理解为该位置可达与否，最终得到的结果是可达的计数 —— 当然在python里，由于数据的弱类型，换成 return True 和 return False，该代码可以直接运行。
再怀疑的话，穷举出来就可以证明了吧。使用深搜算法穷举所有方案如下：
编程题。两题都很有挑战性。
第一题、取石子
虽然看得出来是区间DP，但转移方程的思维难度不小。本题也是上古原题：[ZJOI2009]取石子游戏 - 洛谷
大家可以自行查阅题解——虽然未必能一下子搞懂。
由于本题只有两个答案，非“Yes”即“No”。而周赛的用例，直接 print(“Yes”) 即可通过70%，于是问哥果断选择骗分通过。等以后有空，再仔细研究研究。
第二题、勾股定理困难版
官方给的题解如下图：
反正我是没看懂，数学好的同学可以解析一下再出份详细题解。
在这里问哥简要说一下自己野路子的思路：
由于 z 很大很大（后面的 0 数不清），所以穷举 必定超时，无法通过，只能从寻找勾股数的规律入手。
结合经验并简单查阅资料就可以发现（前面都翻书了，还有什么不能查资料的？），一组勾股数（x、y、z）具有如下规律：
- 斜边 z 为偶数时，该组勾股数必然全是偶数——不存在互质；
- 斜边 z 为奇数时，该组勾股数的 x 和 y 必然一个是奇数、一个是偶数。
当 z 为偶数时，所有满足条件的勾股数组合，一定都可以约分成互质的勾股数。比如当 ，满足条件的组合有（30,40,50）、（14,48,50），可以分别约分成为互质的（3,4,5）、（7,24,25）。于是，我们要找斜边为 z 的勾股数组合，等价于寻找所有互质的勾股数组合——这些组合中的斜边都是 z 的奇因数。所以我们只要分析，当 z 的奇数因子（偶数不存在互质的勾股数）分别作为新的斜边时，各存在多少互质的勾股数组合（也可能一个都没有），再将这些组合数累加在一起即可。
于是，问题转化成，对 z 的所有奇数因子进行穷举互质勾股数组合，再进行累加。
但是这样仍然会超时，因为根据 z 的奇数因子简单穷举某条边的话，复杂度仍然和 z 是同一个级别。于是我又注意到，当 z 为奇数时，勾股数还存在下面这两个规律：
- 斜边 z 减去偶数边，得到的奇数，必然是某奇数的平方，如1、9、25等；
- 斜边 z 减去奇数边，得到的偶数，必然是某偶数的平方的一半，如2、8、18等。
此处设 a 为某奇数，b 为某偶数，则上面两个规律可以表示为
很显然，通过枚举 a 或 b（二选一即可，因为第三条边可以通过 得到），可以将复杂度降低至 z 的平方级，通过C站的测试就没有问题了。
最后别忘记，由于我们只枚举了一条边（奇数边或偶数边），所以还要把得到的组合数乘以2（两条边互换），才是最终答案。
就酱紫吧，走运又拿了名次，德不配位。下次还是低调点吧，免得又被别人说抄袭。