A
求所有长度为 \(n(n\leq10^6)\) 且满足条件的小写字母字符串 \(S\)。
- 存在至少三个不交的连续子串 \(T = \mathbf{shs}\)
定义 \(f(i,j,k)\) 表示对于长度为 \(i\) 的字符串，满足已经存在 \(k\) 个连续子串，且最后 \(j\) 位与，\(T\) 的前 \(j\) 位相同。
直接 DP 即可，考虑该状态能从何处转移而来，方程见代码。
#define irep(i,l,r) for(int i = l; i <= r; ++i)
f[0][0][0] = 1;
irep(i,1,n){
f[i][0][1] = f[i-1][0][0] + f[i-1][0][1];
f[i][0][2] = f[i-1][0][1];
f[i][0][0] = f[i-1][0][0] * 25 + f[i-1][0][1] * 24 + f[i-1][0][2] * 25;
f[i][1][0] = f[i-1][1][0] * 25 + f[i-1][1][1] * 24 + f[i-1][1][2] * 25 + f[i-1][0][2];
f[i][1][1] = f[i-1][1][0] + f[i-1][1][1];
f[i][1][2] = f[i-1][1][1];
f[i][2][0] = f[i-1][2][0] * 25 + f[i-1][2][1] * 24 + f[i-1][2][2] * 25 + f[i-1][1][2];
f[i][2][1] = f[i-1][2][0] + f[i-1][2][1];
f[i][2][2] = f[i-1][2][1];
g[i] = f[i-1][2][2] + g[i - 1] * 26;
irep(j,0,2)irep(k,0,2)f[i][j][k] %= mod;
g[i] %= mod;
}
B
给一个 \(n\times m\) 的矩形网格黑白染色，定义一个染色方案是好的，当且仅当任意相邻两行的颜色对应恰好相同或对应恰好相反，求所有恰好染黑 \(k\) 个格子的染色方案数\((1\leq n,m\leq10^7)\)
不考虑染色数为 \(k\) 的限制，如果某一个状态是好的，那么把它某一列或者某一行取反一定也是好的，已知全白是一个好的状态，实际上所有合法的状态就是选定某一些行，选定某一些列，把它们取反。设选 \(c_1\) 行，\(c_2\) 列，那么染黑的方格数为 \(c_1(m-c_2)+c_2(n-c_1)=k\)，可以枚举 \(c_2\)，解得 \(c_1=\dfrac{k-n\cdot c_2}{m-2c_2}\)，它应当是在区间 \([0,n]\) 之中的整数。那么这种情况下的方案数为 \(\large\binom{n}{c_1}\binom{m}{c_2}\) ，特殊的，当分母 \(m-2c_2=0\) 时，原式化为 \(mn=2k\)，故这种情况需要单独考虑，此时无论 \(c_1\) 为何值，式子都成立；若 \(mn\neq 2k\) ，则都不成立。
值得注意的是，选择行列的方案不是染色方案，因为对于所有选择取反，染色结果不变，答案要乘以 \(0.5\)。
- \(C_n^m=\binom{n}{m}\) 表示组合数
C
对 \(n\cdot (n-1)^2\cdot(n-2)^3\cdots 1^{n}\) 分解质因数 \(n\leq 10^7\)
首先， 设 \(n!\) 的分解为 \(p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_m^{\alpha_m}\) ，则 \(\alpha_i=\left\lfloor\dfrac{n}{p}\right\rfloor+\left\lfloor\dfrac{n}{p^2}\right\rfloor+\left\lfloor\dfrac{n}{p^3}\right\rfloor+\cdots\)，其证明显然，第一项表示 \([1,n]\) 中为 \(p\) 的倍数的数，第二项表示为 \(p^2\) 的倍数的，如果 \(t\) 是恰好是 \(p^r\) 的倍数，那么恰好会做出 \(r\) 次贡献。
于是，对于每一个质数 \(p\)，即求 \(\sum\limits_{i=1}^n\alpha_{i}=\sum\limits_{i=1}^{+\infty}\left(\sum\limits_{j=1}^n\left\lfloor\dfrac{j}{p^i}\right\rfloor\right)\) ，括号里的式子可以直接求，实际上时间复杂度为 \(O(n)\)，瓶颈在筛质数，因为只有为质数次幂的数才会计算答案。
D
有两条长度为 \(n\) 的项链，每个珠子有一个颜色；有 \(m\) 种魔法，每个魔法可以花费 \(c\)，能把一个颜色 \(u\) 变成 \(v\)；随机把项链旋转，然后染色，使得珠子的颜色对应相等，求最优策略下花费的期望。\(n\leq10^5,m\leq10^6,u,v\leq400,c\leq100\)
对于颜色变换建图，跑 Floyd，把 \(u,v\) 变成同样颜色的最小代价就是 \(W(u,v)=\min\limits_kdis(u,k) + dis(v,k)\) ，考虑所有的旋转方案，\(E=\frac{1}n\sum\limits_{u=1}^n\sum\limits_{v=1}^n W(u,v)\) ，按值域考虑即可。
E
扫一遍，存每个颜色的上一个的位置，新添加一个颜色，可以求出与上一个的距离。判断与 \(K\) 的关系即可。
F
有 \(n\) 批敌人，每一批有 \(c\) 个血量为 \(h\) 的敌人。你可以选择两种攻击方式，你需要依次打败所有的敌人，求最小用时
- 普通攻击：花一秒减少一个敌人的一点血量
- 特殊攻击：花零秒减少一个敌人的 \(k\) 点血量
初始状态可以使用特殊攻击，当使用过特殊攻击后将不能使用，但是如果杀死某个敌人的最后一击是普通攻击，则能够恢复使用特殊攻击的能力。
定义 \(f(i,0/1)\) 为消灭前 \(i\) 批敌人，且消灭之后 能够/不能够 使用特殊攻击的最小时间。
如果 \(h\geq k+1\)，杀死一个敌人可以立即恢复特殊攻击：\(f(i,0/1)=\min \{(h-k)\cdot c+f(i-1,0),(h-k)\cdot c+k+f(i-1,1) \}\)
如果 \(h\leq k\)，那么如果使用特殊攻击将会一击必杀，需要对 \(c\) 分奇偶讨论：
若 \(c\) 为奇数
考虑 \(f(n,0)\)：若开始能够使用特殊攻击，则为使用特殊攻击的方案是 YNYNN，第 \(i\) 个字符为 Y 表示对第 \(i\) 个敌人使用特殊攻击；若不能使用，则方案为 NYNYN
考虑 \(f(n,1)\)：若开始能够使用特殊攻击，则为使用特殊攻击的方案是 YNYNY，若不能使用，则方案为 NYNNY
若 \(c\) 为偶数
考虑 \(f(n,0)\)：若开始能够使用特殊攻击，则为使用特殊攻击的方案是 YNYN，若不能使用，则方案为 NYNN
考虑 \(f(n,1)\)：若开始能够使用特殊攻击，则为使用特殊攻击的方案是 YNNY，若不能使用，则方案为 NYNY
根据以上讨论，可以列出 DP 方程，详见代码：
int main(){
ll f0 = 0, f1 = 0;
ll n = read(), k = read();
irep(i,1,n){
ll ht = read(), c = read();
ll g0, g1;
if(ht > k)g0 = g1 = min(f0 + c * (ht - k), min(f0,f1) + (c - 1) * (ht - k) + ht);
else{
int a = c / 2;
if(c & 1){
g0 = min(f0,f1) + (a + 1) * ht;
g1 = min(min(f0,f1) + (a + 1) * ht, f0 + a * ht);
}else{
g1 = min(f0,f1) + a * ht;
g0 = min(f0 + a * ht, min(f0,f1) + (a + 1) * ht);
}
}
f1 = g1, f0 = g0;
}
cout << min(f1,f0);
return 0;
}