打完了。不算别的东西大概是115minAK的。
T1
题目大意：给你一坨字符，计算每个字符的ASCII码的积
其实刚一开看见这道题是有点慌的，以为要把所有特殊字符写出来。
但其实把一个字符强转成 int\tt{int}int 就是其 ASCII 值了，简单。
然后注意到本题需要高精度，需要写一个高精乘低精。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
时间复杂度：O(∣s∣2)O(|s|^2)O(∣s∣2)。
体感难度：橙。
T2
题目大意：求第 lll 年至第 rrr 年之间的闰年个数。
直接求 [l,r][l,r][l,r] 之间的闰年个数是复杂且麻烦的，需要处理很多边界情况。
不妨利用前缀和的思想，计算区间 [1,r][1,r][1,r] 和 [1,l−1][1,l-1][1,l−1]，相减即为 [l,r][l,r][l,r]。
然后考虑怎么求 [1,x][1,x][1,x]。闰年的规律是“四年一润，百年不润，四百年再润”。所以答案为 x4−x100+x400\frac{x}{4}-\frac{x}{100}+\frac{x}{400}4x −100x +400x 。
时间复杂度：O(1)O(1)O(1)。
体感难度：红
T3
题目大意：不可描述
简单的区间 DP\tt{DP}DP。定义 f(l,r)f(l,r)f(l,r) 表示目前这个人能不能赢。
初始状态 f(i,i)=1f(i,i)=1f(i,i)=1，就剩一个字符肯定能赢。
然后对于题目中四种操作分别转移即可：
* 1. DP 跑两边，跨度为 111。
* 2. 直接DP收缩。
* 3. DP 跑两边，跨度为 222。
* 4. DP跑幸运字符那边，跨度为 111。
时间复杂度：O(T×∣S∣2)O(T\times|S|^2)O(T×∣S∣2)
体感难度：黄。
T4
求哈密顿路径是否存在
这个问题请读者自行学习一部分。
哈密顿路径，就是说在一个有限的网格图里面，从一个格子开始，能否不重不漏的走完所有格子。也就是本题问的。
首先如果总的格子数为奇数，对于所有格子 (i,j)(i,j)(i,j)，此时 i+ji+ji+j 是偶数的格子比 i+ji+ji+j 是奇数的格子要多一个，此时你要看的是 x+yx+yx+y 的奇偶性，x+yx+yx+y 必须是偶数，你才能走出来这样的路径。
否则总格子数是偶数，对于随便一组 x,yx,yx,y，(x,y)(x,y)(x,y) 的上下左右至少有一个方向距离为偶数个格子，一定能走出一条“蛇形”的哈密顿路径。
注意 n=1,m=1n=1,m=1n=1,m=1 的狭长网格图是个特例，你必须在这个网格左右其中一端才行。
时间复杂度：O(T)O(T)O(T)。
体感难度：黄。
T5-EX
难度还是有的，感觉没有大家说的那么不堪）也可能是我太蠢了。
虽然题目中没有明确给出，但是 O(nm)O(nm)O(nm) 不超时的显然可以朴素 DP\tt{DP}DP 解决。
下文中 C(N,M)C(N,M)C(N,M) 表示组合数，NNN 个里面选 MMM 个。
对于正解：考虑计算所有经过了 (i,j)(i,j)(i,j) 的路径。方案数显然为 C(i+j−2,i−1)×C(n+m−i−j,n−i)C(i+j-2,i-1)\times C(n+m-i-j,n-i)C(i+j−2,i−1)×C(n+m−i−j,n−i)。这个读者应该能理解。
然后，我们令 x=i+jx=i+jx=i+j，所有 i+j=xi+j=xi+j=x 的 (i,j)(i,j)(i,j) 的总贡献为：
f(x)=∑i=max(1,x−m)min(n,x−1)C(x−2,i−1)×C(n+m−x,n−i)f(x)=\sum_{i=max(1,x-m)}^{min(n,x-1)} C(x-2,i-1)\times C(n+m-x,n-i) f(x)=i=max(1,x−m)∑min(n,x−1) C(x−2,i−1)×C(n+m−x,n−i)
读者自证不难读者自证不难读者自证不难对不起懒得写具体化简过程。当你把式子化简，你就会发现这个式子的值与 xxx 无关！变成了 C(n+m−2,n−1)C(n+m-2,n-1)C(n+m−2,n−1)。也就是说对于每个质数带来的贡献都是 C(n+m−2,n−1)C(n+m-2,n-1)C(n+m−2,n−1)。
分析到这里就豁然开朗，答案为 1∼n+m1\sim n+m1∼n+m 的质数个数 ×C(n+m−2,n−1)\times C(n+m-2,n-1)×C(n+m−2,n−1)，于是预处理质数筛算质数，预处理阶乘和逆元计算出组合数，本题就可以阿里嘎多妈妈哈哈的AC掉了。记得取模哦。
时间复杂度：O(n+m)O(n+m)O(n+m)
体感难度：绿上蓝下。
另外，不要抄我的代码哦，留了点小惊喜，抄了肯定过不了。但是不影响观看
