由于都是 CF 上非赛时做的题，因此所有代码都可以去 CF 上找我的账号 zimujun 的 submission 查看。
每道题的标题上有题目链接。
1559E Mocha and stars
*2200，考察基本数论函数性质、背包 dp 和前缀和优化的综合应用，属于综合性较强的基础题。
求有多少长度为 (n) 的序列 ({a_i}) 满足 (forall i in [1, n]capmathbb Z, l_i le a_i le r_i, displaystylesum_{i = 1} ^ n a_i le m, gcd(a_1, a_2, cdots, a_n) = 1)。
(n le 50, l_i le r_i le m le 10 ^ 5)。
后面那个 dp 求解就好，由于上界只到 (lfloordfrac{m}{t} floor) 因此总的复杂度是 (O(nmln m)) 的。
具体的，设 (f(i, j)) 表示在前 (i) 个数中选出的总和为 (j) 的方案数，显然有 (displaystyle f(0, 0) = 1, f(i, j) = sum_{k = lceilfrac{l_i}{t} ceil} ^ {lfloorfrac{r_i}{t} floor} f(i - 1, j - k))，不难发现后面这个转移可以一个前缀和搞掉，最后答案即为 (displaystyle sum_{i le lfloorfrac{m}{t} floor} f(n, i))。
1550E Stringforces
*2500，考察二分和状压，同时涉及部分贪心策略的应用，解法较为巧妙。
要求使得最小值最大，可以考虑二分一个限制指 (len)，要求这 (k) 种字符连续出现的最大次数都大于 (len)，然后判断这个限制值是否合法。
可以考虑然把这 (k) 个长度为 (len) 的连续段放入字符串的一个前缀，因为当没有别的限制的时候，我们肯定会选择贪心地加入，使得已经加入的前缀尽可能短，可以证明这样的构造方案一定不会更劣。
但是现在有确定字符的限制，而且不同种类字母的限制不同（被除了当前种类字字母在内的所有其他字母限制）。看到 (k le 17)，考虑状压。
设 (f(S)) 表示已经加入的字母种类集合为 (S) 时所占前缀的最小长度。通过枚举往集合中新加入的字符刷表转移。最后判断 (len) 是否合法即可转化为判断 (f({1,2,cdots,k}) le n) 是否成立，考虑如何优雅地实现这个转移。
做一个预处理，设 (next(i,j)) 表示从第 (i) 个位置，放长度为 (len) 的第 (j) 种字母的连续段，可以放到的最小右端点位置。倒序枚举 (i)，如果后面 (len) 长度内出现了除了 ? 和第 (j) 种字母之内的其他字符（通过维护已经扫过去的每一种字符最靠左的位置实现即可），那就把 (next(i, j)) 赋值为 (next(i + 1, j))，如果没有出现，那就是 (i + len)。这样处理一遍的复杂度为 (O(nk))。
完成这个预处理，我们就可以实现这个转移了。
枚举状态和字符转移即可，复杂度为 (O(k2^k))。
总的复杂度为 (O((nk + k2^k)log n))。
1246C Rock is Push
*2200，考察对题目性质的发现和使用 dp 求解问题的能力。
前几天 vp 的时候没做出来的一道题。
看起来很 npc 的题意，没想到是个 dp，后来一想，如果把方案数按下一步向左还是向下走区分开，那么这样确实满足无后效性。
然后一个前缀和优化就做完了。
很有意思的一道题。
（要是具体做法还不太明白的话私戳我吧）