#11 ARC104D
题目传送门
首先，看到平均值套路地做转化：给每一个数减去 \(x\)，然后求和。
转化后序列变成两段，每一段的值域都形如 \([1,r]\)。
那么我们考虑 dp 计数，定义 \(f_{i,j}\) 为考虑了小于等于 \(i\) 的数，且此时为 \(j\)。
转移是 naive 的，答案就是 \((k+1)\sum \limits_{i=1}^n\sum \limits_{j=1}^{n(n-1)/2}f_{i-1,j} \times f_{n-i,j}\)。
但是直接做是 \(O(n^3k^2)\) 的，非常不可过。
于是我们考虑前缀和优化多重背包。具体地，我们先当完全背包做一遍，然后我们考虑对 \(f_{i,j}\)来说，第 \(i\) 维上的有效贡献区间为 \([j,j-ki]\)，于是我们减去 \(f_{i,j-i(k+1)}\) 即可。
时间复杂度为 \(O(n^3k)\)，常数极小，时限充裕。
#12 ARC107D
题目传送门
巧妙转化！
我们考虑将集合内的元素按升序安排，例如 \(\{\frac{1}{16},\frac{1}{8},\frac{1}{2},\frac{1}{2}\}\)。那么我们可以把其视为由 \(\{1,1,1,1\}\)，在 \([1,1]\) 乘一个 \(2^{-1}\)，在 \([1,2]\) 乘两个 \(2^{-1}\)，在 \([1,3]\) 乘一个 \(2^{-1}\) 得到。也是说我们可以通过在若干个前缀上乘若干个 \(2^{-1}\) 得到。然后据此 dp 即可。
值得注意的是，因为结果是整数，所以我们在 dp 过程中可以忽略出现小数的情况。
时间复杂度为 \(O(n^2)\)。
#13 ARC197D
题目传送门
首先，我们要明确一件事：对于一对父子，与儿子在同一条链上的点不多于与父亲在同一条链上的点。（因为父亲可能有其他子树，这些子树内的点和该儿子不在同一条链上）。
因此，如果两个点 \((u,v)\) 有边，那么必然存在 \(a_u \cup a_v=a_u\) 或 \(a_v \cap a_u =a_v\)，且深度关系确定。
那么我们考虑 \(a_u=a_v\) 的情况，这时候这两个人谁当父亲都行，也就是说可以任意排列它们在链上的顺序。因此对于一个大小为 \(sz\) 的 \(a\) 相同的极大团，它对答案有 \(sz!\) 的贡献。
小细节：\(1\) 是所有人的祖先。
#14 P8136
题目传送门
首先，我们可以把任务分为“好任务”（可以获得倍增器的任务）和“普通任务”（不能获得倍增器的任务）。
那么我们观察到：一定存在一个任务顺序，使得我们先做好任务，再做普通任务。
证明：如果存在一个两个任务 \(i,j\)，且 \(i\) 是普通任务，\(j\) 是好任务，且 \(i\) 先于 \(j\) 做,我们设当前经验为 \(xp\)。那么有 \(xp \ge vd_i,xp+x_i\le vd_j-1\)；如果我们交换 \(i\) 和 \(j\) 的顺序，那么有 \(xp \le vd_j-1，xp+cx_j\ge vd_i\)。两个任务性质不变，因此交换不会变劣。
其次，我们再观察到：普通任务的顺序不影响最后经验值。
因为顺序只关系我们能否获得增幅器，既然已经不能获得增幅器了，那么顺序也就没有意义了。
最后，我们有一个惊人注意力：我们定义 \(mx_i=vd_i+cx_i-1\)，即做完任务 \(i\) 时可能的最大经验值，那么我们会优先做 \(mx_i\) 小的好任务。
证明：
我们假设存在两个好任务 \(i,j\)，\(i\) 先于 \(j\) 做且 \(mx_i>mx_j\)，那么可以推断：
那么我们要判断 \(xp+cx_j\) 和 \(vd_j-1\) 的大小关系，注意到：
因此交换 \(i\) 和 \(j\) 的顺序不会改变任务的性质，不会使答案变劣。
根据上述性质，我们按照 \(mx_i\) 给任务升序排序，那么依照这个顺序 dp 即可。
这个 dp 类似于背包，我们定义 \(f_{i,j}\) 为考虑到第 \(i\) 个物品，是否可以使从任务获得的经验为 \(j\)。转移时钦定当前物品是否在好物品集合中，这是简单的。找答案就倒序枚举 dp 数组，找到一个可以的经验值。
我们定义 \(m=nc \times\sum x_i\)时间复杂度为 \(O(nm+n\log n)\)，接近 \(1.6 \times 10^{13}\)，非常不可过。
考虑优化：
- 我们可以把好任务获得的经验分成 \(x_i\) 和 \((c-1)x_i\)，这样我们就可以只统计后面那部分的贡献。换句话说，我们可以只关心好任务的选取情况；
- 因为所有好任务提供的经验的都有 \(c-1\) 的系数，将其提出，可以降低值域大小；
- \(01\) 背包可以使用
bitset优化；
经过上述优化后，我们定义 \(m=n\times \sum x_i\)，时间复杂度为 \(O(\dfrac{nm+m \log m}{w})\)。
#15 CF587F
题目传送门
先考虑答案怎么求。因为包含一个字符串的串，在 fail 树上体现为这个串的结束节点及其子树。所以我们可以每一个字符串的结束节点及其子树加一，然后对字符串的每一个节点进行一次单点询问，权值和就是出现次数。
那么我们有两种答案统计方式：“统计”和“被统计”。
首先，我们考虑自己统计答案。我们把询问离线，然后类似扫描线地拆询问，然后每扫到一个串，就把它结束节点及其子树加一，然后做询问时直接枚举节点做单点询问，时间复杂度为 \(O(|s|\log m)\)。
然后，我们考虑让别人帮我统计。我们先把字符串上每一个点加一，然后枚举区间内的字符串，询问其结束节点及其子树的权值和，时间复杂度为 \(O(m\log m)\)。
那么我们考虑平衡复杂度，我们定义一个闸值 \(T\)：
-
若 \(s_i \le T\)，我们用第一个方式统计答案，时间复杂度为 \(O(n\log m+qT \log m)\)，使用分块可以做到 \(O(n\sqrt m+qT)\)。
-
若 \(s_i>T\)，我们用第二个方式统计答案，时间复杂度为 \(O(\dfrac{m^2}{T}+q \log m)\)。
那么时间复杂度为 \(O(\dfrac{m^2}{T}+qT\log m+q\log q+n\log m)\)，当 \(T=\dfrac{m}{\sqrt{q\log m}}\) 时取到最优时间复杂度为 \(O(n \log m+q \log q+m \sqrt{q\log m})\)。
#16 CF1110H
题目传送门
状态压缩好题。
我们先考虑如果确定一个大数，我们怎么统计答案。我们可以把 \([l,r]\) 内的每一个数都加入 ACAM，然后进行多模式串匹配。
如果 \(r-l+1\) 比较小呢？我们可以在 ACAM 上跑 dp。我们定义 \(f_{i,j}\) 表示长度为 \(i\) 且在 \(j\) 状态的最大权值，\(g_i\) 表示 \(i\) 状态的权值，那么有 \(f_{i,u} =\max \limits_{c,v=tr_{u,c}} f_{i-1,v}+g_u\)。\(g\) 数组的预处理是 \(fail_u\) 向 \(u\) 贡献。
但是本题 \(r-l+1\) 非常大，说明 ACAM 上节点非常多，我们没有办法朴素 dp。但是这是一个数位上的 ACAM，且插入的数连续，那么 Trie 上会有非常多的相同结构（也就是满十叉树），那么我们观察对于一个满十叉树，它无论怎么走贡献是确定的（只有叶子节点的贡献（因为只有这一个结束节点），也就是 \(1\)），这启发我们对这样的子树直接预处理它的贡献，然后直接砍掉。
具体地，我们考虑扩展 \(g\)。我们定义 \(g_{i,j}\) 表示在 \(i\) 状态后加 \(j\) 个字符可以获得的权值。因为 \(g\) 数组内的贡献是额外的，和 fail 树上祖先贡献是无关的（因为这里的贡献是子树内叶子节点的贡献，我们都没有建出这个节点，更不要说 fail 树上祖先对它的贡献了），所以我们可以提前加上。那么转移就变成：
显然你可以对 \(g\) 做一个前缀和实现 \(O(1)\) 转移，然后我们就可以考虑怎么预处理 \(g\) 数组了。
在 fail 树上的贡献是一样的，不再赘述；在开始时，我们考虑类似数位 dp 一样进行统计，看当前状态是否卡到上下界，如果都没有卡，那么就是满十叉树，可以直接记录贡献。
然后就一些小细节：
- 如果 \(l\) 和 \(r\) 的位数不同：我们就给 \(l\) 补零，然后强制 ACAM 的根节点不允许建 \(0\) 的出边。
- 找字典序最小的方案：我们考虑从后往前找答案状态的前驱，然后从前往后输出方案时优先走最小的字符即可。
#17 CF1988F
题目传送门
传奇计数题，充分展现了预处理的魅力。
因为求的是 \([1,n]\) 的答案，所以我们考虑能不能从 \(n-1\) 的答案推出 \(n\) 的答案。
因为前缀最大值个数和后缀最大值个数互不干扰，所以我们可以分开计数。我们定义 \(f_{n,i,j}\) 表示已经插入了 \([1,n]\)，且排列中有 \(i\) 个前缀最大值和 \(j\) 个上升点的方案数；类似地，我们定义 \(g_{n,i,j}\) 表示已经插入了 \([1,n]\)，且排列里有 \(i\) 个后缀最大值和 \(j\) 个上升点的方案。
由对称可以得到：\(g_{n,i,j}=f_{n,i,n-j-1}\)。因此我们只需要计算出 \(f\) 即可。
我们注意到题目中的定义都之和数的相对大小有关，因此我们可以这么考虑从 \(n-1\) 到 \(n\)：我们将所有数加一后，插入一个 \(1\)。因为插入的是 \(1\)，所以我们一定不会对原有的前缀最大值产生影响。此时我们来大力分类讨论一下：
-
把 \(1\) 放在一个上升点后或最后：那么此时我们拆开了一个上升点又产生一个新上升点（你可以理解为 \(1\) 替换掉了原上升点），也就是上升点数不变；如果放在最后，那么显然上升点个数不变。即 \(f_{n,i,j} \leftarrow f_{n-1,i,j} \times (j+1)\)。
-
把 \(1\) 放在第一个位置：那么此时 \(1\) 既是一个前缀最大值，又是一个上升点，即 \(f_{n,i+1,j+1} \leftarrow f_{n-1,i,j}\)。
-
把 \(1\) 放在其他位置：那么此时 \(1\) 会使后面的点变成上升点，即 \(f_{n,i,j+1} \leftarrow f_{n-1,i,j} \times(n-j-2 )\)。
那么直接做空间复杂度为 \(O(n^3)\)，但是我们注意到 \(i\) 转移时只需要 \(i-1\) 的值，因此可以滚动数组优化。
那么我们接下来考虑统计答案：
因为 \(n\) 是数列中最大的数，因此它既是前缀最大值又是后缀最大值，且其他前缀（后缀）最大值一定出现在 \(n\) 之前（之后），所以我们可以以 \(n\) 为界，把数组分为左右两部分。然后我们枚举其中一边的情况，然后就有：
\(O(n^6)\) 非常不可做，我们考虑降维。
我们注意到：\(f_{p-1,i,x}\) 和 \(a_{i+1}\) 只有三个不同的变量，也就是说我们可以在 \(O(n^3)\) 内把它们的积预处理出来，所以我们令 \(u_{i,x}=\sum \limits_{p=1}^if_{p-1,i,x}a_{i+1}\)；类似地，我们记 \(v_{j,y}=\sum \limits_{p=1}^{i}g_{n-p,j,y}b_{j+1}\)。
然后我们成功将原式简化为：
再观察，我们注意到 \(u_{p-1,x}\) 和 \(c_{x+y+[p>1]}\) 只有三个不同变量，于是我们记 \(w_{p,y}=\sum \limits_{x=0}^{p}u_{p,x}c_{x+y+[p>0]}\)（这里看似变化很大，其实也只是把 \(p-1\) 换成了 \(p\) 而已）。
于是我们就有一个最终的式子
#18 AGC027E
题目传送门
首先，这类变化很大的题目一般有某种比较强的不变量限制。
我们观察后发现：我们把 a 看成 \(1\)，把 b 看成 \(2\)，那么我们变换前后得到的字符串的权值 \(\bmod 3\) 的结果不变。
我们再观察可以发现：如果原串中存在一对相邻的相同字符，那么我们一定可以通过变化使得该串最后变为一个字符。
那么我们就把问题转化为：把原串划分为若干个子串，然后把每一段转化为一个字符，询问有多少中本质不同的字符串。
值得注意的是，我们在划分时并不要求子串内有相邻字符，因为如果该子串无法操作，那么我们可以把该子串和下一个子串合并，然后变成将该子串划分为两个合法子串的子问题，这个问题递归处理下去，最后一定存在合法的划分方式。
接下来就可以进行 dp 了。我们定义 \(f_i\) 表示原串上 \([1,n]\) 的划分方案数，\(a_i\) 为 \([1,i]\) 的字符串权值和。然后为了使本次划分的子串可以转化为一个字符，所以我们要从 \(a_i \neq a_j\) 的 \(j\) 转移过来；同时，为了保证我们不重复统计字符，我们钦定从上一个 \(a_j\) 转移过来。同时，如果 \([1,i]\) 可以转化为一个字符，那么我们可以直接操作，因为这样得到的字符串长度为 \(1\)，从其他位置转移过来得到的字符串长度至少为 \(2\)，可以保证不会重复计算。
#19 CF1305G
题目传送门
首先，我们考虑刻画操作 \(2\)。因为每一个点只能加入一次，且加入一个点后会给所有和它有连边的点染色。因此我们考虑是否可以通过生成树来刻画操作。
考虑一条边 \((u,v)\)，如果它被加入，那么它的贡献可能是 \(a_u\) 也可能是 \(a_v\)，这取决于加入该边时加入的是谁。
一个 Trick 是：我们把边权定义为 \(a_u+a_v\)，然后答案就是所有在生成树上的边的边权之和减去所有点权之和；特别地，我们开一个权值为 \(0\) 的虚点，然后向每一个点连边。
接下来贪心地从大到小枚举边权，然后枚举边的两边分别是谁，时间复杂度为 \(O(3^{18}\alpha(n))\)。