1.P7811 JRKSJ R2 你的名字。
不难，但是卡常 /tuu
首先对 \(k\) 根号分治，记阈值为 \(B_1\)，对序列分块，记阈值为 \(B_2\)。
对于 \(k \le B_1\) 的情况，可以直接枚举 \(k\)，然后转化成区间 min，这部分时间复杂度 \(O\left(nB_1 + m\left(B_2 + \dfrac{n}{B_2}\right)\right)\)。
对于 \(k > B_1\) 的部分，考虑将一个询问拆成对于每个 \(x\) 询问 \([l, r]\) 中 \(\ge kx\) 的最小值，一个询问会被拆成 \(O\bigg(\dfrac{V}{B_1}\bigg)\) 个。
改为从小往大加入后变成 \(O(n)\) 次单点改，\(O\bigg(\dfrac{mV}{B_1}\bigg)\) 次查询区间 min。
考虑先把 \([l, r]\) 在同一个块内的询问暴力做，这部分时间复杂度是 \(O(mB_2)\) 的。
然后剩下的询问都能被拆成一个块的后缀 min、一个块的前缀 min、一段块的区间 min。
考虑每个块维护前后缀 min，块间维护 ST 表，这样查询是 \(O(1)\) 的，修改 ST 表上只用改 \(O\bigg(\sum_{i \ge 0} \dfrac{n}{2^iB_2}\bigg) = O\bigg(\dfrac{n}{B_2}\bigg)\) 个位置，是 \(O\left(\dfrac{n}{B_2} + B_2\right)\) 的。
这部分总时间复杂度为 \(O\left(\dfrac{n}{B_2} \log \dfrac{n}{B_2} + mB_2 + \dfrac{mV}{B_1} + n\left(\dfrac{n}{B_2} + B_2\right) \right)\)。
总时间复杂度为 \(O\left( nB_1 + m\left(B_2 + \dfrac{n}{B_2}\right) + mB_2 + \dfrac{mV}{B_1} + n\left(\dfrac{n}{B_2} + B_2\right) \right)\)，当 \(B_1 = \sqrt V\)，\(B_2 = \sqrt n\) 时，时间复杂度为 \(O\big((n + m) \big(\sqrt n + \sqrt V\big)\big)\)。
卡常的话可以把 \(B_1\) 开大一点。
2.SPOJ2939 QTREE5 - Query on a tree V
挺简单的，直接点分树就做完了。
3.P6688 可重集
记区间 \([l, r]\) 的哈希值为：\(\sum_{i = l}^r g^{a_i}\)，这样就能快速至于平移 \(k\) 了。
不难发现 \(k = \min_{i \in [l_1, r_1]}(a_i) - \min_{i \in [l_2, r_2]}(a_i)\)，然后就做完了。
时间复杂度 \(O(n \log n)\)。
4.CF1801F Another n-dimensional chocolate bar
设 \(f_{i, j}\) 表示考虑了前 \(i\) 个，现在还要求 \(\prod_{x > i} b_x \ge j\) 时要求的式子的最大值。
转移为：
我们比较习惯向下取整，所以可以改写为：
\[f_{i, j} \rightarrow f_{i + 1, \lfloor\frac{j - 1}{k}\rfloor +1} \times \left\lfloor \frac{a_i}{k} \right\rfloor \times \frac{1}{a_i} \]算一下状态数。考虑转移两次后，不难发现：
\[\left\lfloor \frac{\left\lfloor \frac{x - 1}{a} \right\rfloor + 1 - 1}{b} \right\rfloor + 1 = \left\lfloor \dfrac{x - 1}{ab} \right\rfloor +1 \]这也就是说，我们 DP 状态的第二位一定是 \(\left\{ \left\lfloor \dfrac{k - 1}{x} + 1 \right\rfloor\right\}\)，也就是说第二维的大小是 \(O(\sqrt k)\) 的。
再算一下转移的时间复杂度：
\[O\left( \sum_{i = 1}^{\sqrt k} \sqrt i + \sqrt{\left\lfloor \frac{k}{i}\right\rfloor} \right) = O\left( \int_{1}^\sqrt k \left(\sqrt x + \sqrt{\frac{k}{x}} \right) \mathrm{d}x \right) = O\big(k^{\frac{3}{4}}\big) \]总时间复杂度 \(O\big(nk^{\frac{3}{4}}\big)\)。
5.CF504E Misha and LCP on Tree
先剖一下，然后每个询问就都被拆成了 \(O(\log n)\) 段字符串。
按 dfn 序正反建 SA，然后就能快速求出两段字符串的 LCP，双指针统计答案即可。
时间复杂度 \(O((n + q)\log n)\)。
6.CF914F Substrings in a String
bitset 字符串匹配。
正解是分块 SAM 支持修改，查询通过根号分治处理。
7.P1222 三角形 and P3219 HNOI2012 三角形覆盖问题
首先我们可以将 \(x\) 轴切成 \(O(n)\) 区间，使得每个区间中只有 \(O(n)\) 个梯形。
将三角形按 \(y\) 排序，扫描每个区间统计答案即可。
时间复杂度 \(O(n^2)\)。
还有一种 \(O(n \log n)\) 的做法。
首先按 \(x\) 排序，维护当前 \(y\) 轴上所有的不交的被覆盖的区间。
现在要做的就是三件事：
- 插入一个三角形。
- 删除一个三角形。
- 分裂一段区间。
可以用 set 维护。
插入的时候先把所有被它包含的删掉，然后再插入。
删除可以直接删。
分裂的话可以维护相邻两个三角形的交的大小，如果最小的为 0 就删掉原本的区间后再插入新的区间。
分析一下时间复杂度。
一个三角形最多被插入 1 次，所以插入的时间复杂度是 \(O(n \log n)\) 的。
同理，删除也是 \(O(n \log n)\) 的。
对于分裂，发现插入一个三角形最多会造成 2 次分裂，所以时间复杂度也是 \(O(n \log n)\) 的。
总时间复杂度 \(O(n \log n)\)。
8.P5291 十二省联考 2019 希望
过了！赢！
首先的第一想法是把包括每个点的答案算出来然后相加，但这样会算重。
但是你发现，对于一组方案， 它能到达的点一定是一个连通块，我们想让它只被算一次。这个可以点边容斥 \(1 = V - E\)。
也就是说，我们要把每个点和每条边的答案算出来相减。
考虑 DP：记 \(f_{u, i}\) 表示选出一个在 \(u\) 子树内且最远点与 \(u\) 距离不超过 \(i\) 的包含 \(u\) 的连通块方案数，\(g_{u, i}\) 表示选出一个在 \(u\) 子树内且最远点与 \(u\) 距离不超过 \(i\) 的包含 \(u\) 的连通块的方案数。
转移为：
然后点的贡献为 \((f_{u, L} g_{u, L})^k\)，\(u \rightarrow fa_u\) 这条边的贡献为 \(\big( f_{u, L - 1}(g_{u, L} - 1) \big)^k\)。
现在的问题是优化这个东西，显然要长链剖分。
记 \(dep_u\) 表示 \(u\) 到子树内离他最远的叶子的距离。
先考虑 \(f\)。发现虽然 \(f\) 第二位的范围是 \(O(n)\) 的，但是 \([dep_u, n]\) 这一部分的值都是相等的。
思考一下我们要支持什么操作：后缀乘，全局加，单点乘。
不难想到用带 \(\log\) 的数据结构维护，但是我们要线性。
对于后缀乘操作，我们对前缀的每个点乘上它的逆元，然后就变成全局乘了。
对于乘 0 的情况，我们可以维护 \((lim_u, val_u)\) 表示 \(f_{u, \ge lim_u} = val_u\)，然后能简单维护。
现在的问题是求逆元，不难发现需要求逆元的位置只有 \(f_{u, dep_u - 1}\)，所以可以预处理后 \(O(n)\) 求出所有逆元。
这样对 \(f\) 的转移就做到了线性。
然后考虑 \(g\)。发现 \(g\) 的第二位只需要维护 \([\max(0, L - dep_u), L]\) 即可转移。
考虑长儿子继承父亲的答案，短儿子暴力转移，这样就做到了 \(O\big(\sum dep_u\big) = O(n)\) 转移。
发现求 \(g\) 需要求 \(f\) 的前后缀乘积，而 \(f_u\) 的前缀乘积是 \(f_{fa_u}\) 做到 \(u\) 这个儿子前的值，后缀乘积我们可以简单维护，所以只需要支持对 \(f\) 的可撤销。
具体的说，我们先在求 \(f\) 的时候，把在每个点对 \(f\) 的影响记下来。
然后在求 \(g\) 的时候，按照和 \(f\) 相反的顺序做，每次把当前儿子的影响撤销，这样 \(f\) 中存储的就是前缀乘积。然后将对应儿子的 \(f\) 的值乘到长儿子的 \(g\) 上，这样长儿子的 \(g\) 中存储的就是当前的后缀乘积。
这样我们就实现了求前后缀积，剩下的按式子转移即可。
时间复杂度 \(O(n)\)。
9.P8557 炼金术（Alchemy）
考虑将每种金属往熔炉里放，这样方案数就是 \((2^k - 1)^n\)。
10.P5303 GXOI/GZOI2019 逼死强迫症
不难发现，如果固定了两个 \(1 \times 1\) 的砖块的位置分别为 \(l, r(r - l > 1)\)，那么第 \([l, r]\) 列的放法就固定了，第 \([1, l - 1]\) 和 \([r + 1, n]\) 列的方法是斐波那契数列。
所以答案的式子是：
如果记 \(S_n = \sum_{i = 0}^n \text{Fib}_i \text{Fib}_{n - i}\)，那么有：
\[\begin{aligned} ans &= 2 + 2 S_{n - 1} - 4 \text{Fib}_{n - 1} - 2\text{Fib}_{n - 2} \end{aligned} \]矩阵乘法即可。
时间复杂度 \(O(\omega^3 \log n + T \omega^2 \log n)\)，其中 \(\omega = 4\)。
11.P7706 「Wdsr-2.7」文文的摄影布置
首先观察到，因为求的是 \(\phi(l, r)\) 的最大值，所以 \(\min(B_j)\) 是没用的，因为取到最大时 \(B_j\) 一定最小。
然后就可以线段树简单维护了。
时间复杂度 \(O(q \log n)\)。
12.P6327 区间加区间 sin 和
直接线段树。
13.P5278 算术天才⑨与等差数列
判定条件是：
- 若 \(k \neq 0\)，\(\gcd(a_{l + 1} - a_l, a_{l + 2} - a_{l + 2}, \cdots, a_{r} - a_{r - 1}) \equiv 0 \pmod k\)。
- \(\max_{i \in [l, r]} a_i - \min_{i \in [l, r]} a_i = (r - l) \times k\)。
- 若 \(k \neq 0\)，\(a_{[l, r]}\) 互不相等。
直接线段树维护即可。
时间复杂度 \(O(n \log V + q(\log n + \log V))\)。
14.P6617 查找 Search
对每个 \(i\) 记 \(lst_i\) 表示 \(\max_{j < i \land a_j + a_i = w} j\)，查询就是查 \(lst\) 的区间 \(\max\)。
然后发现这样修改不了。
你发现你修改不了的原因是你会影响到下一个 \(a_i\) 之间的所有满足 \(a_j + a_i = w\) 的数，但是这些里面只有第一个是对答案有影响的，其他的一定不优，所以把其他的 \(lst_j\) 赋值为 0 即可。
时间复杂度 \(O((n + q) \log n)\)。
15.P4344 SHOI2015 脑洞治疗仪
区间覆盖，区间最长连续 0 子串。
16.P2572 SCOI2010 序列操作
。
17.P4146 序列终结者
。
18.P7738 NOI2021 量子通信
首先发现，由于 \(k \le 15\)，所以如果我们对每个串按 \(B = 16\) 分块，那么至少有一块询问串和字典串是相同的。
由于数据随机，对于查询串的一块，字典串中与这一块相同的串的期望个数为 6.103515625。
所以暴力枚举询问串的每个块，找字典串中与他相同的判断即可。
20.P8576 「DTOI-2」星之界
不难发现，操作二的答案是：
\[\binom{\sum_{i = l}^r a_i}{a_l, \cdots, a_r} = \frac{(\sum_{i = l}^r a_i)!}{\prod_{i = l}^r a_i!} \]只需维护区间和、区间每个数阶乘的乘积。
看到操作一不难想到分块，这部分是简单的。
注意每块的并查集不能对每个颜色维护，而是要对每个位置维护它与哪个位置颜色相等。如果按前一种方法维护，那么 \(x \rightarrow y\)，\(z \rightarrow x\) 之后 \(z\) 的颜色无法维护。
时间复杂度 \(O(q \sqrt n)\)。
21.P8321 『JROI-4』沈阳大街 2
相当于把 \(A\) 和 \(B\) 两两匹配，贡献为没对匹配较小的数的乘积。
所以我们把 \(A\) 和 \(B\) 拼起来，从大到小排序，在后面的数的位置计算贡献即可。
考虑 DP。设 \(f_{i, j}\) 表示前 \(i\) 个数，匹配了 \(j\) 对的贡献之和，转移为：
\[\begin{aligned} f_{i, j} &\leftarrow f_{i - 1, j} \\ f_{i, j} &\leftarrow f_{i - 1, j - 1} \times a_i \times \big(cnt_{1 - type_i, i - 1} - (j - 1) \big) \end{aligned} \]答案为 \(f_{n \times 2, n} / n!\)。
时间复杂度 \(O(n^2)\)。
22.P1641 SCOI2010 生成字符串
看成初始在 \((0, 0)\)，当前在 \((x, y)\)，如果选 0 就走到 \((x + 1, y - 1)\)，如果选 1 就走到 \((x + 1, y + 1)\)，最后在 \((n, n - m)\) 且纵坐标始终不小于 0 的方案数。
答案为 \(\binom{n + m}{m} - \binom{n + m}{m - 1}\)。
23.P3773 CTSC2017 吉夫特
先按 Lucas 定理分解一下。记 \(a_{b_i}\) 的二进制分解的第 \(j\) 位为 \(c_{i, j}\)，则有：
\[\prod_{i = 2}^k \binom{a_{b_{i - 1}}}{a_{b_i}} \equiv \prod_{i = 2}^k \prod_{j} \binom{c_{i - 1, j}}{c_{i, j}} \pmod 2 \]这就要求每个 \(\binom{c_{i, j}}{c_{i - 1, j}}\) 都不等于 0，也就是说 \(c_{i - 1, j} \ge c_{i, j}\)，也就是说如果把二进制看成集合，那么 \(a_{b_{i}} \subseteq a_{b_{i - 1}}\)。
考虑 DP。记 \(f_i\) 表示以 \(i\) 结尾的方案数，那么转移为：
\[f_{i} \leftarrow \sum_{j > i \land a_j \subseteq a_i} f_{j} \]可通过枚举子集做到 \(O\big(3^{\log V}\big)\)。
24.P8688 蓝桥杯 2019 省 A 组合数问题 and P6669 清华集训2016 组合数问题
先按 Lucas 定理分解一下 \(\binom{n}{m}\)，不妨 \(n = \sum_{i} a_i k^i\)，\(m = \sum_i b_i k^i\)，那么有：
\[\binom{n}{m} \equiv \prod_i \binom{a_i}{b_i} \pmod k \]那么 \(\binom{n}{m} = 0 \iff \exists i, a_i < b_i\)。
存在一个不好算，改为算 \(\forall i, a_i \ge b_i\)。
考虑数位 DP。设 \(f_{i, 0 / 1, 0 / 1}\) 表示考虑了高 \(i\) 位，\(a\) 贴 / 不贴上界，\(b\) 贴 / 不贴上界的方案数。
转移为：
其中：
\[\begin{aligned} \operatorname{calc}(n, m) &= \sum_{i = 0}^{n - 1} \sum_{j = 0}^{m - 1} [i \le j] \\ &= \begin{cases} \dfrac{n(n + 1)}{2} &, \text{if } n \le m\\ \dfrac{m(m + 1)}{2} + (n - m) m &, \text{else}\\ \end{cases} \end{aligned} \]时间复杂度 \(O\big(\sum \log_k n\big)\)。
25.P8594 「KDOI-02」一个仇的复
不难发现只有 \(x = 2\) 是特殊的，因为一个 \(2 \times 1\) 的矩形是可以竖着填的，其他的矩形都只能横着填。
所以考虑枚举 \(2 \times 1\) 的矩形个数 \(i\)，它将整个网格分隔成了 \(2 \times a_1, 2 \times a_2, \cdots, 2 \times a_j \ (\sum_{x = 1}^j a_x = n - i)\) 这些较小的网格。
不难通过插板得到分隔的方案数为：
现在的问题是计算每部分的方案数。
先考虑对于一个 \(2 \times n\) 的网格，如果只允许横着放 \(k\) 个矩形，那么有多少种方法。（这个是上面的子问题）
不难通过插板法得到答案：
第一步是枚举了第一行放多少个，第三步是通过范德蒙德卷积化简。
现在再考虑原问题，答案为：
\[\sum_{\sum_{x = 1}^j b_x = k - i} \prod_{x = 1}^j \binom{2a_x - 2}{b_x - 2} = \binom{n - 2i - 2j}{n - i - 2j} \]还是范德蒙德卷积。
此时，我们发现，在 \(i, j\) 相同时，对于每种 \(a\) 序列的答案都是一样的，所以我们只需要在求出 \(a\) 序列的方案数即可。
不难通过插板得到答案为：
所以答案就是上面三部分乘起来，即：
\[\sum_{i = 0}^k \sum_{j = 1}^{k + 1} \binom{i + 1}{j} \binom{n - i - 1}{j - 1} \binom{n - 2i - 2j}{n - i - 2j} \]但是我们还有一种情况没有考虑到，就是 \(n = k\) 时我们可以全放 \(2 \times 1\) 的矩形，所以真正的答案为：
\[\sum_{i = 0}^k \sum_{j = 1}^{k + 1} \binom{i + 1}{j} \binom{n - i - 1}{j - 1} \binom{n - 2i - 2j}{n - i - 2j} + [n = k] \]时间复杂度 \(O(n + k^2)\)。
26.P8367 LNOI2022 盒
先考虑如果已经知道了 \(b\) 数组怎样算答案。
考虑对每个 \(w_i\) 分别计算贡献。记 \(sa_i = \sum_{j = 1}^i a_j\)，\(sb_i = \sum_{j = 1}^i b_j\)。
则答案为:
不知道 \(b\) 的话可以枚举 \(sb\) 的每一项，剩下的是插板：
\[\sum_{i = 1}^{n - 1} w_i \sum_{j = 0}^S \lvert sa_i - j\rvert \binom{j + i - 1}{i - 1} \binom{S - j + n - i - 1}{n - i - 1} \]然后分类讨论拆绝对值，这里只讨论 \(j \le sa_i\) 的部分，这样就转化成了求两个式子：
\[\sum_{j = 0}^k \binom{j + i - 1}{i - 1} \binom{S - j + n - i - 1}{n - i - 1} \]\[\sum_{j = 0}^k j \binom{j + i - 1}{i - 1} \binom{S - j + n - i - 1}{n - i - 1} \]第二个式子的形式是显然不如第一个好的，所以考虑把 \(j\) 吸收进去，转成第一个，变成：
\[i \times \sum_{j = 0}^k \binom{j + i - 1}{i} \binom{S - j + n - i - 1}{n - i - 1} \]后面的那个式子调一下 \(n\) 和 \(S\) 就和第一个一样了。所以现在就只需要求第一个了，记其为 \(f(i, k)\)。
因为 \(i\) 和 \(k\) 都是单调的，所以考虑每次由 \(f(i, k)\) 变成 \(f(i + 1, k)\) 或 \(f(i, k + 1)\)。
变成 \(f(i, k + 1)\) 是简单的，现在主要是解决 \(i\) 加一时的情况。
考虑 \(f(i, k)\) 的组合意义：有 \(n\) 个盒子，要放 \(S\) 个小球，前 \(i\) 个盒子中至多放 \(k\) 个球的方案数。
这个可以转化成第 \(k + 1\) 个球恰好放在 \(i + 1\) 几之后的盒子里。这样可以枚举第 \(k +1\) 个球放的位置，也是个插板：
\[f(i, k) = \sum_{j = i + 1}^n \binom{j + k - 1}{j - 1} \binom{n - j + S - k - 1}{n - j} \]然后 \(i\) 加一就能做了。时间复杂度 \(O(T(n + S))\)。
**27.P4456 CQOI2018 交错序列
答案为：
\[\sum_{i = 0}^n \binom{i + 1}{n - i} i^a (n - i)^b \]然后 \(i^a\) 和 \(i^b\) 可以线性筛一下，这样就线性了。
28.P4562 JXOI2018 游戏
对于 \(l \le i \le r\)，如果 \(\max_{k \mid i \land k \neq 1}(i / k) < l\)，那么我们称 \(i\) 是一个关键点。
不难发现，对于一个排列 \(\pi\)，\(t(\pi) = \max_{\pi_i \text{ is a key node}} i\)。
考虑利用 \(sum = E \times cnt\) 来解决。
我们要求是关键点最大位置的和，不妨先求关键点最大位置的期望。
不妨记关键点的个数为 \(m\)。
对于一个非关键点，它在所有关键点之后的概率为 \(\dfrac{1}{m + 1}\)。
那么所有关键点之后的点数期望为：\(\dfrac{n - m}{m + 1}\)。
所以关键点最大位置的期望为：
最终答案为：
\[(n + 1)\frac{m}{m + 1} \times n! = \frac{m}{m+ 1}(n + 1)! \]关键点的个数可以线性筛出最小质因子然后计算。
时间复杂度线性。
29.P2606 ZJOI2010 排列计数
对于 \(i > 1\)，连边 \(\lfloor i / 2 \rfloor \rightarrow i\)，这样就形成了一棵外向树，我们要求的就是树的拓扑序数量。
答案为：
注意要把每个数表示成 \(am + b\) 的形式再进行乘除运算。
时间复杂度线性。
30.P8863 「KDOI-03」构造数组
记 \(m = \sum_{i = 1}^n a_i\)，先把 \(2 \nmid m\) 的情况判掉，然后令 \(m \leftarrow m / 2\)。
现在我们的问题是数长度为 \(m\) 的二元组序列 \((x_i, y_i)\) 表示我们第 \(i\) 次操作操作了位置 \(x_i, y_i\) 的数量。
此时我们的要求是 \(x_i < y_i, \sum_{i = 1}^n ([x_i = j] + [y_i = j]) = a_j\)。
不妨将第一个条件变为 \(x_i \neq y_i\)，我们最后将结果乘 \(2^{-m}\) 即可。
考虑容斥，钦定一个集合 \(S\) 满足 \(S\) 中的二元组满足 \(x_i = y_i\)，此时的容斥系数为 \((-1)^{\lvert S \rvert}\)。
现在的问题是算方案数。
考虑第二个条件，我们不妨记 \(c_i\) 表示钦定的二元组中 \(x_j = y_j = i\) 的数量，满足 \(\sum c_i = \lvert S \rvert\)。
那么贡献为：
其中第一个组合数是把钦定的位置分配到原序列中的方案数，第二个组合数是把未被钦定的位置分配到二元组中的方案数。
拆一下：
\[\begin{aligned} & (-1)^{\lvert S \rvert} \binom{m}{c_1, c_2, \cdots, c_n, m - \lvert S \rvert} \binom{2(m - \lvert S \rvert)}{a_1 - 2c_1, a_2 - 2c_2, \cdots, a_n - 2c_n} \\ = & (-1)^{\sum c_i} \frac{m!}{(m - \lvert S \rvert)! \prod c_i!} \frac{\big( 2(m - \lvert S \rvert) \big)!}{\prod (a_i - 2c_i)!} \\ = & m! \frac{\big( 2(m - \lvert S \rvert) \big)!}{(m - \lvert S \rvert)!} \frac{\prod (-1)^{c_i}}{\prod c_i! (a_i - 2c_i)!} \\ \end{aligned} \]不难想到记：
\[F_i(x) = \sum_{j} \frac{(-x)^j}{j!(2a_i - j)!} \]那么答案即为：
\[\frac{m!}{2^m} \sum_{s \ge 0} \frac{\big( 2(m - s) \big)!}{(m - s)!} [x^s] \prod_{i} F_i(x) \]暴力卷积可做到 \(O(m^2)\)，使用分治 NTT 可做到 \(O(m \log n\log m)\)。
31.P3266 JLOI2015 骗我呢
首先进行简单的观察，发现每一行都是 \(0, 1, \cdots, m\) 这个序列删掉了一些数。
如果记第 \(i\) 行删掉了 \(a_i\)，那么要求是 \(a_i > a_{i - 1} - 2\)。
考虑 DP，记 \(f_{i, j}\) 表示考虑了前 \(i\) 行，\(a_i \le j\) 的方案数。
转移为：
画一下转移的形态，发现答案等价于从 \((0, 0)\) 走到 \((n + m + 1, n)\)，每一步能向上或向右走，不经过 \(y = x + 1\) 和 \(y = x - (m + 2)\) 的方案数。
反射容斥即可。
时间复杂度 \(O(n)\)。
32.P3197 HNOI2008 越狱
。。。
33.P6692 出生点
不想写了。
34.P1450 HAOI2008 硬币购物
直接列 GF：
\[ans = [x^s] \prod_{i = 0}^3 \frac{1-x^{(d_i+1)c_i}}{1-x^{c_i}} \]然后暴力卷起来就行。
时间复杂度 \(O(ns)\)。
当然你可以把分子暴力展开一下，这样就是 \(O(s + n 2^w)\)，其中 \(w = 4\)。
35.P8290 省选联考 2022 填树
首先考虑枚举最小值 \(l\)，那么我们剩下的能填的最大值 \(r = l + k\)。
但是我们恰好取到最小值不好做，所以我们进行容斥 \([\min = l] = [\min \ge l] - [\min > l]\)。
那么现在我们要求的就是值域是 \([l, r]\) 的子集的方案数和权值和。
先枚举钦定的值域区间 \([l, r]\)，记 \(f_{u, 0 / 1}\) 表示 点 \(u\) 为根选一条链的方案数 / 点 \(u\) 为根的方案数，\(g_{u, 0 / 1}\) 表示 点 \(u\) 为根选一条链的权值和 / 点 \(u\) 为根的权值和。
考虑合并点 \(u\) 的儿子 \(v\)，记 \(w_1 = \vert [l_u, r_u] \cap [l, r] \cap \mathbb{Z} \rvert\)，\(w_2 = \sum_{i \in [l_u, r_u] \cap [l, r] \cap \mathbb{Z}} i\)，则转移为：
时间复杂度 \(O(nV)\)。
发现 \(w_1\) 可以表示成关于 \(l\) 的至多一次的分段多项式，\(w_2\) 可以表示成关于 \(l\) 的至多二次的分段多项式，每个点都会把左端点的值域分成至多 5 段，所以左端点值域总共被划分成了 \(O(n)\) 段，考虑对每段分别 DP。
考虑多项式次数上限。
先考虑 \(f\)。
固定一个 \(l\) 时，\(f\) 就相当于选一条链，把链上的点的 \(w_1\) 乘起来，这个是至多 \(n\) 次的。
然后我们对 \(l\) 做了一个前缀和，这个是至多 \(n + 1\) 次的。
所以 \(f\) 的次数不超过 \(n + 1\)。
再考虑 \(g\)。
固定一个 \(l\) 时，\(g\) 就相当于选一个点，把这个点的 \(w_2\) 乘上这个点的贡献次数，贡献次数就是分别从以这个点为根时的两棵不同的子树中选一条链，将他们的 \(w_1\) 乘起来，这个是至多 \(n + 1\) 次的。
然后我们对 \(l\) 做了一个前缀和，这个是至多 \(n + 2\) 次的。
所以 \(g\) 的次数不超过 \(n + 2\)。
直接拉插可以做到 \(O(n^3)\)。
还有一种常数更好的做法，是从第一篇题解里看到的，我实现了一下发现确实跑的飞快。
就是你考虑直接维护这个多项式，记 \(F_{u, 0 / 1}(x)\) 表示 \(f_{u, 0 / 1}\) 对应的多项式，\(G_{u, 0 / 1}(x)\) 表示 \(g_{u, 0 / 1}\) 对应的多项式，转移和上面的一样，时间复杂度就是树形背包的 \(O(n^2)\)。
现在要做的就是已知 \(f(x) = \sum_{i = 0}^n a_ix^i\)，求 \(\sum_{x = 0}^{r} f(x)\)。
先变一下求和顺序：
然后要求的就是 \(\sum_{x = 0}^r x^k\)：
\[\begin{aligned} \sum_{x = 0}^r x^k &= \sum_{x = 0}^r \sum_{i \le k} \begin{Bmatrix} k \\ i \end{Bmatrix} x^{\underline i} \\ &= \sum_{i \le k} \begin{Bmatrix} k \\ i \end{Bmatrix} \sum_{x = 0}^r x^{\underline{i}} \\ &= \sum_{i \le k} \begin{Bmatrix} k \\ i \end{Bmatrix} i! \sum_{x = 0}^r \binom{x}{i}\\ &= \sum_{i \le k} \begin{Bmatrix} k \\ i \end{Bmatrix} i! \binom{r + 1}{i +1} \end{aligned} \]这样就能 \(O(n^2)\) 求了。
所以时间复杂度为 \(O(n^3)\)，但是常数会小很多。
36.P3746 六省联考 2017 组合数问题
我太唐了。下文基本 copy 自 https://www.luogu.com.cn/article/knllx86m。
\[\begin{aligned} \sum_{i} \binom{nk}{ik + r} &= \sum_{i \bmod k = r} \binom{nk}{i} \\ &= \sum_{i \bmod k = r} [x^i](x+1)^{nk} \\ &= [x^r] \big( (x + 1)^{nk} \bmod (x^k - 1) \big) \end{aligned} \]然后循环卷积快速幂，时间复杂度 \(O(k^2 \log n)\)。