P1173 [NOI2016] 网格

你需要将某些跳蚤替换成蛐蛐，使得在此之后存在至少两只跳蚤不四连通。且最小化替换个数。 $T \leq 20$，$n, m \leq 10^9$，$\sum c \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/32368512) 我们考虑寻找从上往下，从左往右找到第一个不是蛐蛐的位置。将它与其他部分不连通至多需要替换 $2$ 次。 所以若答案存在，一定 $\leq 2$。 答案 $=0$ 是很平凡的。 答案 $=1$，相当于图存在割点。也即：对于每个蛐蛐的四周上的点，寻找是否存在另一个蛐蛐与这个点八连通。若存在，那么这个点是一个割点。 [CF750H](https://www.luogu.com.cn/problem/CF750H) 有类似的套路，感觉是最水的 3500 分题。 # [P1587 [NOI2016] 循环之美](https://www.luogu.com.cn/problem/P1587) 求有多少数值不同的 $x, y$ 满足 $1 \leq x \leq n, 1 \leq y \leq m, \frac xy$ 在 $k$ 进制下是纯循环小数。 $n, m \leq 10^9$，$k \leq 2 \times 10^3$。 *** [评测链接](https://www.luogu.com.cn/record/31531825) 题意转化为 $$\begin{aligned}&\sum_{i=1}^n\sum_{j=1}^m [\gcd(i, j)=1][\gcd(j, k)=1]\\ =&\sum_{i=1}^n\sum_{j=1}^m[\gcd(j, k)=1]\sum_{d|\gcd(i, j)}\mu(d)\\ =&\sum_{d=1}^n[\gcd(d, k)=1]\mu(d)\sum_{i=1}^\frac nd \sum_{j=1}^ \frac md[\gcd(j, k)=1]\\ =&\sum_{d=1}^n[\gcd(d, k)=1]\mu(d)\lfloor \frac nd\rfloor \sum_{j=1}^ \frac md[\gcd(j, k)=1]\end{aligned}$$ 设 $S_n=\sum_{i=1}^n [\gcd(i, k)=1]$。这是很好算的，因为 $\gcd(i, k)=\gcd(i\bmod k, k)$，所以循环节为 $k$。 则答案为 $$\sum_{d=1}^n[\gcd(d, k)=1]\mu(d)\lfloor \frac nd \rfloor S_{\frac md}$$ 设 $T_n=[\gcd(i, k)=1]\mu_i$。如果能求出 $\sum_{i=1}^nT_i$，我们就可以整除分块。 设 $R_n=[\gcd(i, k)=1]$，则 $R*T=\epsilon$。 $$\sum_{d|n}[\gcd(d, k)=1][\gcd(\frac nd, k)=1]\mu(d)=[\gcd(n, k)=1]\sum_{d|n}\mu(d)=[n=1]$$ 于是我们可以杜教筛了。 时间复杂度：$O(k+n^{\frac 23})$。 # [P1721 [NOI2016] 国王饮水记](https://www.luogu.com.cn/problem/P1721) 第 $i$ 个城市有 $h_i$ 的水。 每次操作可以指定若干个城市，让他们的水都变成平均值。 求至多 $k$ 次操作后，$1$ 号城市最高的水位。 $n \leq 8000$，$k \leq 10^9$。 *** [评测链接](https://www.luogu.com.cn/record/38134693) 我们肯定是选择比 $1$ 号城市水位高的若干城市参与合并。所以一个城市若和 $1$ 进行了连通，它将不会再被使用。为了让每个城市都尽其用，我们肯定按 $h$ 从小往大合并。因为首先合并一个大的可能会让若干小的失效。由此我们得出，将 $h$ 排序后，$k$ 次合并都应该是一个区间 $[l_i, r_i]$，且 $r_i <l_{i+1}$。 同时我们发现，大于 $1$ 号城市水位的城市，一定都会被使用。也即 $r_i+1=l_{i+1}$。考虑反证法，若 $r_i+1<l_{i+1}$，我们在第 $i$ 次加入第 $r_i+1$ 个城市一定更优（因为平均值不超过最大值，最大值是 $h_{r_i}$，假如一个不比平均值低的数平均值一定不减）。 设 $f_{i, j}$ 表示前 $i$ 座城市，进行了 $j$ 次操作后，$1$ 号点最高的水位。$s_i$ 表示前 $i$ 座城市的 $h$ 之和。 $$f_{i, j}=\max\{\frac{f_{l, j-1}+s_i-s_l}{i-l+1}\}$$ 非常典型的斜率优化式子。 至于高精度小数，我们可以先用正常的浮点数进行计算，记录决策，最后用高精度计算即可。 # [P1971 [NOI2011] 兔兔与蛋蛋游戏](https://www.luogu.com.cn/problem/P1971) 这些天，兔兔和蛋蛋喜欢上了一种新的棋类游戏。 这个游戏是在一个 $n$ 行 $m$ 列的棋盘上进行的。游戏开始之前，棋盘上有一个格子是空的，其它的格子中都放置了一枚棋子，棋子或者是黑色，或者是白色。 每一局游戏总是兔兔先操作，之后双方轮流操作，具体操作为： * 兔兔每次操作时，选择一枚与空格相邻的白色棋子，将它移进空格。 * 蛋蛋每次操作时，选择一枚与空格相邻的黑色棋子，将它移进空格。 第一个不能按照规则操作的人输掉游戏。 现在给定一个长度为 $k$ 的操作序列。 求出所有在这次操作前兔兔有必胜策略，而这次操作后蛋蛋有必胜策略的操作位置。 $n, m \leq 40$，$k \leq 1000$。 *** [评测链接](https://www.luogu.com.cn/record/32393328) 首先，网格图是二分图，所以白色棋子和空格子在网格图上为同色点，或者黑色棋子和空棋子在网格图上为异色点，都是无意义的。 这样，我们就让黑色点上只有黑色棋子，白色点上只有白色棋子。 问题变为，在二分图上走增广路，不能走的人输。问必胜策略。 这是一个经典的问题：二分图博弈。有一道与其类似但更难的[题](https://loj.ac/p/536)。 对于该问题有定理： 起点 $v$ 必胜当且仅当 $v$ 在所有的最大匹配上。 证明： * 必要性：反证，若存在一个最大匹配没有包含 $v$，那么先手要么无路可走，要么走到了右侧的匹配点上（不可能走到非匹配点，不然我们找到了一条增广路，与最大匹配矛盾），后手只用走到左侧对应的匹配点即可。 * 充分性：增广路定理有推论：对于无向图 $G$ 和其任一最大匹配 $M$，点 $v$ 必定在最大匹配上，当且仅当对于 $M$，$v$ 在匹配上且不存在以 $v$ 为一端的偶数条边的交替路。 于是，我们取任意最大匹配 $M$，现在先手把 $v$ 移动到 $M$ 中与之匹配的点上。那么由于不存在以 $v$ 为一端的偶数长度交替路，移动后并删去点 $v$ 的图中也不存在增广路，于是由增广路定理从 $M$ 中删去先手走的边后仍然是最大匹配，且现在 $v$ 在未匹配点上。于是情况和必要性证明中相同，先手必胜。 于是，我们只用判断空格子是否在所有的最大匹配上。 我们建出删去空格子和不删空格子的两张二分图，判断最大匹配是否相等即可。 # [P1973 [NOI2011] NOI 嘉年华](https://www.luogu.com.cn/problem/P1973) 有 $2$ 个会场和 $n$ 个活动，每个活动在一个会场内在时间 $[S_i, T_i]$ 举行。两个会场不能同时有活动，一个会场内可以同时进行多个活动，活动可以不举行。 问，强制第 $i$ 个活动举行，举办活动少的会场举办活动个数的最大值。 *** [评测链接](https://www.luogu.com.cn/record/33147255) 设 $c_{i, j}$ 表示 $[l, r] \in [i, j]$ 的活动个数。$O(n^3)$ 预处理。 设 $f_{i, j}$ 表示最后一个活动在第 $i$ 个时刻或之前结束，总共进行了 $j$ 个活动，另一个会场最多能进行多少活动。 $$f_{i, j} = \max_k(f_{k, j-c_{k+1, i}}, f_{k, j}+c_{k+1, i})$$ $g$ 表示第一个活动在第 $i$ 个时刻或之后结束。 $f, g$ 的计算是 $O(n^3)$ 的。 强制第 $i$ 个活动选时： $$\textrm{ans}=\max_{i=0, j = r, x=0, y = 0}^{i \leq l, j \leq m, x \leq n, y \leq n}\min(x + y + c_{i, j}, f_{i-1, x}+g_{j+1, y})$$ 复杂度 $O(n^5)$。 可以对于每个 $i, j$ 预处理 $\max_{x=0, y = 0}^{x \leq n, y \leq n}\min(x + y + c_{i, j}, f_{i-1, x} + g_{j+1, y})$，复杂度 $O(n^4)$。 发现 $f_i$ 非增，$g_i$ 非降，双指针即可。$O(n^3)$。 # [P2012 拯救世界2](https://www.luogu.com.cn/problem/P2012) 有 $4$ 种元素可以任意选，$4$ 种元素只能选偶数个，$4$ 种元素只能选奇数个，选 $n$ 个构成序列，求不同的序列的个数。 $n \leq 2^{63}-1$，$T \leq 2\times 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/30808310) 三种元素的 EGF： $$\sum_{i=0}^\infty \frac {x^i}{i!}=e^x$$ $$\sum_{i=0}^\infty \frac{x^{2i}}{2i!}=\frac {e^x+e^{-x}}2$$ $$\sum_{i=0}^\infty \frac{x^{2i+1}}{{2i+1}!}=\frac {e^x-e^{-x}}2$$ 全乘起来，代值，完了。 # [P2020 [NOI2011] 兔农](https://www.luogu.com.cn/problem/P2020) $f_{i}=f_{i-1}+f_{i-2}-[(f_{i-1}+f_{i-2})\bmod k = 1] $n \leq 10^{18}$，$k \leq 10^6$，$p \leq 10^9$。 *** [评测链接](https://www.luogu.com.cn/record/33136192) 若 $f_i=0, f_{i+1}=a$，那么在第一个 $\bmod k =1$ 出现之前，$f_{i+t}=a\times \textrm{fib}_t$，设 $\textrm{pos}_i$ 表示 $\textrm{fib}_j=i$ 的最小的 $j$，则下一次出现 $\bmod k = 1$ 的 $t =\textrm{pos}_{\frac 1a}$。 我们又发现，$a$ 是唯一的参数，决定了哪里会 $\bmod k=1$。所以我们直接考虑 $a$ 的循环。显然这是一个 $\rho$ 型结构，因为每个 $a$ 唯一地导向一个 $a'$。最后剩半圈，我们提前记录一下 $\textrm{len}_i$ 表示 $a=i$ 时，走到 $a'$ 的距离即可。 # [P2086 [NOI2012] 魔幻棋盘](https://www.luogu.com.cn/problem/P2086) 矩形加，求矩形 $\gcd$。保证所有矩形的交不为空。 $n\times m \leq 2 \times 10^5$，$Q \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/33195457) 我们可以以所有矩形的交点为中心点向四周差分。 具体地，若中心点为 $(x, y)$，则 $$\begin{aligned}b_{x, j}=a_{x, j}-a_{x, j+1} && j < y \\ b_{x, j}=a_{x, j}-a_{x, j-1} && j > y \\ b_{i, y}=a_{i, y}-a_{i+1, y} && i < x\\ b_{i, y}=a_{i, y}-a_{i-1, y} && i > x\\ b_{i, j}=a_{i, j}-a_{i+1, j}-a_{i, j+1}+a_{i+1, j+1}&& i < x, j < y \\ b_{i, j}=a_{i, j}-a_{i-1, j}-a_{i, j+1}+a_{i-1, j+1}&& i > x, j < y \\ b_{i, j}=a_{i, j}-a_{i+1, j}-a_{i, j-1}+a_{i+1, j-1}&& i < x, j > y \\ b_{i, j}=a_{i, j}-a_{i-1, j}-a_{i, j-1}+a_{i-1, j-1}&& i > x, j > y \\ \end{aligned}$$ 这样，矩形加变为单点加。线段树维护即可。 # [P2109 [NOI2007] 生成树计数](https://www.luogu.com.cn/problem/P2109) 点 $i$ 会向 $[i-k, i-1]$ 连边，求生成树个数。 $n \leq 10^{15}$，$k \leq 5$。 *** [评测链接](https://www.luogu.com.cn/record/32388209) 大小为 $5$ 的本质不同的并查集状态只有 $52$ 种。 设 $f_{i, j}$ 表示前 $i$ 个位置，并查集状态为 $j$ 的方案数。每次考虑一个集合和 $i$ 合并。保证点 $i-k$ 不能孤立。 矩阵快速幂优化。 # [P2150 [NOI2015] 寿司晚宴](https://www.luogu.com.cn/problem/P2150) 在 $\{2, 3, \ldots, n\}$ 选两个不交的集合 $S, T$，使得不存在 $x \in S, y \in T, \gcd(x, y) \neq 1$，求方案数。 $n \leq 500$。 *** [评测链接](https://www.luogu.com.cn/record/29857333) 设 $S$ 中所有数的因子集合为 $A$，$T$ 中为 $B$。则 $A\cap B=\varnothing$。 设数 $i$ 的质因子集合为 $C_i$。 设 $f_{a, b}$ 表示 $A=a,B=b$ 的方案数。 $$\begin{aligned}f'_{a\cup C_i, b}\leftarrow f_{a, b} && b\cap C_i=\varnothing\\ f'_{a, b\cup C_i}\leftarrow f_{a, b} && a\cup C_i=\varnothing\\ f'_{a, b}\leftarrow f_{a, b}\end{aligned}$$ 这样的复杂度是 $O(n4^{d(n)})$。 我们发现，$\geq \sqrt n$ 的质因子，每个数只有一个。 我们把数按 $\geq \sqrt n$ 的质因子分类，每一类要求前两种转移只能有一种。 我们可以设 $g1_{a, b}$ 表示临时数组，转移只能用第一种和第三种，$g2$ 表示第二种和第三种。 开始时把 $g1, g2$ 赋值为 $f$，每做完一类再把 $g1, g2$ 给回 $f$。 注意会重复计算这一类数没有一个被选的方案，所以 $f_{a, b}=-f_{a, b}+g1_{a, b}+g2_{a, b}$。 时间复杂度：$O(n4^{d(\sqrt n)})$。 # [P2179 [NOI2012] 骑行川藏](https://www.luogu.com.cn/problem/P2179) 有 $n$ 条路，第 $i$ 条路长度为 $s_i$，若经过速度为 $v$，做功 $E=k_i(v-v_i)^2s_i$。 总做功至多 $E_U$，求最短经过时间。 $n \leq 10^4$，$E_U \leq 10^8$，$1 \leq s\leq 10^5$，$1 \leq k \leq 15$，$|v| \leq 100$。 *** [评测链接](https://www.luogu.com.cn/record/33206121) $(v-v_i)^2$ 是关于 $v$ 的凸函数。 根据凸函数的套路，我们有每次选取贡献最优的进行贡献。 所以最后每条路的贡献率应该相同。贡献率形式化就是 $E$ 关于 $v$ 的导数。 二分这个数，解方程判断即可。 # [P2305 [NOI2014] 购票](https://www.luogu.com.cn/problem/P2305) 给定一棵 $1$ 号点为根的带权树。 从 $v$ 到 $1$ 的方法为：选择城市 $v$ 的一个祖先 $a$，付出费用到达 $a$。再选择城市 $a$ 的一个祖先 $b$，付出费用到达 $b$。以此类推，直至到达 $1$。 对于任意一个点 $v$ 有距离限制 $l_v$。对于 $v$ 的祖先 A，只有当它们之间所有边的总长度不超过 $l_v$ 时，从 $v$ 才可以一次到达城市 A。 从城市 $v$ 到城市 A 购买的票价为 $dp_v+q_v$，$d$ 为路径长度。 求每个点到达 $1$ 的最小费用。 $n\leq 2 \times 10^5$，$0 \leq p_v \leq 10^6$，$\ 0 \leq q_v \leq 10^{12}$，$0 <s_v \leq 2 \times 10^{11}$。 *** [评测链接](https://www.luogu.com.cn/record/47164530) 设 $f_i$ 表示到点 $i$ 的最小费用。$\textrm{dis}_i$ 表示到 $i$ 的距离。 $$f_u=\min_{v \in \textrm{anc}_u \& dis_u-dis_v \leq l_u}f_v+(dis_u-dis_v)p_u+q_u$$ 令 $b_u=\mathrm{dis}_up_u+q_u$。 则有 $f_{u}=b_u+\min_{v \in \textrm{anc}_u\& dis_u-dis_v \leq l_u}f_v-dis_vp_u$。 发现是个斜率式子，李超树维护。$\textrm{dis}$ 的限制，再套个树状数组，祖先的限制，$\textrm{dfs}$ 的时候维护从祖先到 $u$ 的信息，可撤销化即可。 # [P2538 [SCOI2008]城堡](https://www.luogu.com.cn/problem/P2538) 在一个国家里，有 $n$ 个城市（编号为 $0$ 到 $n-1$）。这些城市之间有 $n$ 条双向道路相连（编号为 $0$ 到 $n-1$），其中编号为 $i$ 的道路连接了城市 $i$ 和城市 $r_i$（一条道路可以连接一个城市和它自身），长度为 $d_i$。$n$ 个城市中有 $m$ 个拥有自己城堡，可以抵御敌人侵略。如果没有城堡的城市遭受攻击，则离它最近的城堡将派兵前往救援。 你的任务是在不超过 $k$ 个没有城堡的城市中建立城堡，使得所有城市中“离最近城堡的距离”的最大值尽量小。换句话说，若令 $dist(c)$ 表示城市 $c$ 的最近城堡离它的距离，则你的任务是让 $\max\{dist(c)\}$ 尽量小。 输入数据保证存在方案使得对于每个城市，至少有一个城堡能够到达。 *** [评测链接](https://www.luogu.com.cn/record/33663952) 退火。 # [P2791 幼儿园篮球题](https://www.luogu.com.cn/problem/P2791) $S$ 组询问，每次给定 $n, m, L$，求： $$\sum_{i=0}^k \binom mi\binom {n-m}{k-i}i^L$$ $S \leq 200$，$L \leq 2 \times 10^5$，$n, m \leq 2\times 10^7$。 *** [评测链接](https://www.luogu.com.cn/record/34246411) $$\begin{aligned}&\sum_{i=0}^k \binom mi\binom {n-m}{k-i}i^L\\ =&\sum_{i=0}^k \binom mi\binom {n-m}{k-i}\sum_{j=0}^L{j\brace L}\binom ijj!\\ =&\sum _{j=0}^L{j\brace L}j!\sum_{i=0}^k\binom mi \binom {n-m}{k-i}\binom ij\\ =&\sum_{j=0}^L{j \brace L}j!\sum_{i=0}^k\binom{n-m}{k-i}\binom{m}{j}\binom{m-j}{i-j}\\ =&\sum_{j=0}^L{j \brace L}j!\binom{n-j}{k-j}\binom mj\end{aligned}$$ 预处理一行斯特林数即可。 # [P3175 [HAOI2015]按位或](https://www.luogu.com.cn/problem/P3175) 刚开始你有一个数字 $0$，每一秒钟你会随机选择一个 $[0,2^n-1]$ 的数字，与你手上的数字进行或（C++,C 的 `|`，pascal 的 `or`）操作。选择数字 $i$ 的概率是 $p_i$。保证 $0\leq p_i \leq 1$，$\sum p_i=1$ 。问期望多少秒后，你手上的数字变成 $2^n-1$。 $n \leq 20$。 *** [评测链接](https://www.luogu.com.cn/record/38158165) $\min-\max$ 容斥经典题。 考虑每一位成为 $1$ 的时间 $t(i)$，我们需要求 $E(\max t(i))$，这等于 $\sum_{S}(-1)^{|S|+1}E(\min_{i \in S}t(i))$，而 $\min_{i \in S}t(i)$ 表示的是我们选中 $S$ 中任意一个元素的期望时间，这等价于选中 $S$ 中任意一个元素的概率的倒数，也即 ($1-$ 选中 $S$ 的补集的子集) 的倒数。 FWT_or 即可。 # [P3214 [HNOI2011]卡农](https://www.luogu.com.cn/problem/P3214) 求选出 $m$ 个无序非空集合，集合内的元素为 $\leq n$ 的整数，没有完全相同的集合，且每个元素出现次数为偶数的方案数。 $n, m \leq 10^6$。 *** [评测链接](https://www.luogu.com.cn/record/33044290) 首先无序变有序，这样防止算重。最后除以 $m!$ 即可。 设 $f_i$ 表示选 $i$ 个集合的方案数。 由于出现次数都为偶数，如果前 $i - 1$ 个集合已知，那么第 $i$ 个集合可以求出。这样的方案数是 $A_{2^n-1}^{i-1}$。 不过这里有不合法的状况，比如第 $i$ 个集合为空。那么前 $i-1$ 是合法的方案，所以减去 $f_{i-1}$。 还有一种不合法情况是 $i$ 和之前的某个集合相同了。那么我们把这两个集合删去后，剩下的 $i-2$ 个是一个合法的方案，枚举这个集合的位置和元素，共有 $(i - 1)(2^n-i-1)$ 种情况，所以减去 $(i-1)(2^n-i-1)f_{i-2}$。 所以转移式为： $$f_i=A_{2^n-1}^{i-1}-f_{i-1}-(i-1)(2^n-i-1)f_{i-2}$$ # [P3236 [HNOI2014]画框](https://www.luogu.com.cn/problem/P3236) 求一个排列 $p$，使得 $\sum A_{i, p_i}\sum B_{i, p_i}$ 最小。 $n \leq 70$，$A, B \leq 200$。 *** [评测链接](https://www.luogu.com.cn/record/39193288) 同最小乘积生成树，这个是最小乘积二分图匹配。 极限卡常，用邻接矩阵存图。 # [P3266 [JLOI2015]骗我呢](https://www.luogu.com.cn/problem/P3266) 求满足以下条件的 $n\times m$ 的矩阵的个数：对于矩阵中的第 $i$ 行第 $j$ 列的元素 $x_{i,j}$ 都有 * $x_{i,j}<x_{i,j+1}

• x_{i,j}<x_{i-1,j+1}
• 0\le x_{i,j}\le m

*** [评测链接](https://www.luogu.com.cn/record/47232865) 发现一行的 $x$ 有 $m + 1$ 种选择，所以每行只有一个数没有出现。 我们记第 $i$ 行没有出现的位置为 $p_i$。 设 $f_{i, j}$ 表示前 $i$ 行，$p_i=j$ 的方案数。 则有 $$f_{i, j}=\sum_{k=0}^{j+1}f_{i-1, k}$$ 优化得 $$f_{i, j}=f_{i-1, j+1}+f_{i, j-1}$$ 设 $g_{i, j}=f_{i, j - i}

则有

g_{i, j}=g_{i - 1, j}+g_{i, j - 1}

定义域为 i \leq j, i+m \geq j

发现这就是从原点出发，只能向右或向上走，不接触两条直线 A,B，到达点 (n+m+1,n) 的路径条数。

这个怎么做呢？

如果只有一条直线，那么我们的经典套路是计算不合法的方案数，而不合法的路径都满足至少经过了 A 一次，所以我们把第一次跨过 A 之后的折线作关于 A 的对称。这样既能满足与原来的线一一对应，又能满足一定至少经过了一次 A。

那两条线呢？我们不合法的方案就变得复杂了。

我们考虑一个经过 A 若干次，然后经过 B 若干次，然后经过 A 若干次，\ldots 并且之后路线任意，这样的路线条数该如何计算。

我们倒着考虑，每次作对称，这样消掉了最后一个的贡献。

那么由于我们令之后的路线任意，一个长度为 l 的容斥系数为 (-1)^l。

计算到方案数为 0 时停止。

复杂度瓶颈在预处理阶乘。后面的计算是 O(\frac nm) 的。

P3270 [JLOI2016]成绩比较

有 n 个同学，第 0 个人称作 B。共有 m 门课，第 i 门课能够获得的成绩为 [1, U_i]，有恰好 k 个人每门课的成绩都不低于 B，且已知 B 每门课的排名 r_i（分数相同的，B 优先），求所有人成绩的方案数。

*** [评测链接](https://www.luogu.com.cn/record/39547815) 看到恰好想到容斥。 考虑至少有 $i$ 个人每门课的成绩都不低于 B，则有： $$\sum_{i=k}^{\min\{n-r\}}(-1)^{i-k}\binom ik \binom {n-1}i\prod_{j=1}^M\binom{n-1-r_j}{r_j-1}\sum_{x=1}^{U_j}x^{n-r_j}(U_j-x)^{r_j-1}$$ 后面的一坨看起来就能插值。 $$\begin{aligned}&\sum_{x=1}^{U_j}x^{n-r_j}(U_j-x)^{r_j-1}\\ =& \sum_{x=1}^{U_j} x^{n-r_j}\sum_{k=0}^{r_j-1}\binom {r_j-1}kU_j^{r_j-1-k}(-1)^kx^k\\ =&\sum_{k=0}^{r_j-1}U_j^{r_j-1-k}(-1)^k\sum_{x=1}^{U_j}x^{n-r_j+k}\end{aligned}$$ 插值求自然数幂和即可。 时间复杂度：$O(n^2m)$。 # [P3348 [ZJOI2016]大森林](https://www.luogu.com.cn/problem/P3348) 你有 $n$ 棵树，每棵树有一个生长结点。你需要支持以下操作： * `0 l r`，表示将第 $l$ 棵树到第 $r$ 棵树的生长节点下面长出一个标号相同的子节点。 * `1 l r x`，表示将第 $l$ 到第 $r$ 棵树的生长结点改为 $x$。 * `2 x u v`，表示询问第 $x$ 号点上 $u$ 和 $v$ 的距离。 $n \leq 10^5$，$m \leq 2 \times 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/43196466) 由于树形不变，我们可以把询问放到最后做。 考虑扫描线，一个 $1$ 操作变为：在 $l$ 处把生长结点改为 $x$，在 $r$ 处改回来。 那么如果现在在生效的 $1$ 操作为 $p_1, p_2, \ldots, p_k$，则在 $[1, p_1)$ 的 $0$ 操作连向 $1$，$(p_1, p_2)$ 的 $0$ 操作连向 $x_{p_1}$，$(p_2, p_3)$ 的 $0$ 操作连向 $x_{p_2}$，$\ldots$。 所以我们可以这么构造：对于每个 $1$ 操作建一个虚点，第 $i$ 个虚点连向第 $i-1$ 个虚点，$0$ 操作连向它之前的最近的虚点，每当一个操作 $j$ 生效，我们把第 $j$ 个虚点在原链上断掉，连向 $x_j$，这样，每个虚点都带着它之前的未生效的一段链。 LCT　即可。 查询的时候，因为要维持父子关系，不能 `makeroot`，所以搞个用 LCT 求 LCA。 时间复杂度：$(n+m)\log(n+m)$。 # [P3600 随机数生成器](https://www.luogu.com.cn/problem/P3600) 生成 $n$ 个 $[1, x]$ 的整数 $a_1, a_2 \ldots a_n$，给定 $q$ 个区间 $[l_i, r_i]$，求 $\max\{\min_{l_i \leq j \leq r_i} a_j \}$ 的期望。 $n, x, q, \leq 2000$。 *** [评测链接](https://www.luogu.com.cn/record/43908512) 看到 $\max$ 的期望想到前缀和。 设 $f_i$ 表示 $\max \leq i$ 的方案数。 这相当于每个区间都至少有一个 $\leq i$ 的数。 我们先把 $[l_1, r_1] \in [l_2, r_2]$ 的 $[l_2, r_2]$ 删去，因为它不可能对 $\max$ 做贡献。 设 $g_{i, j}$ 表示第 $i$ 个位置放了点，前 $i$ 个位置放了 $j$ 个点的方案数。$l_i$ 表示覆盖了位置 $i$ 的最靠左的区间，$r_i$ 表示覆盖了位置 $i$ 的最靠右的区间，如果没有就令 $r_i$ 为 $i$ 前的上一个区间，$l_i=r_i+1$。则 $$g_{i, j} = \sum_{r_k+1 \geq l_i}g_{k, j-1}$$ 发现能够转移的是一个区间，用前缀和优化到 $O(n^2)$。 # [P3642 [APIO2016]烟火表演](https://www.luogu.com.cn/problem/P3642) 给定一棵树，你需要更改边权使得每个叶子到根的距离相同，改大或改小一条边的边权 $1$ 的代价是 $1$。 $n \leq 3 \times 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/44604089) 设 $f_{u, i}$ 表示 $u$ 子树的所有叶子到 $u$ 距离为 $i$ 的最小代价。 由于我们可以对合法方案整体增加边权使得其仍合法，每种方案对答案的贡献应该是一条一次函数。所以 $f_u$ 是下凸函数。 考虑 $u$ 向父亲连的边加入的过程。设边权为 $l$，$f_u$ 斜率为 $0$ 的区间为 $[L, R]$。 $$f'_{u, j}=\begin{cases}f_{u, j}+l & l \leq L\\ f_{u, L}+l-x+L & L < x \leq L+l\\ f_{u, L} & L + l < x \leq R+l \\ f_{u, j}+x-R-l & x>R+l\end{cases}$$ 这是因为我们考虑斜率 $\neq 0$ 的位置，发现改变 $l$ 肯定更优。 发现这个过程是没有决策的。 考虑这个过程，实际上让 $\leq L$ 的位置整体 $+l$，$(L, R]$ 整体向右平移 $l$ 位，在 $[L, L+l]$ 加入了一条新的直线，$\geq R + l$ 的位置的斜率变成 $1$。 发现操作都是斜率相关，我们不如直接维护斜率变化的点。我们要支持这几个东西：pop_back, push_back, merge。 还发现，这个信息是有序的，所以 back 等于最大的。所以我们用可并堆。 # [P3700 [CQOI2017]小Q的表格](https://www.luogu.com.cn/problem/P3700) 一个表格，始终满足： * 对任意的正整数 $a,b$，都要满足 $f(a,b)=f(b,a)$。 * 对任意的正整数 $a,b$，都要满足 $b\times f(a,a+b)=(a+b)\times f(a,b)$。 最初，$f(a, b) = ab$，你需要支持单点修改，查询 $\sum_{1 \leq i, j \leq k}f(i, j)$。 $m \leq 10^4$，$n \leq 4 \times 10^6$。 *** [评测链接](https://www.luogu.com.cn/record/47240091) $$\frac{f(a, b)}b=\frac{f(a, a+b)}{a+b}$$ $$\frac {f(a, b)}{ab}=\frac {f(a, a+b)}{a(a+b)}$$ $$\frac {f(a, b)}{ab}=\frac {f(a, a\bmod b)}{a(a\bmod b)}$$ $$\frac {f(a, b)}{ab}=\frac {f(\gcd(a, b), \gcd(a, b))}{\gcd(a, b)^2}$$ 所以我们维护 $f(x, x)$ 即可。 求答案时： $$\begin{aligned}&\sum_{1 \leq i, j \leq k} f(i, j)\\ =&\sum_{1 \leq i,j \leq k} ij\frac {f(\gcd(i, j), \gcd(i, j))}{\gcd(i, j)^2}\\ =& \sum_{d}f(d, d)\sum_{1 \leq i, j \leq \frac nd}ij[\gcd(i, j)=1]\\ =&\sum_{d}f(d, d)\sum_{i=1}^{\frac nd} i^2\varphi(i)\end{aligned}$$ 整除分块即可。 我们共有 $O(n)$ 次修改，$O(n\sqrt n)$ 次查询，所以使用分块平衡。 # [P3704 [SDOI2017]数字表格](https://www.luogu.com.cn/problem/P3704) $$\prod_{i=1}^n \prod_{j=1}^m f_{\gcd(i, j)}$$ 其中，$f_i$ 表示斐波那契数列第 $i$ 项。 $T \leq 10^3$，$n, m \leq 10^6$。 *** [评测链接](https://www.luogu.com.cn/record/29698910) $$\begin{aligned}&\prod_{i=1}^n \prod_{j=1}^m f_{\gcd(i, j)}\\ =&\prod_{i=1}^n \prod_{j=1}^m \prod_{k=1}^{\min(n, m)}f_k^{[\gcd(i, j)=k]}\\ =& \prod_{k=1}^{\min(n, m)}f_k^{\sum_{i = 1}^n \sum_{j=1}^m [\gcd(i, j)=k]}\\ =&\prod_{k=1}^{\min(n, m)}f_k^{\sum_{d=1}^{\frac nk}\mu(d)\lfloor\frac n{kd}\rfloor\lfloor\frac m{kd}\rfloor}\\ =&\prod_{T=1}^{\min(n, m)}(\prod_{k|T}f_k^{\mu(\frac Tk)})^{\lfloor\frac n{T}\rfloor\lfloor\frac m{T}\rfloor}\end{aligned}$$ 内层 $O(n\log n)$ 预处理，外层数论分块。 # [P3734 [HAOI2017]方案数](https://www.luogu.com.cn/problem/P3734) 如果 $ a \land b = a $，那么 $ a \subseteq b $，其中 $ \land $ 表示二进制下的“与”操作。 考虑现在有一个无限大的空间，现在你在 $ (0, 0, 0) $，有三种位移操作。 * $(x,y,z)\to(x',y,z)$ if $x\subseteq x'

• (x,y,z)\to(x,y',z)$ if $y\subseteq y'
• (x,y,z)\to(x,y,z')$ if $z\subseteq z'

有 o 个点不能经过。现在问你到某个点 (n, m, r) 的方案数。

*** [评测链接](https://www.luogu.com.cn/record/47967472) 先考虑没有障碍的情况。 设 $f_{i, j, k}$ 表示 $x, y, z$ 的二进制下有 $i, j, k$ 个 $1$ 时的方案数。简单转移即可。 那有不能经过的点怎么办？ 考虑容斥，问题变为求出必定经过一个子集的方案数乘容斥系数的和。 而我们发现，由于这些点都是在三维平面上的，所以如果我们把它们按照字典序排列，他们之间的转移关系构成了一个 DAG！ 所以我们设 $g_i$ 表示最后一个点是 $i$ 的，上述的和。 枚举 $1$ 到 $i-1$，转移给它即可。 若两个点 $(x_1, y_1, z_1), (x_2, y_2, z_2)$，前者走到后者的路径数为 $f_{x_2-x_1, y_2-y_1, z_2-z_1}$。 时间复杂度：$O(o^2)$。 # [P3771 [CTSC2017]网络](https://www.luogu.com.cn/problem/P3771) 给定一棵树，你需要加一条给定边权的边，使得图的直径最小。 $n \leq 2 \times 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/26064838) 首先有显然地，这条边至少有一个端点在直径上。不然直径根本没变。 然后，另一个人端点也必须在直径上，否则调整到直径肯定更优。 所以，两个端点都必须在直径上。 先二分答案，假设我们想知道是否存在 $a, b$ 使得所有点对的距离都 $\leq D$。 我们先预处理 $\textrm{dis}_i$ 表示直径上第 $i$ 个点的子树内距离最大值，$\textrm{pos}_i$ 表示直径上第 $i$ 个点与第 $1$ 个点的距离。 则每对 $i, j$ 必须满足 $$\textrm{dis}_i+\textrm{dis}_j+\min(\textrm{pos}_j-\textrm{pos}_i, |pos_i-pos_a|+|pos_j-pos_b|)\leq D$$ 也就是说，所有不满足 $\textrm{pos}_j-\textrm{pos}_i \leq D - \textrm{dis}_i - \textrm{dis}_j$ 的 $(i, j)$，都必须满足 $|pos_i-pos_a|+|pos_j-pos_b| \leq D - \textrm{dis}_i - \textrm{dis}_j

绝对值不好处理，拆开得：

• pos_i-pos_a+pos_j-pos_b \leq D - \textrm{dis}_i - \textrm{dis}_j
• pos_i-pos_a-pos_j+pos_b \leq D - \textrm{dis}_i - \textrm{dis}_j
• -pos_i+pos_a+pos_j-pos_b \leq D - \textrm{dis}_i - \textrm{dis}_j
• -pos_i+pos_a-pos_j+pos_b \leq D - \textrm{dis}_i - \textrm{dis}_j

需同时满足。

我们按照 \textrm{dis}_i+\textrm{pos}_i 从小到大枚举 i，维护所有满足 \textrm{pos}_j-\textrm{pos}_i > D - \textrm{dis}_i - \textrm{dis}_j 的 j 的信息，求出四个式子带来的限制。

限制形如：\textrm{pos}_a+\textrm{pos}_b\in [l_1, r_1]，\textrm{pos}_b-\textrm{pos}_a \in [l_2, r_2]。

枚举 a，用四个指针维护 b 的范围，判一下是否有交即可。

时间复杂度：O(n\log \textrm{ans})

P3773 [CTSC2017]吉夫特

输入一个长度为 n 的数列 a_1, a_2, \cdots , a_n 问有多少个长度大于等于 2 的不上升的子序列满足：

\prod _{i=2}^{k} \binom{a_{b_{i-1}}}{a_{b_i}} \mod 2 = \binom{a_{b_1}}{a_{b_2}} \times \binom{a_{b_2}}{a_{b_3}} \times \cdots \binom{a_{b_{k-1}}}{a_{b_k}} \mod 2 > 0

保证 a 互不相同。

*** [评测链接](https://www.luogu.com.cn/record/38548957) 考虑 Lucas 公式 $$\binom ab\bmod p=\prod_i \binom {\frac a{p^i}\bmod p}{\frac b{p^i}\bmod p}$$ 简单推导发现，一个序列合法，当且仅当对于每个 $i$，$a_i$ 的二进制表示是 $a_{i+1}$ 的子集。 由于 $a$ 互不相同，我们记每个数出现的位置，枚举子集转移即可。 时间复杂度：$O(a^{\log_23})$。 # [P3781 [SDOI2017]切树游戏](https://www.luogu.com.cn/problem/P3781) 给你一棵树，每个点有点权，你需要支持两个操作。 * 单点修改点权。 * 询问有多少个连通子图的点的异或和为 $k$。 设点权上限为 $m$。 $n, q \leq 3 \times 10^4$，$m \leq 127$。 *** [评测链接](https://www.luogu.com.cn/record/42625763) 设 $f_{u, j}$ 表示 $u$ 号点，异或和为 $j$ 的连通子树的个数。 $$f'_{u, k}\leftarrow\sum_{i\oplus j=k} f_{u, i}f_{v, j}$$ 设 $g_u$ 为 $f_u$ FWT 后的结果。 $$g'_{u, k}= g_{u, k}(1+g_{v, k})$$ 设 $s_{u, k}$ 表示 $u$ 子树 $f_{*, k}$ 的和。 考虑用动态 dp 优化此过程。 再应用一些卡常技巧，很没意思，不想再提了。 # [P3783 [SDOI2017]天才黑客](https://www.luogu.com.cn/problem/P3783) 给定一张图，每条边上有一个字符串。一条路径 $e_1, e_2, \ldots, e_k$ 的权值为 $$\sum_{i=1}^{k-1}\textrm{lcp}(\textrm{str}_{e_i}, \textrm{str}_{e_{i+1}})$$ 每个字符串都能被一个大小为 $k$ 的字典树识别。 求单源最短路。 $n, m\leq 5\times 10^4$，$k \leq 2 \times 10^4$。 *** [评测链接](https://www.luogu.com.cn/record/47765979) 应该能意识到，我们需要优化建图，之后跑最短路即可。 最初我的想法是，对于每个点的所有出边字符串和入边字符串在字典树的终止位置建虚树，$\textrm{lcp}$ 是两个点 $\textrm{lca}$ 的深度，所以把虚树的每条边在新图上建出来即可。 但是这样是不对的。因为 $\textrm{lca}$ 是祖先中深度**最大的**，而我们要求的是**最短路**，所以多余的边会产生影响。 所以我们需要找到能用最小来表达 $\textrm{lcp}$ 的属性。 想到两个串的 $\textrm{lcp}$ 为字典序在两者之间的若干串，排序后相邻两串 $\textrm{lcp}$ 的最小值。 也即，若字符串字典序 $A < B < C$，那么，$\textrm{lcp}(A, C)=\min(\textrm{lcp}(A, B), \textrm{lcp}(B, C))$。 （这个过程可以类比拆绝对值 $\max\{|a|\}=\max(\max\{a\}, \max\{-a\})$） 我们把入边、出边按照字符串的终止位置的 dfs 序排序，连成一条入链和一条出链。 之后，我们把入链第 $u$ 个点和出链第 $u + 1$ 个点连上两者的 $\textrm{lcp}$。 这样，我们就能完成 $S < T$，$S \to T$ 的连边。 再反着连一遍即可。 # [P3822 [NOI2017] 整数](https://www.luogu.com.cn/problem/P3822) 有一个变量 $x$，最初为 $0$。 你需要支持两个操作： * $x$ 加上 $a \times 2^b$，$a$ 可以为负数。 * 查询 $x$ 二进制表示第 $k$ 位。 $n \leq 10^6$，$b, k \leq 30n$。 *** [评测链接](https://www.luogu.com.cn/record/32704033) 如果 $a=1$，那么直接加，均摊复杂度是 $O(1)$ 的。 如果 $|a|=1$，那么就不能直接加减了。我们可以用线段树维护一下从一个位置开始向前/后有多少个 $1$，再支持一个区间赋值。这样复杂度是 $O(\log n)$ 的。 $|a|\leq 10^9$，这样复杂度变为 $O(\log a\log n)$，无法通过，所以 $30$ 个压一位，这样只用操作两次。 # [P3920 [WC2014]紫荆花之恋](https://www.luogu.com.cn/problem/P3920) 最初，你有一个树根。 你需要支持两个操作： * 询问整棵树上 $dis(i, j)\leq r_i + r_j$ 的 $(i, j)$ 个数。 * 新增一个叶子。 强制在线。 $n \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/44632158) 第一个操作让我们想到点分树。对于每一层，我们需要支持插入、删除，查询大于一个数的元素个数。使用平衡树维护。 但是新增叶子怎么做？我们考虑对点分树上的每个点设定描述平衡的估价函数（这里是 $\frac {\max siz}{\sum siz}$），当其达到一定阈值时将整棵子树重构。 因为卡常，这里使用了 WBLT 平衡树。 # [P4002 [清华集训2017]生成树计数](https://www.luogu.com.cn/problem/P4002) 在一个 $s$ 个点的图中，存在 $s-n$ 条边，使图中形成了 $n$ 个连通块，第 $i$ 个连通块中有 $a_i$ 个点。 现在我们需要再连接 $n-1$ 条边，使该图变成一棵树。对一种连边方案，设原图中第 $i$ 个连通块连出了 $d_i$ 条边，那么这棵树 $T$ 的价值为： $$ \mathrm{val}(T) = \left(\prod_{i=1}^{n} {d_i}^m\right)\left(\sum_{i=1}^{n} {d_i}^m\right) $$ 你的任务是求出所有可能的生成树的价值之和，对 $998244353$ 取模。 *** [评测链接](https://www.luogu.com.cn/record/31972132) 考虑每个点出现在 prufer 序列的次数，记作 $d_i$。则我们要求 $$\begin{aligned}&\frac {(n-2)!}{\prod d_i!}\prod (d_i+1)^ma_i^{d_i+1}\sum (d_i+1)^m\\ =& \frac {(n-2)!}{\prod d_i!}\prod a_i\times \prod (d_i+1)^ma_i^{d_i}\sum(d_i+1)^m\\ =& (n-2)!\prod a_i\times \sum_i\frac 1{d_i!}(d_i+1)^{2m}a^{d_i}\sum_{j\neq i}\frac{(d_j+1)^m}{d_j!}\end{aligned}$$ 设 $A(x)=\sum (i+1)^m\frac {x^i}{i!}, B(x)=\sum (i+1)^{2m} \frac {x^i}{i!}

则答案为

\begin{aligned}&\sum_i B(a_ix)\prod_{j\neq i}A(a_jx)\\ =& \sum_i \frac {B(a_ix)}{A(a_ix)}\prod_j A(a_jx)\\ =&\exp\sum_i (\ln A)(a_ix)\times \sum_i \frac {B(a_ix)}{A(a_ix)} \end{aligned}

发现两个式子都需要支持带入 a_i 后求和。

也即，x^k 项乘 \sum_{i}a_i^k。我们需要对于每个 k 求这个。

考虑每个 a_i 的生成函数 \sum a_i^kx^k=\frac 1{1-a_ix}。

\begin{aligned}\sum \frac 1{1-a_ix}=\frac {\sum_{i=1}^n\prod_{j \neq i}(1-a_jx)}{\prod (1-a_ix)}\end{aligned}

设分子为 P(x)，分母为 Q(x)。

对于 $P(x)$ 我们考虑有 $k$ 个位置选择了 $a_ix$ 这一项，那么它对 $x^k$ 的贡献是 $(n-k)\prod a_i$，而下面为 $\prod a_i$。所以 $$P(x)=\sum_i(n-i)[x^i]Q(x)x^i$$ 这样就做完了，复杂度与 $m$ 无关。 时间复杂度：$O(n\log^2n)$。 # [P4003 无限之环](https://www.luogu.com.cn/problem/P4003) 游戏在一个 $n \times m$ 的网格状棋盘上进行，其中有些小方格中会有水管，水管可能在格某些方向的边界的中点有接口，所有水管的粗细都相同，所以如果两个相邻方格的共边界的中点都有接头，那么可以看作这两个接头互相连接。水管有以下 $15$ 种形状：  游戏开始时，棋盘中水管可能存在漏水的地方。 形式化地：如果存在某个接头，没有和其它接头相连接，那么它就是一个漏水的地方。 玩家可以进行一种操作：选定一个含有**非直线型**水管的方格，将其中的水管绕方格中心顺时针或逆时针旋转 $90$ 度。 直线型水管是指左图里中间一行的两种水管。 现给出一个初始局面，请问最少进行多少次操作可以使棋盘上不存在漏水的地方。 $nm \leq 2000$。 *** [评测链接](https://www.luogu.com.cn/record/39343211) 发现除了直线，其他的类型都仅仅是若干变量和的限制，满足线性规划的形式。 假设 $x_1, x_2, x_3, x_4$ 是一个位置上下左右四个位置是否有出口。 直线：$x_1+x_2=2 \oplus x_3+x_4=2$，$\oplus$ 很不好，线性规划没法处理。 两边：$x_1+x_2=1 \land x_3+x_4=1$。 三边：$x_1+x_2+x_3+x_4=3$。 四边：$x_1+x_2+x_3+x_4=4$。 又发现没有漏水的地方等价于最大化咬合的位置。这样，我们能建立费用流模型。 # [P4005 小 Y 和地铁](https://www.luogu.com.cn/problem/P4005) $1$ 到 $2n$ 这 $2n$ 个点在依次一条线段上排列。他们构成了 $n$ 对匹配。 我们现在需要把匹配的一对点之间在二维平面上连边。问至少需要交叉多少次。 $T \leq 100$，$n \leq 44$。 *** [评测链接](https://www.luogu.com.cn/record/33917824) 这里就借题解区的图了。 一共有 $8$ 种情况。         又发现 $1, 2$，$3, 4$，$5, 6$，$7, 8$ 是等价的。 所以只用四种情况。 然后退火。。。 # [P4007 小 Y 和恐怖的奴隶主](https://www.luogu.com.cn/problem/P4007) 有一个 $\infty$ 血的 boss 和一个 $m$ 血的随从。 你打一次随从，它掉一滴血。如果它没死并且随从个数 $\neq k$，它会再召唤一个 $m$ 血的随从。 每次你会随机一个对象打。 问你打 $n$ 次，期望打 boss 的次数。 $T \leq 1000$，$n \leq 10^{18}$，$m \leq 3$，$k \leq 8$。 *** [评测链接](https://www.luogu.com.cn/record/33919099) 设 $f_{i, a, b, c}$ 表示前 $i$ 次，有 $a$ 个 $1$ 血，$b$ 个 $2$ 血，$c$ 个 $3$ 血时期望打 boss 的次数。转移即可。 发现合法的状态只有 $165$ 种。我们除此之外再记录一下整体期望打 boss 的次数。这 $166$ 个状态跑矩阵快速幂。 由于询问很多，所以先预处理矩阵乘 $2^k$ 次后的结果，用向量乘。 时间复杂度：$O(c^3\log n+Tc^2\log n)$。 其中 $c=166$。 # [P4091 [HEOI2016/TJOI2016]求和](https://www.luogu.com.cn/problem/P4091) $$\sum_{i=0}^n\sum_{j=0}^i {i \brace j} 2^j j!$$ 其中 $S$ 为第二类斯特林数。 $n \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/34164183) $$m^n=\sum_{i=0}^m{n\brace i}\binom mi i!$$ 二项式反演得： $${n\brace m}m!=\sum_{i=0}^m\binom mi(-1)^{m-i}i^n$$ $${n \brace m}=\sum_{i=0}^m \frac 1{i!(m-i)!}(-1)^{m-i}i^n$$ 当 $n < m$ 时，这个式子也能自动修正为 $0$。所以 $j$ 可以枚举到 $n$。 带入得： $$\begin{aligned}&\sum_{i=0}^n\sum_{j=0}^n2^jj!\sum_{k=0}^j\frac {k^i}{k!}\frac{(-1)^{j-k}}{(j-k)!}\\ =& \sum_{j=0}^n2^jj!\sum_{k=0}^j\frac {\sum_{i=0}^nk^i}{k!}\frac {(-1)^{j-k}}{(j-k)!}\end{aligned}$$ 这是卷积的形式，NTT 即可。 # [P4094 [HEOI2016/TJOI2016]字符串](https://www.luogu.com.cn/problem/P4094) 给定 $s$，$m$ 组询问，每次给定 $a,b,c,d$，求 $$\max_{[x, y] \in [a, b]}\textrm{lcp}(s[x, y], s[c, d])$$ $|s|, m \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/48908434) 二分答案。 考虑 $s[c, c+mid)$ 在 SAM 上定位到节点 $u$，只用查 Right 集合中是否有 $(a+mid, b]$ 即可。 # [P4125 [WC2012]记忆中的水杉树](https://www.luogu.com.cn/problem/P4125) 在二维平面上有 $n$ 条线段，他们互相没有接触。 每次可以选择一条线段，选择一个方向，并把它从这个方向移出到无穷远出。 如果移出时碰到了还没有移出的线段（仅端点接触不算碰到），则这次移动是非法的。 现在有两个问题： * 给定一个操作序列，给出第一个不合法的操作位置。 * 构造一个操作序列，使得所有线段都被移出。 $n \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/33041431) 先考虑第二问。 我们仅使用一个方向，将依赖关系建图。由于他们互相没有接触，这张图一定是一个 DAG。 那么我们的目标就是得到它的一个拓扑排序。 考虑维护不交的线段的经典套路：先扫描线，目前扫描到的线段的相对顺序不会改变，所以用 set 维护。当加入一个点时，它的后继向它，它向它的前驱连两条边。 第一问怎么做呢？我们考虑维护区间横竖两种拓扑序最大/最小值，倒着加线段，如果当前区间的拓扑序小于/大于最值（小于还是大于，最大还是最小看方向），那么就是非法的。 # [P4156 [WC2016]论战捆竹竿](https://www.luogu.com.cn/problem/P4156) 给定一个字符串 $S$，现在有一个空串 $T$，你可以向 $T$ 后拼接 $S$ 前缀砍去一个 border （可以为空）后的字符串。 求 $\leq w$ 有多少种 $|T|$。 $|S| \leq 5 \times 10^5$，$w \leq 10^{18}$。 *** [评测链接](https://www.luogu.com.cn/record/25647122) **定理：** 一个字符串的所有 border 排序后，至少存在一种将序列划分为若干子序列的方案，使得所有子序列均为等差数列，且子序列的个数为 $O(\log|s|)$。 **证明：** 一个显然的结论：$s[0..k - 1]$ 为 $s$ 的 border $\rightleftharpoons$ $|s| - k$ 为 $s$ 的周期。 另一个显然的结论：若 $p$ , $q$ 为 $s$ 的周期，则 $\gcd(p, q)$ 也为 $s$ 的周期。 以上两个结论可以套定义得到。 考虑两个 $|s|$ 的 border : $A$，$B$，其中 $B$ 为最长的 border ( $s$ 本身除外)，$|A| \geq \frac{|s|}{2}$ 。 令 $p=|s| - |A|$，$q=|s| - |B|$。 若这样的两个 $border$ 存在，则 $p$ , $q$ , $\gcd(p,q)$ 均为 $s$ 的周期，所以 $s[0..|s| - \gcd(p, q)]$ 为 $s$ 的 border，又因为 $B$ 为最长的 border，所以 $\gcd(p,q)$ = $q$。 因此 $q|p$ 。又因为 $k \times q$ 也是 $|s|$ 的周期，所以 $s[0..|s| - k \times q - 1]$ 都是 $s$ 的 border。因此**所有长度大于等于字符串一半的 border 构成一个等差数列**。 考虑两个 $|s|$ 的 border : $A$，$B$ ($|A| < |B|$)。 则 $A$ 也为 $B$ 的 border。 所以我们可以把 border 分成两个集合：第一个集合的 border 长度大于等于 $\frac{|s|}{2}$，第二部分为其他。第一部分构成了一个等差数列，第二部分所有字符串为其中最长的字符串的 border，可以递归处理，至多 $\log |s|$ 层。定理得证。 *** 得到了这个定理，我们回到题目。 我们可以将题意转化为：$\sum_{i=1}^{\textrm{cnt}}a_ix_i$ 在 $[0,w-n]$ 中能取到的值的个数，其中 $\textrm{cnt}$ 为 $|s|$ 的周期个数，$a$ 为周期长度。 由此我们想到了**同余最短路**。 注意，$\min\{a_i\}\times \textrm{cnt}$ 是 $O(n^2)$ 的，构造方法为 `aaa...aabaaa...aa` 。其中 $b$ 处在字符串较中间的位置。 但是由于 border 拥有特殊的性质，我们可以进行优化。 我们把不同的等差数列分开处理。 首先，对于一个等差数列 $x,x + d,x + 2d, \ldots x + l\times d$，我们在$\mod x$ 下跑同余最短路。其中对于 $0 \leq y < x$ 的 $y$ 向 $ (y + d) \bmod x$ 连边，会形成 $\gcd(x, d)$ 个环。每个环可以分开处理。 但我们此时发现，把等差数列分开处理的坏处就是此时没有源点，如果用环上任何一点去优化另外一点，需要 $\Omega(n^2)$ ，这样复杂度很劣。 但是我们又可以发现，环中 $\textrm{dis}$ 最小的一点是绝不会被更新的，且相邻两点之间权值相同，都为 $d$。这两条性质，可以让我们从 $dis$ 最小点出发，使用单调队列计算。 我们在单调队列里放入离现在处理点距离小于等于 $l$ 的点，以 $\textrm{dis}_i -\textrm{pos}_i * d$ 作为比较方式（因为环上 $a$ 点到 $b$ 点的代价是 $-\textrm{pos}_a * d + \textrm{pos}_b * d$)。这样我们就能处理环上的转移。 还有一个问题，是 $\textrm{dis}$ 数组在不同模数之间的转换。若原先的模数为 $las$，现在的模数为 $\textrm{now}$，很显然 $\textrm{dis}_i$ 可以更新 $\textrm{dis}'_{\textrm{dis}_i \bmod \textrm{now}}$。但 $\textrm{dis}_i$ 的含义是 $\textrm{dis}_i + k * \textrm{las}$ ($k \geq 0$) 可以被访问。所以我们在$\mod \textrm{now}$ 意义下再用 $x$ 更新$(x + las)\mod \textrm{now}$ 跑一边同余最短路即可。 注意到这个过程类似于单个等差数列的处理过程。同样可以把环分开处理。不过由于没有 $l$ 的限制，不需要用到单调队列。 时间复杂度：$O(Tn\log n)$ 。 # [P4183 [USACO18JAN]Cow at Large P](https://www.luogu.com.cn/problem/P4183) 农场可视为一棵有 $n$ 个结点的树。每个叶子结点都是出入口。开始时，每个出入口都可以放一个农民（也可以不放）。每个时刻，贝茜和农民都可以移动到相邻的一个结点。如果某一时刻农民与贝茜相遇了（在边上或点上均算），则贝茜将被抓住。抓捕过程中，农民们与贝茜均知道对方在哪个结点。 对于每个结点 $i$，求如果开始时贝茜在该结点，最少有多少农民，她才会被抓住。 $n \leq 7 \times 10^4$。 *** [评测链接](https://www.luogu.com.cn/record/34065378) 假设当前在点 $u$，设 $g_i$ 表示 $i$ 子树内离 $i$ 最近的叶子。 一棵子树能用一个人堵住当且仅当 $\textrm{dis}(u, i) \leq g_i$。 那么，答案应该等于满足这条，而子树不满足的个数。 对于这个，我们有经典套路：一棵子树的度数和为 $2n-2$，算上根向父亲的连边，是 $2n-1$，那么 $2-\textrm{deg}_i$ 的和为 $1$。 这是点对之间的贡献，所以用点分治来做。 # [P4189 [CTSC2010]星际旅行](https://www.luogu.com.cn/problem/P4189) 给定一颗树，每个点有点权 $h_i$，表示从这个点出发至多 $h_i$ 次。保证 $h_i \geq \textrm{deg}_i$。对于每个点，求从 $0$ 出发，$i$ 结束至多走多少步。 $n \leq 5 \times 10^4$，$h \leq 4 \times 10^4$。 *** [评测链接](https://www.luogu.com.cn/record/39308566) 首先这是一个网络流的模型。 由于保证了 $h_i \geq \textrm{deg}_i$，我们肯定能从 $0$ 出发，走一圈回到 $0$。 之后，我们考虑增加流量。如果 $u, v$ 都有权值，我们可以增加流量。 之后我们考虑更改终点。 如果我们要把终点从 $u$ 改到 $v$，那么分三种情况 * 如果 $u$ 还有权值，之前的路径不用变，再加 $u \to v$ 的一点流量。 * 如果 $v$ 有儿子 $x$ 还有权值，我们退流 $v \to u$，加入 $v \to x$，$x\to v$。 * 否则，我们只能退流 $v \to u$。 增加减少流的同时，别忘了修改权值。 # [P4191 [CTSC2010]性能优化](https://www.luogu.com.cn/problem/P4191) 求 $n - 1$ 次多项式 $f$ 循环卷积 $C$ 次模 $n$ 后的结果。 保证 $n$ 能分解为 $2^a3^b5^c7^d$ 的形式。 $n \leq 5 \times 10^5$，$C \leq 10^9$。 *** [评测链接](https://www.luogu.com.cn/record/39326208) 一道无法靠背 NTT 板子通过的裸 NTT 题。 考虑 $n$ 有因子 $k$，我们把多项式分为 $k$ 份： $$f(x)=\sum_{i=0}^{k-1}x^if'_i(x^k)$$ 其中，$f'_i(x)=\sum_{j=0}^\frac nk [x^{jk+i}]f(x)x^j$。 将 $\omega_n^j$ 带入得： $$f(\omega_n^j)=\sum_{i=0}^{k-1}\omega_n^{ij}f_i'(\omega_{\frac nk}^j)$$ 递归即可。 # [P4218 [CTSC2010]珠宝商](https://www.luogu.com.cn/problem/P4218) 给定一棵树和一个串 $S$，树上每个点有一个字符。求 $n^2$ 条路径构成的字符串在 $S$ 中出现次数总和。 $n, |S|\leq 5\times 10^4$。 *** [评测链接](https://www.luogu.com.cn/record/38149126) 考虑对 $S$ 建后缀自动机，之后对树点分治。 那么我们需要支持两个操作： * 向前加字符 * 向后加字符 询问他们在同一个点匹配的次数乘积的和。 向前加怎么做呢？考虑随便记录一个 right 集合中的位置，判一下往前加是否还合法。如果 $\textrm{len}$ 超过了就在 parent 树上枚举后继。 这样一次的复杂度是 $O(|S|)$ 的。 但是如果我们分治到了很小的子树，每次还是 $O(|S|)$ 的，不能接受。 考虑暴力对子树内每个点为根开始 dfs，暴力匹配。 这样的复杂度是 $O(\textrm{siz}^2)$ 的。 平衡一下，因为点分树只有至多 $\sqrt n$ 个

\textrm{siz }\geq \sqrt n 的子树，所以复杂度是 O((n+|S|) \sqrt n)$ 的。

P4220 [WC2018]通道

给定三棵树。求

\textrm{dis}_1(u, v)+\textrm{dis}_2(u, v)+\textrm{dis}_3(u, v)

的最大值。

*** [评测链接](https://www.luogu.com.cn/record/31830043) 假如有一棵树怎么做？求直径。 假如有两棵树怎么做？考虑第一棵树的距离拆成 $$\textrm{dep}_u+\textrm{dep}_v-2\textrm{dep}_{\textrm{lca}(u, v)}$$ 我们枚举第一棵树的 $\textrm{lca}$，那么此时我们要求 $$\textrm{dep}_u+\textrm{dep}_v+\textrm{dis}_2(u, v)$$ 的最大值。 我们知道，如果边权非负，那么两棵树合并后的直径的端点一定可以从原来两棵树的直径端点中产生。 那么加上 $\textrm{dep}$ 后，这个性质还成立吗？结果是肯定的。我们考虑在原树上每个点向上连一个虚点 $u'$，边权为 $\textrm{dep}_u$，这样获得的还是一棵树。 那么，三棵树怎么做？ 我们对第一棵树进行边分治。（为什么不是点分治呢？因为我们只想要两棵子树，不然复杂度会爆炸） 分出来的两棵子树，我们可以建虚树。这样复杂度就有保证了，然后就可以套两棵树的做法了。 # [P4221 [WC2018]州区划分](https://www.luogu.com.cn/problem/P4221) 给定一张 $n$ 个点 $m$ 条边的图。你需要把点划分成若干组，使得每组的导出子图都没有欧拉回路。 假设划分的集合为 $V_1, V_2\ldots, V_k$，那么它的贡献为： $$(\prod_{i=1}^k \frac {\sum_{x \in V_i}w_x}{\sum_{j=1}^i\sum_{x\in V_j}w_x})^p$$ 求所有划分的贡献和。 $n \leq 21$，$p \leq 2$，$w \leq 100$。 *** [评测链接](https://www.luogu.com.cn/record/33064931) 大概是将子集卷积引入的题。 # [P4224 [清华集训2017]简单数据结构](https://www.luogu.com.cn/problem/P4224) 一个序列，你需要支持以下操作： * `push_front` * `pop_front` * `push_back` * `pop_back` 保证： * 序列中的数互不相同。 * 每个数至多插入 $10$ 次。 每次询问最长的子序列 $B$ 的长度，满足 $B_i|B_{i+1}$。 你还需要输出满足最长的，不同的 $B_1$ 的个数。 设插入的数 $\leq m$，初始有 $n$ 个数。 $n, q \leq 10^5$，$m \leq 10^6$。 *** [评测链接](https://www.luogu.com.cn/record/37861270) 设 $f_i$ 表示从序列首到以 $i$ 结尾的位置，最长序列的长度。 发现没法支持删除。 所以设 $g_{i, j}$ 表示从序列首到以 $i$ 结尾的位置，序列长度为 $j$，能够转移到它的长度为 $j-1$ 的序列的个数。 由于至多插入 $10$ 次，所以我们暴力加入，暴力撤销（枚举因数/倍数）是可以接受的。 # [P4227 我的生命已如风中残烛](https://www.luogu.com.cn/problem/P4227) 在二维平面上有若干个钉子。 有 $m$ 根绳子，给定了长度，一端固定在某一点，另一端在平面上顺时针旋转，当碰到一个钉子时，它会作为新的轴心。 求每条绳子会更改多少次轴心。 $n, m \leq 500$。 *** [评测链接](https://www.luogu.com.cn/record/47887499) 如果长度足够，我们肯定会绕出循环节（在凸包上绕）。所以我们暴力计算下一次到达的点，循环节直接除。再重复这个过程（因为还有可能有小的循环节）。 循环节的更改类似于取模运算，每次至少减少一半，所以循环节改变的次数是 $\log$ 的。 复杂度：$O(mn^2\log L)$。 # [P4228 [清华集训2017] 榕树之心](https://www.luogu.com.cn/problem/P4228) 给定一棵树，初始只有根节点，接下来树会长出一个新结点，即某个和当前已经存在的某个结点相邻的结点被加入了树中。 根节点有一个心，每次加入一个点，心都会沿着心到新加结点的简单路径移动一步。 求每个点能否成为心最终的位置。 $n \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/33989346) 考虑只判断最终到根是否合法。 考虑题目所描述的过程可以理解为两个不同子树的两个点匹配。 如果重儿子没有其他儿子的 $\textrm{siz}$ 总和大并且奇偶性正确，到根就是合法的。 否则，我们没法把所有点进行匹配。 此时还有一种解决方案，先把心挪入重儿子，此时重儿子的两个点匹配，心的位置不变，相当于抵消了。 这是一个递归的过程。 我们设 $f_u$ 表示 $u$ 号点的子树匹配完后，心里 $u$ 至少多远。 那么答案为 $[f_1=0]$。 设 $v$ 为 $u$ 的重儿子，则有转移： $$f_u=\begin{cases}f_v\bmod 2 & f_v+1\leq \textrm{siz}_u-\textrm{siz}_v-1\\ f_v+1-(\textrm{siz}_u-\textrm{siz}_v-1) & \textrm{else}\end{cases}$$ 对于判断其他点的情况，我们考虑先从 $1$ 号点走到 $u$ 号点，把 $1\to u$ 缩成一个点，当做新的根，再进行相同的处理。 有可能 $1\to u$ 经过了某些点的重儿子，所以我们还要维护次重儿子的信息。 # [P4229 某位歌姬的故事](https://www.luogu.com.cn/problem/P4229) 一个序列 $h$，满足每个数都是 $[1, A]$ 的整数。 有 $Q$ 个要求，每个要求形如 $[l, r]$ 的最大值恰好为 $m$。 求合法的序列数。 $n, A\leq 10^9$，$Q \leq 500$，$T \leq 20$。 *** [评测链接](https://www.luogu.com.cn/record/37975554) NOI2020 命运 的序列版本。 先离散化，这样每个位置有一个长度 $l_i$。 首先，我们设位置 $i$ 限制它的最严的为 $m_i$。 发现，如果两个位置 $m_i$ 不同，那两个位置的放置没有任何关联。所以我们每次把 $m_i$ 相同的拿出来一起处理。 问题转化为，每个位置可以放 $0/1$，有若干个区间，每个区间至少有一个 $1$，问有多少种放法。 设 $f_{i, j}$ 表示前 $i$ 个位置，上一个 $1$ 的位置是 $j$ 的方案数。$\textrm{lim}_i$ 表示最左在哪里放 $1$ 能满足位置 $i$。则 $$f_{i, j}=\begin{cases}f_{i-1, j}(m_i-1)^{l_i}& \textrm{lim}_i \leq j < i \\ \sum_kf_{i-1, k}(m_i^{l_i}-(m_i-1)^{l_i}) & i=j\end{cases}$$ 前缀和优化即可。 时间复杂度：$O(TQ^2)$。 # [P4233 射命丸文的笔记](https://www.luogu.com.cn/problem/P4233) 设 $i$ 个点的存在哈密顿回路的竞赛图个数为 $A_i$，哈密顿回路总数为 $B_i$。 对于每个 $i \leq n$，求 $\frac {B_i}{A_i}$。 $n \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/44949618) 考虑一种哈密顿回路，会在 $2^{\binom n2-n}$ 个图中出现。共有 $(n-1)!$ 种，所以 $$B_n=(n-1)!\times 2^{\binom n2-n}$$ 竞赛图存在哈密顿回路当且仅当图是强连通图。 考虑容斥。 $$A_n=2^{\binom n2}-\sum_{i=0}^n\binom niA_i2^{\binom {n-i}2}$$ 分治 NTT 优化即可。 # [P4247 [清华集训2012]序列操作](https://www.luogu.com.cn/problem/P4247) 有一个长度为 $n$ 的序列，有三个操作： * `I a b c` 表示将 $[a,b]$ 这一段区间的元素集体增加 $c$。 * `R a b` 表示将 $[a,b]$ 区间内所有元素变成相反数。 * `Q a b c` 表示询问 $[a,b]$ 这一段区间中选择 $c$ 个数相乘的所有方案的和 $\mod 19940417$ 的值。 *** [评测链接](https://www.luogu.com.cn/record/38433120) 原来的答案是 $$\sum_{|S|=c}\prod_{i \in S}a_i$$ 现在变为 $$\begin{aligned}&\sum_{|S|=c}\prod_{i \in S}(a_i+x)\\ =&\sum_{j=0}^c\binom cj x^{c-j}\sum_{|S|=j}\prod_{i\in S} a_i\end{aligned}$$ 所以我们对于每个 $c$ 维护答案即可。 合并两个区间的答案是卷积的形式。取反是平凡的。 # [P4249 [WC2007]剪刀石头布](https://www.luogu.com.cn/problem/P4249) 给定一个竞赛图，若干条边已经被定向。你需要给其他的边定向使得三元环个数最多。 $n \leq 100$。 *** [评测链接](https://www.luogu.com.cn/record/28148127) 考虑三元组没有构成三元环的情况。 必然是存在某个点，使得这个点有两条出边。 设 $\textrm{out}_i$ 表示 $i$ 的出边。 则整张图三元环个数为 $\binom n3-\sum \binom{\textrm{out}_i}2$。 发现 $\binom x2$ 是一个凸函数。 也即，$x$ 增加使得 $\binom x2$ 的变化量越来越大。 因此，我们考虑一个费用流模型。 * $s$ 向每条边连 $(1, 0)$ 的边。 * 每条边向两个端点连 $(1, 0)$ 的边。如果已经被定向，就只连一条边。 * 每个点向 $t$ 连 $(1, \binom 12)$，$(1, \binom 22-\binom 12)$，$(1, \binom 32-\binom22)$，$(1, \binom 42-\binom 32)$,$\ldots$。 由于 $n$ 很小，所以连边数量能接受。 # [P4252 [NOI2006] 聪明的导游](https://www.luogu.com.cn/problem/P4252) 退火提答，不写了。 # [P4337 [ZJOI2018]线图](https://www.luogu.com.cn/problem/P4337) 对于无向图 $G = ⟨V, E⟩$，它的 线图 $L(G)$ 也是一个无向图： * 它的点集大小为 $|E|$，每个点唯一对应着原图的一条边。 * 两个点之间有边当且仅当这两个点对应的边在原图上有公共点（注意不会有自环）。 给定一棵树 $T$，计算 $L^k(T)$ 的点数（$L^k(T)$ 表示对 $T$ 求 $k$ 次线图）。 $n \leq 5000$，$k \leq 9$。 *** [评测链接](https://www.luogu.com.cn/record/44370031) * $k=1$，答案为 $n-1$。 * $k=2$，答案为 $\sum \binom{\textrm{deg}_i}2$。 * $k=3$，有两种情况，一条长度为 $3$ 的链最终构成了一个点，一个三条边的菊花最终构成了三个点。所以答案为 $\sum_{i=1}^m(\textrm{deg}_u-1)(\textrm{deg}_v-1)+\sum_{i=1}^n3\binom {\textrm{deg}_i}3$。 * $k=4$，$L^4(G)=L^3(L(G))$，所以我们需要知道 $T$ 的线图中每个点的度数，还需要快速求出每条边的贡献，这个是容易的。 进一步发现，线图上每个点对应着一棵不超过 $k+1$ 个点的树，表示是从原树的一个这样的连通子图得到的。 一棵小树 $R$ 对答案的贡献是其 $k$ 阶线图的点数。由于 $n$ 只有 $k+1$，我们可以暴力计算 $L^{k-4}(R)$ 再套公式计算。 之后，我们需要求出 $R$ 在 $T$ 中的出现次数，设 $f_{i, j}$ 表示 $T$ 的 $i$ 子树匹配了 $R$ 的 $j$ 子树的方案数。每次转移的时候新开一个状压数组。这样的复杂度是 $O(nk2^{k+1})$ 的。简单优化，发现叶子没有形态，不用状压，只用记录个数。这样复杂度就是 $O(nk2^{\frac {k+1}2})$ 的。之后别忘了考虑同构造成的重复计数，用树 hash 判。 枚举所有的 $R$ 是 $k^{k-2}$ 的，但是同构的两棵树我们只用计算一次。所以用树 hash 去重，最后只有 $1205$ 棵。 # [P4365 [九省联考2018]秘密袭击coat](https://www.luogu.com.cn/problem/P4365) 给一颗有 $n$ 个点的树，点权在 $1 \sim W$ 之间，求树的每一个联通块的第 $k$ 大点权之和。 $n, k, W \leq 1666$。 *** [评测链接](https://www.luogu.com.cn/record/43799830) 先把问题转化为，对于每个权值 $i$，求出大于等于 $i$ 的权值 $\geq k$ 的连通块个数。求和就是答案。 设 $f_{u, i, j}$ 表示 $u$ 号点，权值 $\geq i$ 的有 $j$ 个点的方案数。则有 $$f_{u, i, j}=\begin{cases}\prod_{\sum k=j} f_{v, i, k}& d_u <i\\ \prod_{\sum k = j-1}f_{v, i, k} & d_i \geq i\end{cases}$$ 这是卷积的形式，考虑插 $n+1$ 个值代入。 假如现在的值是 $x$，则有： $$\begin{cases}f_{u, i}=1&d_u < i \\ f_{u, i}=x& d_u \geq i\end{cases}$$ 设 $g_{u, j}$ 表示 $f_{u, j}$ 的和。 转移时： $$f_{u, j}=f_{u, j}\prod f_{v, j}+1$$ $$g_{u, j}=f_{u, j}+\sum g_{v, j}$$ 这显然是线段树合并的形式。 时间复杂度：$O(nk\log k)$。 # [P4383 [八省联考2018]林克卡特树](https://www.luogu.com.cn/problem/P4383) 给定一棵树，你需要去掉 $k$ 条边把他分成 $k+1$ 个联通子树，求子树直径和的最大值。 $n, k \leq 3 \times 10^5$，边权可以为负。 *** [评测链接](https://www.luogu.com.cn/record/33015651) 问题转化为选择 $k$ 条不相交的路径使得边权和最大。 设 $f_{i, j, 0/1/2}$ 表示 $i$ 号点，已经分了 $j$ 次，剩下的部分为空/链/路径的直径和最大值。 又发现，这个问题可以费用流。 所以答案是关于 $k$ 的凸函数。 wqs 二分优化这个 dp 即可。 # [P4424 [HNOI/AHOI2018]寻宝游戏](https://www.luogu.com.cn/problem/P4424) 给定 $n$ 个 01 串 $a_i$ 和 $m$ 个 01 串 $r_i$，你需要在 $a$ 相邻两个串中加入或/与运算。对于每个 $r_i$，求出运算式等于 $r_i$ 的方案数。 $n, m \leq 5000$，$q \leq 1000$。 *** [评测链接](https://www.luogu.com.cn/record/44968437) 我们从后往前考虑 * 与运算后有 $0$，那么答案是 $0$。 * 或运算后有 $1$，那么答案是 $1$。 否则继续考虑前一位。 发现这类似于字典序的比较。 所以我们把或运算看作 $0$，与运算看作 $1$，则一列 $a$ 的答案由 $a_i$ 和操作序列的数字翻转后的大小关系决定。 那需要获得 $r_i$ 相当于我们有若干不等式的限制。求交集即可。 # [P4425 [HNOI/AHOI2018]转盘](https://www.luogu.com.cn/problem/P4425) 一个转盘上有摆成一圈的 $n$ 个物品（编号 $1\sim n$），其中的 $i$ 个物品会在 $T_i$ 时刻出现。 在 $0$ 时刻时，任选 $n$ 个物品中的一个，我们将其编号为 $s_0$。如果 $i$ 时刻选择了物品 $s_i$，那么 $i+1$ 时刻可以继续选择当前物品或选择下一个物品。当 $s_i$ 为 $n$ 时，下一个物品为物品 $1$，否则为物品 $s_{i}+1$。求什么时候能访问到所有物品？ $m$ 次修改，每次修改将改变其中一个物品的出现时间。强制在线。 $n, m, T_i \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/44968448) 最优的策略应该为：在原地停若干时间，之后走一圈取完所有物品。这是因为我们总可以把等待时间往前提。 我们把 $T$ 序列倍长，那么答案为： $$\min_{i=1}^{n}\{\max_{i\leq j < i + n} (T_j-j)+i\}-n-1$$ 设 $a_j=T_j-j$。 $$\min_{i=1}^{n}\{\max_{i\leq j < i + n} a_j+i\}-n-1$$ 由于 $T_j-j-n<T_j-j$，所以可以放宽限制。 $$\min_{i=1}^{n}\{\max_{i\leq j < 2n} a_j+i\}-n-1$$ $a_j$ 当且仅当它是后缀最大值，才对答案有影响。 线段树维护（楼房重建）即可。 # [P4426 [HNOI/AHOI2018]毒瘤](https://www.luogu.com.cn/problem/P4426) 求独立集方案数。 $n \leq 10^5$，$m \leq n + 10$。 *** [评测链接](https://www.luogu.com.cn/record/31725570) 考虑 $3^{11}$ 枚举每个不在树边上的两点的情况。 这样复杂度是 $O(n3^{m-n+1})$ 的。 考虑给这 $22$ 个点建虚树。 每个点 $u$ 对其虚树上的父亲的贡献写作 $af_{u, 0}+bf_{u, 1}+c$。 先预处理这个 $a, b, c$ 即可。 # [P4466 [国家集训队]和与积](https://www.luogu.com.cn/problem/P4466) 给出 $n$，统计满足下面条件的数对 $(a,b)$ 的个数： 1. $1\le a<b \le n$。 2. $a+b$ 整除 $a\times b$。 $n\leq 2 ^{31}-1$。 *** [评测链接](https://www.luogu.com.cn/record/29731283) 设 $g=\gcd(a, b)$。 $$g(a'+b')|g^2a'b'$$ $$a'+b'|ga'b'$$ 由于当 $\gcd(a, b)=1$ 时，$a+b\not|ab$，所以 $a'+b'|g$。 答案为 $$\begin{aligned}&\sum_{1 \leq a< b \leq n}[\gcd(a, b)=1]\lfloor\frac n{b(a+b)}\rfloor\\ =&\sum_{1 \leq a < b \leq \sqrt n}[\gcd(a, b)=1]\lfloor\frac n{b(a+b)}\rfloor\\ =&\sum_{1 \leq a<b \leq \sqrt n}\lfloor\frac n{b(a+b)}\rfloor\sum_{d|\gcd(a, b)}\mu(d) \\ =&\sum_{d=1}^{\sqrt n}\mu(d)\sum_{1 \leq a < b \leq \frac {\sqrt n}d}\frac {n}{b(a+b)d^2}\end{aligned}$$ 枚举 $d, b$，对 $a+b$ 数论分块。 时间复杂度：$O(n^{\frac 34})$。 # [P4515 [COCI2009-2010#6] XOR](https://www.luogu.com.cn/problem/P4515) 坐标系下有若干个等腰直角三角形，且每个等腰直角三角形的直角顶点都在左下方，两腰与坐标轴平行。被奇数个三角形覆盖的面积部分为灰色，被偶数个三角形覆盖的面积部分为白色。已知 $n$ 个等腰直角三角形的顶点坐标及腰长，求灰色部分面积。 $n \leq 10$。 *** [评测链接](https://www.luogu.com.cn/record/45661123) 如何容斥？ 我们需要一个式子得到 $[2 \not| k]$，怎么做？ 设集合大小为 $i$ 的容斥系数为 $v_i$。 则有 $\sum_{i=0}^n \binom nik_i=[2 \not|k]$。 二项式反演得：$k_n=\sum_{i=0}^n(-1)^{n-1}[2\not|i]\binom ni

考虑 [n|x]x^n 的时候我们的做法是搞 n 次单位根，那这个就是二次单位根 \frac{(1+1)^n+(1-1)^n}2=(-2)^{n-1}。

P4517 [JSOI2018]防御网络

给定点仙人掌，求所有点集的子集的斯坦纳树边数期望。

*** [评测链接](https://www.luogu.com.cn/record/47336720) 考虑每一条边的贡献。 如果是割边，贡献是平凡的。 如果是环边，由于是点仙人掌，我们可以对每个环分开考虑。 考虑如果我们选的点集把环分割成了 $k$ 段，则贡献应该为环长 - 最长的一段。 所以我们需要对于每个长度 $i$ 求出在环上最长的距离 $=i$ 的点集数目 $c_i$，设环长为 $l$。答案为 $$\sum_i c_i(l-i)$$ 如何求 $c_i$？设 $f_{i, j, k}$ 表示从 $i$ 开始，到 $j$ 结束，最大值为 $l$ 的方案数。为什么要同时记录开始和结束？因为 $l-(j-i)$ 也是被划分出的一段，我们需要知道它的长度。 转移如下 $$\begin{cases} f_{i, j, k} \leftarrow f_{i, j-p, k} & p \leq k \\ f_{i, j, p} \leftarrow f_{i, j-p, k} & p > k\end{cases}$$ 之后 $f_{i, j, k}\leftarrow f_{i, j, k}(2^{\textrm{siz}_j}-1)

P4546 [THUWC2017]在美妙的数学王国中畅游

给定一棵树，你需要维护以下操作

• 加删边
• 修改点权
• 求一条路径上点权的 f 之和。

其中 f 是一个函数，可以是一次函数、\sin, \exp。

*** [评测链接](https://www.luogu.com.cn/record/38401000) 烂题。 一次函数可以直接做。实际上多项式都能维护。 泰勒展开 $20$ 项，没了。 # [P4547 [THUWC2017]随机二分图](https://www.luogu.com.cn/problem/P4547) 有若干边组，组有三种类型： * 一条边，出现的概率是 $50\%$。 * 两条边，$50\%$ 同时出现，$50\%$ 同时不出现。 * 两条边，$50\%$ 第一条边出现，$50\%$ 第二条边出现。 求完美匹配数量的期望。 $n \leq 15$。 *** [评测链接](https://www.luogu.com.cn/record/39226446) 根据期望的线性性，我们只用求出每种完美匹配存在的概率。 考虑一个边组在完美匹配里的出现情况。 拿第二种举例，应该是这样的 * $50\%$ 第一条边出现在完美匹配中。 * $50\%$ 第二条边出现在完美匹配中。 * $50\%$ 两条边同时出现在完美匹配中。 * $50\%$ 两条边同时不出现在完美匹配中。 我们把一个边组拆成两条 $50\%$ 的边和一个 $25\%$ 的边组，可以发现他的出现情况满足上述要求。 同理第三个就是 $-25\%$ 的边组。 之后状压 dp 即可。 # [P4565 [CTSC2018]暴力写挂](https://www.luogu.com.cn/problem/P4565) 给定两棵树，求 $$ \mathrm{depth}(x) + \mathrm{depth}(y) - ({\mathrm{depth}(\mathrm{LCA}(x,y))}+{\mathrm{depth'}(\mathrm{LCA'}(x,y))})$$ 最大值。 $n \leq 366666$。 *** [评测链接](https://www.luogu.com.cn/record/39793578) 和通道差不多啊？ # [P4566 [CTSC2018]青蕈领主](https://www.luogu.com.cn/problem/P4566) 若区间 $[l, r]$ 满足 $\max a-\min a = r - l + 1$，那我们称其为连续区间。 给定数组 $L$，表示每个位置为右端点时最长的连续区间的左端点。 求合法的排列 $a$ 的个数。 $n \leq 5 \times 10^4$。 *** [评测链接](https://www.luogu.com.cn/record/38156587) 计数题，咕。 # [P4607 [SDOI2018]反回文串](https://www.luogu.com.cn/record/44809265) 求字符集为 $k$，长度为 $n$ 的本质不同的回文串或回文串的循环同构串个数。 $n \leq 10^{18}$。 *** [评测链接](https://www.luogu.com.cn/record/44809265) 考虑一个回文串，其最小循环节为 $d$。 那么它的贡献 $h_d$ 为 $\begin{cases}d & d\bmod2=1\\ \frac d2 & d\bmod 2=0\end{cases}

因为最小循环节也是一个回文串。转 \frac d2 次后变成了一个新的回文串。所以两个串造成了 d 的贡献。

设 f_i 表示最小循环节为 i 的回文串个数。

则有 (f*1)(n)=k^{\frac {n+1}2}。

设 g_i=k^{\frac {n+1}2}。

则有 f=g*\mu。

那么答案为

\begin{aligned}&\sum_d h_df_d\\=&\sum_d h_d\sum_{p|d}g_p\mu_{\frac dp}\\ =&\sum_p g_p\sum_{d|\frac np}h_{dp}\mu_d\end{aligned}

发现 h_{dp}=dh_p，除非 d 是偶数 p 是奇数。

而这个时候，\sum_{d|\frac np} h_{dp}\mu_d=p\sum_{d|\frac np} h_d\mu_d

后面那个东西，我们考虑把 \frac np 的所有因数分成奇数和偶数两部分，奇数 * 2 都能在偶数里找到对应的值。所以两两消去，结果为 0。

所以 h_{dp}=dh_p。

那么答案为

\sum_p g_ph_p\sum_{d|\frac np} d \mu_d

后面怎么算？

\sum_{d|n}d\mu_d=\prod_{p|n, p\in prime}(1-p)

pollard_rho 即可。

P4619 [SDOI2018]旧试题

\sum_{i = 1}^A\sum_{j=1}^B\sum_{k=1}^Cd(ijk) *** [评测链接](https://www.luogu.com.cn/record/32127505) 咕。 # [P4687 [IOI2008] Pyramid Base](https://www.luogu.com.cn/problem/P4687) 给定一个 $n \times m$ 的网格，其中有 $k$ 个矩形，删去一个矩形有一个花费 $v_i$，你需要删去一些矩形，使得总花费不超过 $B$，且从不被矩形覆盖的区域选出一个正方形的边长尽可能大。 $k \leq 3 \times 10^4$，$B \leq 2\times 10^9$。 $k \leq 4 \times 10^5$，$B=0$。 *** [评测链接](https://www.luogu.com.cn/record/27094068) 扫描线。 当 $B=0$ 时，我们扫描到 $r$，维护一下 $l, r$ 最长全 $0$ 子段。如果这个长度小于 $r-l+1$，我们就让 $l$ 向右移动。 当 $B\neq 0$ 时，我们先二分答案，考虑正方形左上角的位置。每个矩形需要造成花费的位置还是一个矩形。所以还是扫描线。 # [P4694 [PA2013]Raper](https://www.luogu.com.cn/problem/P4694) $n$ 道题, 第 $i$ 天可以花费 $a_i$ 准备一道题, 花费 $b_i$ 打印一道题, 每天最多准备一道, 最多打印一道, 准备的题可以留到以后打印, 求最少花费使得准备并打印 $k$ 道题。 $n, k \leq 5 \times 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/51826249) 考虑费用流。 $s$ 向 $i$ 连边 $(1, a_i)$，$i$ 向 $t$ 连边 $(1, b_i)$，$i$ 向 $i+1$ 连边 $(\infty, 0)$。 开始时限制流量为 $k$，跑最小费用最大流。 由于它是费用流所以它是凸的。 所以 wqs 二分。 当然，也可以线段树维护最短路。维护一下所有的 $\min a, \min b, \min dis$，反边的 $\min a, \min b, \min flow, \min dis$ 即可。 # [P4705 玩游戏](https://www.luogu.com.cn/problem/P4705) 给定两个序列 $a, b$。 对于每个 $k$，求出 $\sum_{i=1}^n \sum_{j=1}^m (a_i+b_j)^k$。 $n, m \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/32361419) 计数题，咕。 # [P4707 重返现世](https://www.luogu.com.cn/problem/P4707) 有 $n$ 种物品，每次随机生成一种，每种有一个生成概率。 求生成 $k$ 个不同的物品的期望时间。 $n \leq 1000$，$n-k \leq 10$。 *** [评测链接](https://www.luogu.com.cn/record/43443370) 计数题，咕。 # [P4769 [NOI2018] 冒泡排序](https://www.luogu.com.cn/problem/P4769) 求冒泡排序达到交换次数下界的排列个数。 $n \leq 6 \times 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/37922519) 问题等价于：不存在长度为 $3$ 的下降子序列。 这又等价于：能够把序列划分成两个集合，使得他们都是不降的。 设 $f_{i, j}$ 表示填了前 $i$ 个数，第一个集合最大值为 $j$ 的方案数。 那么如果填入第一个集合，那必须 $\geq j$。 否则必须是没有填的中最小的，否则最小的那个就没地可去了。 所以 $f_{i, j}=\sum_{k \leq j} f_{i - 1, k}$。 这相当于在二维平面上只能向左向上，不能经过 $y=x-1$ 的方案数。 这样我们就能 $O(1)$ 计算一个位置的 $f$。 再考虑字典序的问题，考虑何时与限制分界。这样推出来还是一列 $f$ 的前缀和的形式，等于下一列的一个位置 $f$，$O(1)$ 计算即可。 时间复杂度：$O(n)$。 # [P4770 [NOI2018] 你的名字](https://www.luogu.com.cn/problem/P4770) 给定一个模板串 $S$，多组询问，每次给出一个询问字符串 $T$ 和一个区间 $(l,r)$。要求出 $T$ 有多少个**本质不同**的子串，满足这个子串没有在 $S$ 的 $(l,r)$ 这段区间当中出现。 $|S| \leq 5 \times 10^5$，$Q \leq 10^5$，$\sum |T| \leq 10^6$。 *** [评测链接](https://www.luogu.com.cn/record/29945741) 已经成烂大街的套路题了。 # [P4827 [国家集训队] Crash 的文明世界](https://www.luogu.com.cn/problem/P4827) 给定一棵树，对于每个 $u$，求出 $\sum_{i=1}^n \textrm{dis}(u, i)^k$。 $n \leq 5 \times 10^4$，$k \leq 150$。 *** [评测链接](https://www.luogu.com.cn/record/34276289) $m^n=\sum_{i=0}^n{n\brace i}\binom mii! \begin{aligned}&\sum_{i=1}^n \sum_{j=0}^k{k \brace j}\binom{\textrm{dis}(u, i)}{j}j!\\ =&\sum_{j=0}^k{k \brace j}j!\sum_{i=1}^n \binom{\textrm{dis}(u, i)}{j}\end{aligned}

设 f_{u, i} 表示 \sum_{v\in \textrm{subtree}_u} \binom{\textrm{dis}(u, v)}{i}。

再设 g_{u, i} 表示 \sum_{v\notin \textrm{subtree}_u} \binom{\textrm{dis}(u, v)}{i}

转移即可。

P4841 [集训队作业2013]城市规划

求出 n 个点的简单 (无重边无自环) 有标号无向连通图数目。

评测链接

g=\sum\frac {2^{\binom i2}}{i!}x^i ans=\ln g

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

区间逆序对（可离线）。

250ms, 31.25MB。 *** [评测链接](https://www.luogu.com.cn/record/49862678) 莫队二离模板题。 具体怎么搞呢，首先可以用树状数组+莫队做到 $O(n \sqrt n \log n)$，但我们发现我们使用树状数组时有 $O(n\sqrt n)$ 次修改，$O(n)$ 次查询，这个可以通过分块平衡。所以把所有的修改/询问记录下来，重新搞。 # [P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III](https://www.luogu.com.cn/problem/P5048) 区间众数（强制在线）。 $n, m \leq 5 \times 10^5$。 62.5MB *** [评测链接](https://www.luogu.com.cn/record/49875430) 分块。 设 $f_{i, j}$ 表示第 $i$ 个块到第 $j$ 个块的众数的出现次数。 零散块我们考虑这个位置之前，这个值在序列出现次数为 $k$，那我们只用从第 $k+ans$ 次开始扩展即可。这样扩展只有 $O(\sqrt n)$ 次。 # [P5090 [eJOI2018]互素树](https://www.luogu.com.cn/problem/P5090) 提交答案题。 给定一棵树，你需要给每个点设置一个 $[1, n]$ 的权值，权值两两不同。并且一条边相连的两个点不互素。 $nT \leq 10^5$。 *** 瞎退火就过了。 # [P5206 [WC2019]数树](https://www.luogu.com.cn/problem/P5206) 有两棵 $n$ 个结点的树，它的权值定义为 $y$ 的两棵树边的交集的大小次方。 有三个问题： 1. 给定两棵树，求权值。 2. 给定一棵树，求权值期望。 3. 求权值期望。 $n \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/31100752) $$\begin{aligned}&\sum_{E_2}y^{n-|E_1\cap E_2|}\\ =&\sum_{S}y^{n-|S|}\sum_{S=E_1\cap E_2}1\\ =&\sum_{S}y^{n-|S|}\sum_{S\subset E_1\cap E_2}\sum_{P \subset S}(-1)^{|S|-|P|}y^{n-|P|}\\=&\sum_{S\subset E_1}g(S)y^{n-|S|}\sum_{P \subset S}(-y)^{|S|-|P|}\\ =&\sum_{S \subset E_1}g(S)y^{n-|S|}(1-y)^{|S|}\end{aligned}$$ 其中，$g(S)$ 表示包含边集 $S$ 的树的个数。 Cayley 定理指出，包含一个边集的树的个数为 $n^{k-2}\prod a_i$，其中 $k$ 为连通块个数，$a_i$ 为每个连通块的大小。 $\sum_{S\in E_1}y^k

P5244 [USACO19FEB] Mowing Mischief P

二维平面上有若干个点，你从 (0, 0) 走到 (T, T)，问经过最多的点的情况下，代价最小为多少。

设经过的点为 a_1, a_2,\ldots, a_k，代价为 \sum (x_{a_{i+1}}-x_{a_i})(y_{a_{i+1}}-y_{a_i})。

*** [评测链接](https://www.luogu.com.cn/record/38812056) 按照能经过的点的个数分层。 每两层之间的转移，肯定是留 $x$ 递增 $y$ 递减的一排。 转移式为 $$f_i=\min \{f_j+(x_j-x_i)(y_j-y_i)\}$$ 考虑两个转移点 $j, k$（$j > k$），$j$ 优于 $k$ 当且仅当 $$f_j+(x_j-x_i)(y_j-y_i) < f_k+(x_k-x_i)(y_k-y_i)$$ $$f_j-f_k<x_ky_i-x_iy_k+x_ky_k-x_jy_j+x_iy_j+x_jy_i$$ $$(f_j-x_jy_j)-(f_k-x_ky_k) < (x_i-y_i)(y_j-y_k)$$ $$\frac {(f_j-x_jy_j)-(f_k-x_ky_k)}{y_j-y_k} > x_i-y_i$$ 发现当 $i$ 递增时，$x_i-y_i$ 递增，到某个分界点后 $k$ 比 $j$ 更优。 也就是说，决策点始终在向前移。 所以用决策单调性的那一套理论做就行了。 # [P5279 [ZJOI2019]麻将](https://www.luogu.com.cn/problem/P5279) 把一副 $4n$ 张牌的纸牌随机打乱，每一次依次加入，求存在一个子集胡牌的期望加入次数。 $n \leq 100$。 *** [评测链接](https://www.luogu.com.cn/record/38776701) 考虑给定一副牌，如何判定他是否是胡的。 我们把牌从小到大排序，设 $f_{i, j, k, l}$ 表示前面留了 $j$ 个 $i$，$k$ 个 $i - 1$，$l$ 个对子，最多能获得多少个面子。 那么设 $F_{i, j, k, l, q}$ 表示 $f_{i, j, k, l}=q$ 的状态。 那么这样的 $F$ 一共有 $2092$ 种。 我们设 $g_{i, j}$ 表示放了 $i$ 张牌，走到了状态 $j$ 的方案数。转移即可。 # [P5284 [十二省联考2019]字符串问题](https://www.luogu.com.cn/problem/P5284) 给定一个模板串 $S$，有两个字符串数组 $A, B$，每个字符串都是 $S$ 的一个子串。 有 $m$ 条边，$(u, v)$。 若 $B_i$ 是 $A_j$ 的前缀，则有一条边 $(i, j)$。 求一条路径使得经过的字符串的长度和最大。 $|S|, n, m \leq 2 \times 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/43006821) 建出后缀树。 每个点的后缀链接向他连边。 每个 $B$ 向它在后缀树上对应的结点连边。 每个 $A$ 被它在后缀树上对应的结点连边。 $m$ 条边也加进来。 就成了一个 tarjan + DAGdp。 当然，有个问题，在后缀树的一个节点中可能有 $|B| > |A|$ 的情况。 所以对于每一个节点我们把他们按照长度连成一条链即可。 # [P5287 [HNOI2019]JOJO](https://www.luogu.com.cn/problem/P5287) 有一个字符串，最初为空。你需要支持以下操作： * 在末尾插入 $x$ 个 $c$ 字符。 * 回滚到第 $x$ 次操作。 * 求每个前缀的 border 的长度和。 $n \leq 10^5$，$x \leq 10^4$。 *** [评测链接](https://www.luogu.com.cn/record/47925387) 首先没有强制在线，所以回滚操作形成的树形结构可以直接建出来。这样我们只用支持撤销，这是很简单的。 我们考虑加入一段字符后，它的 border 应该形如若干段，长度递减。 那我们只用找到这些段能贡献的长度就好。 我们跳倒数第二段字符的 border，看一下 border 的下一段字符是不是 $c$，如果是，那么就可以贡献。 但是我们不能暴力跳 border。考虑我们只需要字符串的局部结构而不需要全局结构。所以当 border $\geq \frac {\textrm{len}}2$ 的时候，它的周期 $\leq \frac {\textrm{len}}{2}$，我们只用考虑第一个周期即可。 这样跳，复杂度是 $\log \textrm{len}$ 的。 # [P5291 [十二省联考2019]希望](https://www.luogu.com.cn/problem/P5291) 给定一棵树，让你找出 $k$ 个连通块，使得这些连通块交集中存在一点让这些连通块中任意一点到这个点的距离不超过 $L$。求选择连通块的方案数。 $n \leq 10^6$，$k \leq 10$。 *** [评测链接](https://www.luogu.com.cn/record/44500155) 设 $f_{u, l}$ 表示以 $u$ 为子树，与 $u$ 距离不超过 $l$ 的连通块个数。$g_{u, l}$ 表示除去 $u$ 的子树（$u$ 除外），与 $u$ 距离不超过 $l$ 的连通块个数。 $$f_{u, i} = \prod f_{v, i-1}+1$$ $$g_{u, i}=g_{fa_u, i}\prod_{v \neq u, v \in son_{fa_u}} f_{v, i-2}+1$$ 答案是 $\sum (f_{u, L}-1)g_{u, L}$。 发现 $f_u$ 的下标范围不超过 $\textrm{dep}_u$，考虑长链剖分优化。这部分是很常规的。 $+1$ 可以用加法 tag。 注意到我们存的是“不超过”，所以我们没有维护的部分实际上是有值的，我们可以用一个乘法 tag（因为他已经接受了 $+1$ 的 tag），这样，我们需要把之前的值全部乘一个逆元，那假如最后是 $0$，我们特判一下，再维护一个 $0$ 标记。 $g$ 的优化是困难的。 考虑最后答案的统计方式，我们维护 $g$ 也只用维护到 $\textrm{dep}_u$ 位。 $g$ 的转移是自上向下的，那么我们让重儿子从父亲继承，其他儿子从父亲剥离。 那这个 $\prod_{v \neq u, v \in son_{fa_u}} f_{v, i-2}$ 怎么计算？ 如果直接维护，我们需要对于每个前后缀，都求出乘积数组。这个可以用主席树。但是在这一题中，任何 $\log$ 都是不能接受的。 所以我们可以这样进行：前缀边做边乘，这样不用记录每个版本。后缀先全部做完，再进行回退操作，这样也不用记录每个版本。 最后的最后，发现乘法 tag 需要求逆元使得我们的复杂度带了 $\log$。这怎么办呢？ 我们需要求逆元的位置是 $f_{u, \textrm{len}_u}$，即不考虑长度限制的情况，我们可以先用一次 dp 求出来。 之后我们需要求 $n$ 个数的逆元。 $$inv_i = \prod_{j=1}^ia_j \times \prod_{j=1}^{i-1}inv_j$$ 所以我们只用求出前缀逆元即可。这个可以先求出所有数的乘积的逆元再一个一个推回来，就像我们算阶乘的逆元一样。 时间复杂度：$O(n)$。 # [P5292 [HNOI2019]校园旅行](https://www.luogu.com.cn/problem/P5292) 给定一张无向图，每个点有一个 $0/1$ 点权，$q$ 次询问，每次询问是否存在一条 $u$ 到 $v$ 的路径（不需要是简单路径），满足这条路径经过的点的点权按照字符串顺序写下是一个回文串。 $n \leq 5 \times 10^3$，$m \leq 5 \times 10^5$，$q \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/36283703) 设 $f_{u, v}$ 表示 $u, v$ 之间是否存在这样一条路径。 每次转移，考虑从 $f_{u, v}=1$ 的位置扩展， $u, v$ 同时扩展一次，到达 $u', v'$，如果 $u', v'$ 的点权相同，那么 $f_{u', v'}=1$。 这样的复杂度是 $O(m^2)$ 的。 考虑一个同色连通块，如果它存在奇环，那么存在一个 $L$，使得对于连通块里的所有 $(u, v)$，对于每一个 $d \geq L$，存在长度 $=d$ 的路径。因为我们可以绕一条边来回走。这样，我们可以构造出两个完全相同的子串。 如果不存在，那么多一个奇偶性的限制。 如果我们把所有的这样的情况应用进去，复杂度是正确的。 更简单的做法是，我们只保留一棵生成树，如果存在奇环，那么再在某一个点上加一个自环。 这样还能满足上述性质，而边数降到了 $O(n)$。 # [P5295 [北京省选集训2019]图的难题](https://www.luogu.com.cn/problem/P5295) 给定一张图，你需要选出一个子集，使得这个子集没有环，子集的补集没有环。 $T \leq 10$，$n \leq 500, m \leq 10^3$。 *** [评测链接](https://www.luogu.com.cn/record/51874882) 一张图是合法的当且仅当其所有导出子图 $(V, E)$ 满足 $|E| \leq 2|V|-2$。 必要性显然。充分性考虑归纳法。我们通过点数为 $|V|-1$ 的图成立推出点数为 $|V|$ 的成立。 设 $d(u)$ 表示 $u$ 的度数，我们取 $d$ 最小的一个作为我们加入的点 $u$。 那么 $1 \leq d(u) \leq 3$。否则 $\sum d=4|V|$，$|E|=2|V|$，不满足条件。 若 $d(u) \leq 2$，我们设相邻的点为 $v_1, v_2$，把 $(v_1, u)$ 加入第一个森林，$(v_2, u)$ 加入第二个森林，仍然满足性质。 若 $d(u)=3$，设相邻的点为 $v_1, v_2, v_3$。那么去掉 $u$ 及其邻边的所有图 $G$ 满足 $|E|<2|V|-2$。 我们考虑三个导出子图 $H_1(E_1, V_1)$, $H_2(E_2, V_2)$, $H_3(E_3, V_3)$，$H_1$ 不包含 $(u, v_1)$ 但包含 $v_2, v_3$，$H_2$ 不包含 $(u, v_2)$ 但包含 $v_1, v_3$，$H_3$ 不包含 $(u, v_3)$ 但包含 $v_1, v_2$。这样的 $H_1, H_2, H_3$ 有很多种。但**至少有一个** $i$ **满足不存在** $H_i$ **使得** $|E_i|=2|V_i|-2$。 引理：若 $G_1(E_1, V_1), G_2(E_2, V_2)$ 满足 $|E_1|=2|V_1|-2, |E_2|=2|V_2|-2$，则 $G_1 \cap G_2(E'_1, V'_1), G_1 \cup G_2(E'_2, V'_2)$ 满足 $|E_1'|=2|V_1'|-2, |E_2'|=2|V_2'|-2$。因为交 + 并 = 和，假如一个没达到上界，另一个就要超过上界。 使用反证法，若三个 $H$ 都能达到上界，那他们的并也达到了上界，而他们的并，就是 $G$。矛盾。 那么假设 $H_1$ 达不到上界，那么我们在 $H_1$ 中加入一条边 $(v_2, v_3)$，这样 $H'_1$ 也是合法的。 于是我们考虑这样一张图：在 $(V, E)$ 的基础上，除去 $u$ 的出边，加入 $(v_2, v_3)$，根据归纳假设，它能够分成两个森林。 我们设第一个森林包含了 $(v_2, v_3)$，那么我们把这条边删去，加入 $(u, v_2), (u, v_3)$，它还是一个森林。第二个森林加入 $(u, v_1)$，它还是一个森林。 原命题得证。 也就是说，我们只用判断这张图是否满足对于所有的子图满足 $|E| \leq 2|V|-2$。 也就是说，$\max\{|E|-2|V|\} \leq -2$。 这是一个最大权闭合子图的模型。考虑一条边的权值为 $1$，一个点的权值为 $-2$，我们要求的是最大权闭合子图。 **但是有一个问题！**这个子图必须非空，因为空的图被判定为不合法了。 所以我们钦定一个点一定被选，把它在网络流中的点删去，最后把答案直接 $-2$ 即可。 这样的复杂度是 $nm \sqrt n$ 的。 （好像这样就能过了，但是 uoj 那题就过不了） 考虑优化，发现每次是删一条边后的最大流。使用退流即可。 时间复杂度：$O(nm)$。 # [P5298 [PKUWC2018]Minimax](https://www.luogu.com.cn/problem/P5298) 有一棵 $n$ 个结点的有根树，根是 $1$ 号结点，且每个结点最多有两个子结点。 定义结点 $x$ 的权值为： * 若 $x$ 没有子结点，那么它的权值会在输入里给出，**保证这类点中每个结点的权值互不相同**。 * 否则它的权值有 $p_x$ 的概率是它的子结点的权值的最大值，有 $1-p_x$ 的概率是它的子结点的权值的最小值。 假设 $1$ 号结点的权值有 $m$ 种可能性，**权值第 $i$ 小**的可能性的权值是 $V_i$，它的概率为 $D_i$（$D_i<0$），求： $$\sum_{i=1}^{m}i\cdot V_i\cdot D_i^2$$ *** [评测链接](https://www.luogu.com.cn/record/32150520) 设 $f_{u, i}$ 表示 $u$ 号结点取值为 $V_i$ 的概率。转移如下： $$f_{u, i}=f_{v_1, i}(p_i\sum_{j < i}f_{v_2, j}+(1-p_i)\sum_{j > i}f_{v_2, j})+f_{v_2, i}(p_i \sum_{j < i}f_{v_1, j}+(1-p_i)\sum_{j > i}f_{v_1, j})+f_{v_1, i}f_{v_2, i}$$ 那我们用线段树维护前缀和，后缀和，前缀概率和，后缀概率和。线段树合并即可。 # [P5305 [GXOI/GZOI2019]旧词](https://www.luogu.com.cn/problem/P5305) 给定一棵 $n$ 个点的有根树，节点标号 $1 \sim n$，$1$ 号节点为根。 给定常数 $k$。 给定 $Q$ 个询问，每次询问给定 $x,y$。 求： $$\sum\limits_{i \le x} \text{depth}(\text{lca}(i,y))^k$$ *** [评测链接](https://www.luogu.com.cn/record/24258605) 离线，相当于链加链查询。 只不过每个点有一个权重。线段树也是可以维护的。 # [P5320 [BJOI2019]勘破神机](https://www.luogu.com.cn/problem/P5320) 设 $f_i$ 表示 $m \times i$ 的网格填入 $1 \times 2$ 或 $2 \times 1$ 的骨牌，填满的方案数。 求 $\sum_{i=l}^r \binom{f_i}k$。 $m = 2/3$，$l, r \leq 10^{18}$，$k \leq 500$。 *** [评测链接](https://www.luogu.com.cn/record/44856472) 当 $m=2$ 时，考虑 $f$ 的递推式，根据上一次是横着放还是竖着放得到：$f_i=f_{i-1}+f_{i-2}$，哈？斐波那契数列，既然是把它放到了组合数里，那我们考虑斐波那契的通项公式： $$f_i=\frac 1{\sqrt 5}(\frac{1+\sqrt 5}2)^n-\frac 1{\sqrt 5}(\frac{1-\sqrt 5}2)^n$$ 它的形式为：$f_i=Ax^n+By^n$。 $$\begin{aligned}&\sum_{l=i}^r \binom{f_i}k\\ =& \frac 1{k!}\sum_{i=l}^r\sum_{j=0}^k(-1)^{k-j}{k \brack j}f_i^j\\ =&\frac 1{k!}\sum_{i=l}^r\sum_{j=0}^k(-1)^{k-j}{k \brack j}(Ax^n+By^n)^j\\ =&\frac 1{k!}\sum_{i=l}^r\sum_{j=0}^k(-1)^{k-j}{k \brack j}\sum_{l=0}^jA^lB^{j-l}(x^ly^{j-l})^i\\ =&\frac 1{k!}\sum_{j=0}^k(-1)^{k-j}{k \brack j}\sum_{l=0}^jA^lB^{j-l}\sum_{i=l}^r (x^ly^{j-l})^i\end{aligned}$$ 枚举 $i, j$，后面的是一个等比数列。直接算就好了。 当然，$\sqrt 5$ 有可能不存在，所以扩域一下。 至于 $m=3$，递推式不一样而已，实际上还是能求出一个 $Ax^n+By^n$ 的通项的。 # [P5321 [BJOI2019]送别](https://www.luogu.com.cn/problem/P5321) 有一个 $n \times m$ 的网格，网格的每条边要么启用要么禁用。边缘的一圈边使用被启用。你需要支持以下操作 * 启用一面墙。 * 禁用一面墙。 * 求从一个位置出发贴墙走（始终左手贴墙向前走）到一个位置的距离。 $n, m \leq 500$，$q \leq 2 \times 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/44675528) 考虑用一棵平衡树维护一个环。这样环会在某处断开。 加入删除的时候，有可能会合并环，扩展环，新增环。直接合并分裂是不行的，因为有可能我们要操作的跨过了断开的位置。 这需要我们支持一个操作，改变环的断裂位置，这个用平衡树合并分裂就好了。 然后就一大堆分类讨论。 用平衡树维护环，还见过一题，给定一个排列，每次俩操作：交换俩元素 / 询问至少交换多少次才能使得数组排好序，由于答案是 $n-$ 环数，所以要维护一下。 # [P5327 [ZJOI2019]语言](https://www.luogu.com.cn/problem/P5327) 给定一棵树和 $m$ 条树上的链，求对于树上每个点 $x$ ，包含它的链的并集的大小之和。 $n, m \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/38790497) 怎么维护一个点能到达的集合？树剖线段树维护一下这个并集，对于每条链树上差分一下。 然后如何对所有点维护？线段树合并。 # [P5331 [SNOI2019]通信](https://www.luogu.com.cn/problem/P5331) $n$ 个排成一列的哨站要进行通信。第 $i$ 个哨站的频段为 $a_i$。 每个哨站 $i$ 需要选择以下二者之一： * 直接连接到控制中心，代价为 $W$； * 连接到前面的某个哨站 $j$ ($j<i$)，代价为 $|a_i-a_j|$。 每个哨站只能被后面的至多一个哨站连接。 请你求出最小可能的代价和。 $n \leq 1000$。 *** [评测链接](https://www.luogu.com.cn/record/32099126) 有一个显然的费用流做法：$(s, u, 1, 0), (u, v', 1, |a_u-a_v|), (u, t, 1, W), (u', t, 1, 0)$，这样我们能保证每条链只有一个点走了 $W$ 那条边。 如何优化？考虑分治，每次仅考虑左半侧对右半侧的连边。连边的贡献形如在数轴上两点的距离。那我们就建出来一个数轴，每走一单位的费用是 $1$，左半侧在它的 $a$ 的位置连向数轴，右半侧在它的 $a$ 的位置连出。然后离散化一下数轴就好。 这样边数降到 $O(n \log n)$，再跑费用流，就过了。 主席树优化建图常数太大，SNOI 老爷机会 T。 # [P5332 [JSOI2019]精准预测](https://www.luogu.com.cn/problem/P5332) 给定 $n$ 个人和 $m$ 组限制，分为两种： * 如果 $x$ 在 $t$ 时间前死了，则 $y$ 在 $t+1$ 时间前也死了。 * 如果 $x$ 在 $t$ 时间还活着，则 $y$ 在 $t$ 时间前死了。 请你对每一个人计算出在 $T+1$ 时间时可能与其同时存活的人数。如果这个人在 $T+1$ 时刻必然死则答案为 $0$。 $n\leq 5\times 10^4$，$m\leq 10^5$，$T\leq 10^6$。 *** [评测链接](https://www.luogu.com.cn/record/44933533) 这是一个 2-SAT 的模型。 暴力建图是 $O(nT)$ 个点的。但是大部分情况都类似一条链，我们是不需要链上的点的，可以把他缩成一条边。 这样点数就是 $O(n+m)$ 的。 之后就可以 bitset 了。我们还发现原图是个 DAG（因为同一层只有活 -> 死的边），所以连缩点都不用了。 空间开不下，所以分部分做 bitset。 # [P5333 [JSOI2019]神经网络](https://www.luogu.com.cn/problem/P5333) 给定 $n$ 棵树，两棵树之间的任意点对也有连边。求哈密顿回路数量。 $\sum |T| \leq 5 \times 10^3$，$n \leq 300$。 *** [评测链接](https://www.luogu.com.cn/record/42515799) 设 $f_{u, i}$ 表示把第 $u$ 棵树分成 $i$ 条链的方案数。这个可以通过 dp 解决。 假设我们知道了每棵树选的链条数，方案数等价于求序列的方案数，其中第 $i$ 种数有 $a_i$ 种，需要保证相邻的种类不相同。 这个我们可以通过容斥解决：考虑强制 $d$ 个位置不合法，那么这 $d$ 个位置合并了，相当于让 $a$ 减小这么多次。 我们把这个式子拿生成函数写出来。对于一棵树，它的 EGF 为： $$\sum_{i=1}^{|T|}f_ii!\sum_{j=0}^{i-1}(-1)^{i-j}\binom{i-1}{j}\frac {x^{i-j}}{(i-j)!}$$ 把它们卷起来就好了。 有几个特殊的地方 * 第一棵树必为起点，所以我们钦定一条链，让他不参与可重排列计算。 * 首尾链种类不能相同，我们减去这种情况。 暴力卷积即可。 # [P5342 [TJOI2019]甲苯先生的线段树](https://www.luogu.com.cn/problem/P5342) 同 CF750F。 # [P5359 [SDOI2019]染色](https://www.luogu.com.cn/problem/P5359) 给定 $2\times n$ 的格点图。其中一些结点有着已知的颜色，其余的结点还没有被染色。 一个合法的染色方案不允许相邻结点有相同的染色。 现在一共有 $c$ 种不同的颜色，依次记为 $1$ 到 $c$。 求有多少对未染色结点的合法染色方案。 $n, c \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/44763160) 设 $f_{i, a, b}$ 表示前 $i$ 列，第 $i$ 列上面是 $a$ 下面是 $b$ 的方案数。 发现空行的转移系数是一样的，所以可以预处理 $k$ 个空行的转移系数。 之后我们只用考虑那些不是空行的位置了。 这样其实可以缩掉一维。因为至少一个已经被填了。 那我们设 $f_i$ 表示在当前这一行，空的那一个位置填 $i$ 的方案数。 那么有全局加，全局乘，单点修改，全局修改，单点查询，全局查询。 这个随便搞搞就行了，甚至有不带 $\log$ 的做法。 注意空行的转移，左右两个边界的位置与值的关系是会影响转移的。但是状态只有 $O(1)$ 种，就考虑哪些位置被填了，哪些位置的值相等就好了。 # [P5360 [SDOI2019]世界地图](https://www.luogu.com.cn/problem/P5360) 给定一个 $n \times m$ 的网格图，其中第一列和最后一列也有边（网格“带”）。 $q$ 次询问，每次询问删去 $[l, r]$ 列之间的所有点后的最小生成树。 $n \leq 100$，$m \leq 10^4$，$nq \leq 10^6$。 *** [评测链接]() 首先，我们对于每个前后缀求出其最小生成树。合并的时候像 lct 那样删边。 这样存储都是个问题。但是我们发现，实际上除了最靠边的的连接关系，别的都不用存。 所以我们可以考虑对于每个前后缀求出其最小生成树最靠边的一排点的虚树。 那如何求呢？我们考虑递推，每次都要往最内部加一排点，所以我们再把内部的点也考虑进虚树就好了。 # [P5362 [SDOI2019]连续子序列](https://www.luogu.com.cn/problem/P5362) 定义 $\textbf{T. M.}$ 序列 $\{T_n\}$ 为如下形式得布尔序列： - $T_0=0$； - $T_{2n}=T_n$; - $T_{2n+1}=1-T_n$。 现在给定一个布尔序列（01字符串）$S$ 和一个非负整数 $k$，请统计一下一共有多少种 $\textbf{T. M.}$ 序列的连续子序列 $T$ 满足： - $S$ 是 $T$ 的前缀； - $T$ 是由 $S$ 额外在右侧添加了恰好 $k$ 项形成的。 $|S| \leq 100$，$k \leq 10^{18}$。 *** [评测链接](https://www.luogu.com.cn/record/44776914) 妙妙题。 这个序列的构造可以理解为：每次将序列中的一个 `0` 变为 `01`，`1` 变为 `10`。 这让我们想到降低 $S$ 的分辨率，即每次做它的逆过程，进行匹配，匹配得到的数量就是答案。因为每个在低分辨率的匹配扩展之后都能在高分辨率处匹配。 那我们分两种情况考虑，$12, 34, 56, 78$ 这样降分辨率，还是 $X1, 23, 45, 67$ 这样降，递归处理就好了。 # [P5366 [SNOI2017]遗失的答案](https://www.luogu.com.cn/problem/P5366) 给定 $n, g, l$。 $q$ 次询问，每次询问 $1 \sim n$ 中选择若干数，必选 $x$，$\gcd=g, \textrm{lcm}=l$ 的方案数。 $n, g, l \leq 10^8$，$q \leq 10^5$。 *** [评测链接](https://www.luogu.com.cn/record/32311378) 等价于每次求 $1\sim n'$，$\gcd=1, \textrm{lcm}=\frac lg$ 的方案数。 我们把 $\textrm{lcm}$ 的质因子选出来，状压即可。 如何强制一个必选？FWT。 # [P5405 [CTS2019]氪金手游](https://www.luogu.com.cn/problem/P5405) 有 $n$ 种卡，每种卡的权值 $W_i$ 有 $p_i$ 的概率取值为 $i$，抽一次卡获得 $i$ 的几率为 $\frac {W_i}{\sum_j W_j}$。 问：经过若干次抽卡并集齐所有卡后，第一次抽卡到每张卡的时间 $T_i$ 满足给定的树形关系的概率。树形关系指的是将其变为无向边后成为一棵树。 $n \leq 1000$。 *** [评测链接](https://www.luogu.com.cn/record/38472051) 考虑当这棵树是外向树时如何求解。 对于一个点 $u$，他要比它子树的其他所有点都要早取到。我们知道这个概率是 $\frac {W_u}{\sum_{v\in subtree_u} W_v}$。 那么我们设 $f_{u, i}$ 表示 $u$ 号点的子树的 $W$ 的和为 $i$ 时，$u$ 子树内全部满足的概率。 当其不是外向树时，我们可以考虑容斥。 假设我们强制某些不满足，那么它们的边反向。其他的边无视。 那反向了还有可能不是外向树啊？ 我们此时发现，实际上只用容斥那些反向边就好了。也就是说我们可以把一个子集拿来容斥，得到的是这个子集的交。