我不会啊。 感觉是若干套路的集合。 首先显然有 。对于 的情况下，可以计算所有 的值，用莫反或者子集反演计算 的值。 这里提一下用子集反演替代一部分莫反的情况。当你要求的函数只和质数集合 有关的时候，那么可以使用子集反演代替莫反。核心原理是在 的情况下，一个数不同质数的个数不会超过 个，稍后我们来讲解一下如何用这个解决这个题目。 但这个题目由于有 次幂的影响，我们很难将 暴力展开计

神在哪里。 首先这意味着只有最后一层是不满的，可以散着一些叶子。否则你可以把最深的叶子往上提一层。 然后根据 BST 一个节点对应一个区间的规则，不难想到一个区间 DP。 表示值域在 之间，根节点奇偶性是偶数/奇数的情况。转移是枚举一下最后一层分给左侧几个叶子，右侧几个叶子，算出根节点，然后根据根节点奇偶性做转移。 然后有一个观察，就是你发现给值域整体加上一个 是不会破坏奇偶性要求的。因此后文

感觉远古 和现在 难度差远了。 不妨先考虑没有限制的情况。 首先对于这种问题，可以考虑转化成一个序列上的问题。 其实就是，有长度为 的序列 和长度为 的序列 ，有两种匹配方式： 匹配 ，对应横放的骨牌。 匹配 ，对应竖放的骨牌。 此时可以考虑做一个容斥原理。但是实际上你发现并不是很好容斥。 继续考虑，不妨考虑如何生成一组匹配。可以先考虑进行一些 的匹配，然后对于每个 的匹配，

好题。 首先考虑最简单的区间 DP， 表示在横坐标 ，纵坐标 的最小复杂度，每次转移的时候枚举一下切割线，每次取 即可做到 的复杂度。 你会发现这个复杂度显然不太能接受。 我们考虑优化。不妨分析一下这个复杂度有什么性质。 直觉上来说，肯定是越大的矩形复杂度就越大。形式化的说，如果一个矩形的复杂度为 ，那么在这个矩形的基础上任意增加一行或者一列，新的矩形的复杂度至少是 。 证明比较无脑，直接数

看上去是要维护一个二维数组，支持区间平移。但是仔细观察后你发现向下的平移只会在最后一列出现。 因此我们实际上只需要支持最后一列的向上平移，和行的向左平移即可。 平衡树做法 对于这种区间平移的问题有一种比较无脑的做法就是直接平衡树。 更具体的，我们对于每行的前 个元素和最后一列的 个元素开一颗平衡树。 每次我们删除第 行的平衡树的第 个元素，将最后一列对应的平衡树的第 个元素插入到最后。然

非常有趣的题目。 首先观察样例，不妨猜测蛇一定是对称的（这点我们稍后证明）。因此我们可以将这个正方形砍掉一半只保留左上角。 考虑对角线上的点，每个点必然不同的蛇。这是因为一条蛇只能往右侧和下方走，所以一条蛇不可能同时占有一个格子和一个格子右上角的格子。 因此，我们考虑为每个对角线上的格子分配一个长度，其对应的棋盘结果是唯一的。因为你只能贴着边界摆放。 比如考虑这张图，如果这样摆放，那么 两个点

非常好题目。 我们考虑计算出所有可行的答案最后除以 来计算出答案。 考虑一个简单的 dp 设计。令 表示前 个数进行了 次加法操作所得到的方案数。 转移是每次加入一个数或者直接乘转移到下一个位置。你发现这个复杂度直接爆炸了，因为 的范围是 。 我们希望把状态从 中踢出去。 考虑使用乘法分配律。但是暴力展开之后实际上并不好处理。我们继续观察一下，考虑每次操作对每个位置产生的影响，也就是下

▶INFO 题意简述 有 个格子，每个格子有一个参数 。有一枚棋子初始在第 个格子，力量值为 。有两名玩家轮流操作这个棋子，假设当前棋子在第 个格子，当前玩家可以选择增加最多 的力量值，然后将棋子移动不超过当前力量值的距离（不能原地不动）。先到 的玩家获胜。

写完这篇题解就去睡觉。 上来经典套路，方差等于平方的均值减去均值的平方，对应到这里就是 。 我们来考虑如何计算一下这两个东西。 首先是 。考察 是 之间均匀独立分布的随机变量， 那么 。我们注意到实际上 的分布是一样的，因此这两个期望也是一样的。 就是 。考虑全期望公式。 维护一下前缀和即可。 接下来是 。我们如法炮制。 前面的 我们继续用全期望公式展开之后是 。想之前那样维护一个前缀

▶INFO 题意 给定 个字符，第 个字符的代价是 ，现在你需要用这 个字符构造出 个互相不为前缀的字符串，使得总共的权值和最小。字符串的权值是所有字符的权值和。 我们发现这个等价于在一棵无限大的 Trie 树上找到 个叶子节点，使得叶子