WF 2014 Baggage 设 $(BA)$ 表示 $BABA\cdots BA$，$(AB)$ 表示 $AAA\cdots ABBB\cdots B$。 首先爆搜一下 $n=3,4,5,6,7$，可以发现最短的构造长度为 $n$，同时从 $\_\_(BA)$ 变成了 $(AB)\_\_$。 考虑 $n\geq 8$ 的情况。我们可以做如下操作： $$ \begin{matrix} \_\_BABA(BA)BABA\\ ABBABA(BA)B\_\_A\\ ABBA\_\_(BA)BBAA \end{matrix} $$ 中间那个 $\_\_(BA)$ 可以直接递归处理，处理完后再做如下操作： $$ \begin{matrix} ABBA(AB)\_\_BBAA\\ A\_\_A(AB)BBBBAA\\ AAAA(AB)BBBB\_\_ \end{matrix} $$ 这样子整个序列就变成了 $(AB)$，长度为 $n$。可以证明这是最短的。 Maze Reduction 这种题看着就是要对每个点求一个哈希值，所以关键在于如何设计哈希函数。 设 $h_{i,j,k}$ 表示从 $j$ 的第 $k$ 扇门进去走 $i$ 步的哈希值。假设从 $j$ 的第 $k$ 扇门走进去是 $v$，那么可以从 $j$ 开始绕着 $v$ 走一圈，把所有的 $h_{i-1,v,x}$ 哈希起来表示 $h_{i,j,k}$。特别的，当 $i=0$ 时可以用 $j$ 的度数表示。 然后对每个房间 $i$ 求 $h_{n,i,j}$ 的最小表示，即可当做其哈希值。因为数据范围很小所以可以暴力求，时间复杂度 $\mathcal{O}(n^4)$。 Metal Processing Plant 不妨设 $D(A) \leq D(B)$。 从小到大枚举 $D(A)$，双指针从大到小枚举 $D(B)$，那么只需要考虑如何判断是否合法。 因为每个点要么在 $A$ 中要么 $B$ 中，因此考虑 2-SAT。对于边权在 $(D(A), D(B)]$ 中的边，其两端点需要满足不同时在 $A$ 中；对于边权 $>D(B)$ 的边，其两端点需要满足不同时在一个集合中。 使用压位 Kosaraju 算法找出强连通分量判断即可，时间复杂度 $\mathcal{O}(\frac{n^4}{\omega})$。 Pachinko 设 $f_{i, j}$ 为能够到达 $(i, j)$ 的概率，可以列出一个 $n\times m$ 元方程组。然而直接解时空都无法承受。 不妨把所有格子按照从上到下、从左往右的顺序编号，这样子矩阵是一个长度为 $m$ 的带状矩阵。 因从我们只需要对每行保存 $2m$ 个值，消元时也只需要往下消 $m$ 行再回代就可以了。 Sensor Network 直接随机贪心求最大团是可以过的。具体就是用 bitset 维护已经加入的点，然后随机一个加点排列，能加就加即可。 正解是枚举两个点 $A,B$，则其它点必定在分别以 $A,B$ 为圆心、半径为 $D$ 的两个圆的交内，我们要求最大团。转化成补图的最大独立集，可以发现补图中所有边的端点都在 $AB$ 的两侧，因此补图为二分图，从而很好求最大独立集。 Surveillance 把所有区间按左端点排序，则选了每个区间后下一个必选的区间可以直接双指针预处理出来。 然后预处理倍增数组，枚举起点，然后直接倍增跳一圈即可。 WF 2015 Evolution in Parallel 设 $A\subseteq B$ 表示 $A$ 是 $B$ 的子序列。 首先至少要有 $s_i\subseteq U$，判掉后 $U$ 就没用了。 考虑一条链上的串长度显然是不降的，于是我们把所有串按长度从小到大排序后依次加入，并维护两条链。我们称一个串 $S$ 能接在一条链的末端当且仅当链尾串 $T$ 满足 $T\subseteq S$。 如果当前串不能接在任意一条链的末端，则无解； 如果当前串只能接在一条链的末端，就接上去； 如果当前串可以接在两条链的末端，发现不好处理。我们再维护一条待选链，那么 如果当前串可以接在待选链末端，那么就接上去； 否则一定是这个串和待选链分别接在两条链的末端，随便选择一种接法即可。 这样子总共只需要询问 $\mathcal{O}(n)$ 次 $A\subseteq B$ 是否成立，复杂度 $\mathcal{O}(n^2)$。 Qanat 可以证明，竖井一定会垂直往上运，底部一定会走左右两个竖井中近的那个往上运。 考虑确定最右边的竖井的位置，这样子加上最右边竖井右边部分的代价后即可转化为一个子问题，而这个子问题对应的三角形与原三角形是相似的，所以我们可以只求出原三角形中放 $n-1$ 个竖井的代价，乘上比例系数的平方就可以还原回去。 设最右边竖井到母井的距离为 $L$，我们要计算右边一个 L 状物的代价，即一个 U 状物的代价减去最右边竖井的代价。设 U 状物总长为 $a$，其代价为 $\frac{a^2}{4}$。设原三角形中放 $i$ 个竖井的代价为 $C_i$，于是有 $$ C_n=C_{n-1}\left(1-\frac{L}{w}\right)^2+\frac{\left(h+L+(1-\frac{L}{w})h\right)^2}{4}-\frac{\left[\left(1-\frac{L}{w}\right)h\right]^2}{2} $$ 大力化简得到 $$ C_n=\frac{1-\frac{h^2}{w^2}-\frac{2h}{w}+\frac{4C_{n-1}}{w^2}}{4}L^2+\left(h-\frac{2C_{n-1}}{w}\right)L+\left(C_{n-1}+\frac{h^2}{2}\right) $$ 是二次函数的形式，令 $L=-\frac{2a}{b}$ 即可求出最值。最后再倒推一遍把每条线段放到相似的三角形里去即可。 Weather Report 显然就是要我们求 $4^n$ 个串的 Huffman 编码，直接求复杂度是 $\mathcal{O}(n4^n)$ 的，无法承受。 但是注意到不同的概率只有 ${n+3\choose 3}$ 种，于是我们可以把概率相同的放在一起，每次批量合并即可。 Tile Cutting 设长、宽分别为 $w,h$，长、宽上切点到一个端点的长度为 $a,b$，则面积为 $wh-a(h-b)-b(w-a)$。 令 $c=w-a,d=h-b$，则面积为 $(a+c)(b+d)-ad-bc=ab+cd$。 设面积为 $x$ 的方案数的 OGF 为 $F$，约数个数的 OGF 为 $G$，那么有 $F=G^2$。 线性筛 $d$，NTT 后预处理 ST 表回答询问即可。 WF 2016 Balanced Diet 设 $s=\sum a_i$。当 $s|n$ 时，只有一种取值，否则有两种取值。 如果一个长度为 $s$ 的前缀合法，那么只需要不断重复它就可以构造出无穷长的合法序列，因此我们只需要判断能否到 $s$ 即可。 先只考虑下界限制，也就是要有 $c_i>nf_i-1$，即 $n<\lceil\frac{c_i+1}{f_i}\rceil$。也就是说，对于每个 $i$，我们都需要把它在这个时间之前加上 $1$。我们把这个时间叫做截止时间。 于是可以贪心，每次找一个截止时间最小的出来加 $1$ 即可。可以证明这样并不会超过上界限制。 Branch Assignment 先跑两遍最短路求出 $dis(i,b+1)$ 和 $dis(b+1,i)$。 设 $w_i=dis(i,b+1)+dis(b+1,i)$，可以求出一个集合的权值为 $W(S)=(|S|-1)\sum_{i\in S} w_i$。为了方便我们将 $|S|-1$ 看成 $|S|$，最后再减去 $\sum w_i$ 即可。 将 $w_{1..b}$ 从小到大排序，那么放在一个集合内的一定是连续的一段，从而可以考虑 DP。 设 $dp_{i,j}$ 表示前 $j$ 个数分成了 $i$ 段的最小权值和，转移为 $$ dp_{i,j}=\min_{0\leq k\leq j}\{dp_{i-1,k}+(j-k)(s_j-s_k)\} $$ 这里的 $s$ 是 $w$ 的前缀和。 可以发现这个 DP 对于两维都具有决策单调性。具体的，设 $p_{i,j}$ 表示 $dp_{i,j}$ 是从哪个 $k$ 转移而来的，那么有 $p_{i-1,j}\leq p_{i,j}\leq p_{i,j+1}$。我们从小到大枚举 $i$、从大到小枚举 $j$，在 $[p_{i-1,j},p_{i,j+1}]$ 内枚举转移点，即可做到 $\mathcal{O}(n^2)$。 Clock Breaking 如果一个灯管一直都是 X 或者一直都是 .，那它就有可能恒亮或恒灭。 枚举起始时间，那么如果一个不可能恒亮或恒灭的灯管没有正常发光，那么这个起始时间就不合法。 如果对于某个起始时间，某个灯管都正常发光，那它就有可能是正常工作的。 如果一个灯管的可能性超过 $2$ 种，那么就输出 ?，否则输出对应的东西即可。 Longest Rivers 不妨先考虑只有一个询问 $u$ 时怎么做。显然 $u$ 到根应该都划给 $u$，设这一段长度为 $L$，那么我们希望 $>L$ 的河流数量尽量少。 这个可以直接在树上贪心。如果子树中有一个 $>L$ 的，那么就接它，否则接一个最短的。 后面那一部分和 $L$ 是没有关系的，所以我们考虑让每个节点都接上儿子中最短的，得到一组方案。设 $d_u$ 为这组方案中 $u$ 往下延伸的长度，则有 $$ d_u=\min\left\{d_v\right\}+w_{fa_u,u} $$ 如果只统计 $d_u>L$ 的 $u$ 的数量，显然是会算多的。规定一个节点算了后它的祖先就都不能算了，这样子相当于满足了“如果自述中有一个 $>L$ 的就接它”，算出来的就是对的了。 进一步，如果我们把所有 $d_u\leq L$ 的节点删掉，答案就是叶节点个数 $+1$。 现在已经很好扩展到多组询问了。我们把所有叶节点按到根的距离从小到大排序，这样子 $L$ 是不降的，用堆维护所有叶节点即可。 String Theory 首先如果 $\sum a_i$ 是奇数则一定无解。 显然一个 $k$ 阶串左边一定是 $k-1$ 个引号、$k-2$ 个引号、……、$1$ 个引号，右边一定是 $1$ 个引号、$2$ 个引号、……、$k-1$ 个引号。 那么中间还剩下偶数个引号，我们可以直接把它们整成 $1$ 阶串。 于是可以直接枚举答案，然后从左往右、从右往左各扫一遍判断是否满足条件即可。 What Really Happened on Mars? 直接按照题意模拟即可，主要的问题在 Step 2，也就是如何算当前优先级。 这个东西实际上和最长路很类似，可以直接跑一遍 SPFA 求出。 WF 2017 Airport Construction 显然答案所在直线一定经过多边形的两个顶点。于是可以枚举这两个顶点，然后算长度。 算长度的话，先把所有被直线切开的边拿出来按照交点位置排序，然后扫一遍把所有合法段求个 $\max$ 即可。 Get a Clue! 可以直接爆搜，但是有更加高妙的做法。 我们先预处理出每种手牌集合是否可能是每个玩家持有的手牌。这个可以简单地通过输入数据判断。 注意到每种集合对每个人是独立的，因此可以直接做子集卷积，求出每种集合是否有可能是玩家的手牌。注意到后面我们只需要算缺三张牌的集合，只有三个人的集合两两无交时它们的并才可能恰好缺三张牌，因此可以直接做集合并卷积。 然后对所有可能缺三张牌的集合，判断它缺的三张牌是否每种类型都有一张，如果是说明这三张牌有可能是答案。 最后对每种类型扫一遍，如果答案唯一直接输出，否则输出 ?。 Money for Nothing 可以发现我们要求的就是 $$ \max_{d_i<e_j}\left\{(e_j-d_i)(q_j-p_i)\right\} $$ 可以猜测它有决策单调性，但是我们来尝试证一下。我们把所有东西按时间排好序，设 $i<j\leq k<l$，则应有 $$ (e_k-d_i)(q_k-p_i)+(e_l-d_j)(q_l-p_j)\geq(e_l-d_i)(q_l-p_i)+(e_k-d_j)(q_k-p_j) $$ 大力拆开化简得到 $$ d_iq_k+e_kp_i+d_jq_l+e_lp_j\leq d_iq_l+e_lp_i+d_jq_k+e_kp_j $$ 然而这个东西并不恒成立…… 从头再分析一下。如果 $d_i<d_j,p_i<p_j$，那么我们一定不会买 $j$ 的零件。同理，如果 $e_i<e_j,q_i<q_j$，则我们一定不会卖零件给 $i$。我们可以直接把这些不满足条件的去掉。 那么现在有 $p_i>p_j,q_i>q_j$，根据排序不等式有 $$ \begin{cases} d_iq_k+d_jq_l\leq d_iq_l+d_jq_k\\ e_kp_i+e_lp_j\leq e_lp_i+e_kp_j \end{cases} $$ 这样子上面那个东西就成立了，也就是有决策单调性了，直接分治即可。分治时有一些小细节需要注意。 Replicate Replicate Rfplicbte 注意到每次复制一定会向四周扩展一圈，也就是至多扩展了 $\max\left\{\frac{n}{2},\frac{m}{2}\right\}$ 次。 如果没有发生错误，我们可以直接递推出上一次的状态： $$ b_{i,j}=a_{i-1,j-1}\oplus b_{i,j-1}\oplus b_{i,j-2}\oplus b_{i-1,j}\oplus b_{i-1,j-1}\oplus b_{i-1,j-2}\oplus b_{i-2,j}\oplus b_{i-2,j-1}\oplus b_{i-2,j-2} $$ 问题是有错误。注意到一个错误 $(x,y)$ 会对 $(x+1,y+1),(x+1,y+2)$、$(x+1,y+4),(x+1,y+5)$、……造成影响，那么如果 $b_{i+1,m+1}+b_{i+1,m+2}>0$ 说明第 $i$ 行一定有错误，我们再按列推一遍就可以找到错误位置，然后改掉后再递推就好了。 如果错误数 $\geq 1$ 或者 $n=1$ 或者 $m=1$ 就是答案了。 Tarot Sham Boast 结论：把每个串满足 $2l-i\leq n$（$l$ 是串长，$i$ 是 border 长度）的 border 求出来从大到小排序，字典序小的出现概率大。 官方证明 简化后的感性理解： 长度为 $l$ 的串 $s$ 出现概率为（假设随机串是 $R$） $$ \sum_{S\subseteq\{1,2,\cdots,n-l+1\}}(-1)^{|S|+1}\prod_{i\in S}P(R_{i..i+l-1}=s) $$ 不妨设 $$ F(x)=\sum_{S\subseteq\{1,2,\cdots,n-l+1\},|S|=x}(-1)^{x+1}\prod_{i\in S}P(R_{i..i+l-1}=s) $$ 可以发现 $F(1)$ 恒等于 $3^{-l}$，且 $F(i+1)\ll F(i)$，所以我们可以只比较 $F(2)$ 的值。 假设 $S=\{x,y\}$，那么 $$ F(2)=\begin{cases}-3^{-2l},&i+l-1\leq j\\-3^{-2l+(i+l-j)},&\mathrm{otherwise}\end{cases} $$ 后面那种情况会出现当且仅当 $s$ 有一个长度为 $i+l-j$ 的 border，而且 border 越长贡献越大。又因为前面的系数是 $-1$，所以要按字典序从小到大排序。 需要注意的是 $2l-i>n$ 的 border 是没有贡献的，所以并不能把它们算进去。 Visual Python++ 假设有解，先考虑如何找到这组解。 从左往右扫描线，并用一个 set 维护纵坐标，那么对于一个右上角，拿 set 中纵坐标最大的左下角和它匹配即可。 问题是可能无解，所以上面求出的解不一定是合法的。我们再从左往右扫描线，那么每次加入或删除一个矩形时上下边中间不能有任何其它边界，同样可以用 set 维护。 因为边界重叠也不合法，所以还有许多细节要考虑。 WF 2018 Conquer the World 考虑反着看整个过程，那么相当于每个点有 $y_i$ 只老鼠和 $x_i$ 个洞，所有老鼠都必须进洞。 $u,v$ 匹配的代价是 $dep_u+dep_v-2dep_{\operatorname{LCA}(u,v)}$。因此我们开两个堆维护子树中老鼠和洞的 $dep$，每次把儿子的堆合并，然后取堆顶匹配，再把反悔操作加入堆中即可。 然而这样并不能保证所有老鼠都进洞，所以我们把老鼠的 $dep$ 减去 $+\infty$，最后再把答案加上 $+\infty\times\sum y_i$ 即可。 这样子当匹配的老鼠和洞来自同一棵子树答案可能会不对，但是这样子一定不会是最优解，所以不会有问题。 因为一对匹配的老鼠和洞不会同时反悔，所以只会操作 $X=\sum x_i$ 次，所以时间复杂度 $\mathcal{O}(X\log X)$。可以记一个 pair 表示代价和出现次数从而做到 $\mathcal{O}(n\log n)$。 Gem Island 可以证明，每种最终局面出现的概率是相等的。 于是可以考虑 DP。设 $f_{i,j}$ 表示 $j$ 枚宝石分给 $i$ 个人的方案数，$g_{i,j}$ 表示 $j$ 枚宝石分给 $i$ 个人的所有方案中前 $r$ 多的和。枚举 $k$ 个人，给他们每人一棵宝石，其他人都不再拿宝石，可以得到转移 $$ \begin{aligned} f_{i,j}&=\sum_{k=0}^{\min\left\{i,j\right\}}{i\choose k}f_{k,j-k}\\ g_{i,j}&=\sum_{k=0}^{\min\left\{i,j\right\}}{i\choose k}(g_{k,j-k}+\min\left\{k,r\right\}f_{k,j-k}) \end{aligned} $$ 答案即为 $\frac{g_{n,d}}{f_{n,d}}+r$。 Getting a Jump on Crime 如果我们能够求出从 $u$ 能否到达 $v$，那么就变成一个简单的最短路了，直接 BFS 即可。 考虑这个东西怎么求。设距离为 $d$，高度差为 $h$，根据物理必修一相关知识，可以列出方程 $$ \begin{cases} v_x\!^2+v_y\!^2=v^2\\ d=v_xt\\ v_yt-\frac{1}{2}gt^2=h \end{cases} $$ 化简得到 $$ \frac{1}{4}g^2t^4+(gh-v^2)t^2+h^2+d^2=0 $$ 我们肯定想让 $v_y$ 尽量大（这样就更不容易撞到楼上），所以我们只需要求出 $t$ 的最大值，从而求出 $v_x,v_y$。 然后我们枚举每个边界，如果和路线有交的话就算出跳到这个位置时的高度，然后比较一下即可知道是否会撞上。 Single Cut of Failure 切两条对角线一定能够切断所有电线，所以我们只需要判断答案是否为 $1$ 即可。 把所有端点排序，那么需要判断是否有一个连续的长度为 $n$ 的区间包含恰好 $n$ 条电线，直接开个桶扫一下即可。 由于题目要求，需要把坐标微平移一下。 WF 2019 Beautiful Bridges 容易想到一个 DP，即设 $dp_i$ 表示前 $i$ 个点的最小代价，转移枚举从哪个点修过来。 然而判断转移点是否合法是 $\mathcal{O}(n)$ 的，显然会 T。 考虑对于每个转移点 $j$ 计算不撞上 $j$ 时的半径范围。可以列出式子 $$ r^2\geq (x_j-x_i+r)^2+(y_j-h+r)^2 $$ 于是可以解出合法的 $r$ 的范围。然而有可能一定撞不上 $j$，即 $x_i-x_j\leq 2(y_j-h)$，此时解出来的 $r$ 的范围要特判一下。 对于每个 $j$，只需要看 $x_j$ 是否同时满足 $[j,i]$ 的半径限制即可判断它是否合法。 Directing Rainfall 从上往下扫描线，并维护每个横坐标要有雨最少需要打多少个孔。 那么对于一个雨棚，如果其斜率为正则相当于做一个后缀 $\min$ 再把非左端点加上 $1$，斜率为负则相当于做一个前缀 $\min$ 再把非右端点加上 $1$。 考虑维护其差分数组，并用两个 set 维护差分值为正、为负的位置。前缀 $\min$ 就相当于把正的位置改成 $0$，后缀 $\min$ 就相当于把负的位置改成 $0$，在 set 中找到对应的位置改掉即可。可以发现每次操作会付出 $\mathcal{O}(c)$ 的代价减少差分数组中的 $c$ 个非 $0$ 值，而非 $0$ 值的增加次数是 $\mathcal{O}(n)$ 的，所以这部分复杂度为 $\mathcal{O}(n \log n)$。 我们还需要确定雨棚的加入顺序。我们需要保证一个雨棚加入前其上方所有雨棚都已加入，所以直接按 $y$ 排序是错误的。可以从左往右扫描线来得出雨棚之间的先后关系，然后拓扑排序即可求出一个合法的顺序。 注意到我们不仅需要维护所有整数坐标的答案，还需要维护 $k+0.5$ 这样的坐标的答案，因为有从中间下去更优的情况。 First of Her Name 为了方便，将所有串都反过来，问题变为询问有多少个串以某个串为后缀。 将询问的所有串建 AC 自动机，把名字拿到自动机上匹配并把最终位置 $+1$，在 fail 树上统计子树和即可。 Miniature Golf 显然一个人的分数关于阈值的函数是一个斜率单减的分段函数。 假设我们在求 $x$ 的最好排名。我们枚举一个其它的人 $y$，然后找到它们的交点，则 $x$ 的排名会在交点处改变（$+1$ 或 $-1$）。我们把所有交点拿出来排一遍序，然后扫一遍就可以求出最好排名了。 这个交点比较好求。我们把两个人的所有拐点拿出来归并排序，然后从右往左扫，当 $y$ 的大小关系发生变化时直接算一下即可。 因为题目要求是整数，所以有一些奇奇怪怪的取整的问题。 Traffic Blights 不晓得这东西怎么讲，所以直接蒯 smy 的了 因为 $r_i+g_i\leq 100$，所以经过 $T=\operatorname{lcm}(1,2,\cdots,100)$ 秒红绿灯一定会回到一开始的状态，而 $T|2019!$，所以我们可以看成在 $[0,T)$ 内的随机时刻开始。 考虑求出到达第 $i$ 个红绿灯的概率 $f_i$，这样子差分一下就可以得到答案了。 朴素地想法是列出若干个 $k+x_i\geq r_i\pmod{r_i+g_i}$ 的同余方程，然后求出解集大小，再除掉 $\operatorname{lcm}(r_i+g_i)$。 考虑一些特殊的同余方程组： $\begin{cases}x\in S_1\pmod{p}\\x\in S_2\pmod{q}\end{cases}$，且 $\gcd(p,q)=1$，则解集大小为 $|S_1|\times|S_2|$。 $\begin{cases}x\in S_1\pmod{p}\\x\in S_2\pmod{q}\end{cases}$，且 $p|q$，则可以 $\mathcal{O}(q)$ 求出解集。 如果所有 $p_i$ 都只有一个质因数，那么就可以直接对每个质因数维护一个 $\bmod p^{\lfloor\log_p 100\rfloor}$ 的同余方程，最后合并起来。 我们再设一个 $X$，然后枚举 $a\in[0,X)$，并算所有开始时刻是 $kX+a(k\in N)$ 的贡献。可以发现，$X,a$ 已知时 $kX+a+x_i\geq r_i\pmod{r_i+g_i}$ 可以改写为一个形式为 $k\in S\pmod{\frac{r_i+g_i}{\gcd(r_i+g_i,X)}}$ 的同余方程。 令 $X$ 等于 $\sqrt{100}$ 内所有数的 $\operatorname{lcm}$（即 $2520$），则 $\forall i\in[1,100]$，$\frac{i}{\gcd(i,X)}$ 都只有一个质因数，这样子就可以套用上面的做法了。 NEERC 2017 The Great Wall 把 $b_i,c_i$ 都减去 $a_i$，那么只需要考虑被一个区间覆盖或两个区间覆盖的情况，最后加上 $\sum a_i$ 即可。 考虑二分答案，则我们需要计算 $\leq mid$ 的方案数。 先考虑两个区间无交的情况。设 $b_i$ 的前缀和为 $sb_i$，$c_i$ 的前缀和为 $sc_i$，则和为 $$ sb_{i+r}-sb_i+sb_{j+r}-sb_j $$ 设 $f_i=sb_{i+r}-sb_i$，相当于 $f_i+f_j\leq mid,i+r\leq j$，是一个二维数点问题。 再考虑两个区间有交的情况，和为 $$ sb_j-sb_i+sc_{i+r}-sc_j+sb_{j+r}-sb_{i+r} $$ 设 $g_i=sc_{i+r}-sb_i-sb_{i+r}$，$h_i=sb_i-sc_i+sb_{i+r}$，相当于 $g_i+h_j\leq mid,i+r>j$，同样是一个二维数点问题。 Journey from Petersburg to Moscow 考虑枚举经过第 $k$ 大的边，然后把所有边边权减去这条边的边权后对 $0$ 取 $\max$，那么对应的最短路就是 $dis_n+kw$。 可能没有经过 $k$ 条边，所以还要对原图的最短路取个 $\min$。 通过一些感性理解可以知道这样子包含了所有情况。 Knapsack Cryptosystem 一个做法是直接 meet in the middle，复杂度 $\mathcal{O}(2^{n/2})$，并不能过 $n\leq 64$。 但是题目中还有一个奇妙的性质 $a_i>\sum_{j=1}^{i-1} a_j$，套用得到 $a_1<2^{65-n}$。 发现随着 $n$ 增大 $a_i$ 的取值范围逐渐减小，这启发我们在 $n$ 大时去枚举 $a_1$。 枚举 $a_1$ 后考虑解出 $r^{-1}$，这样子就可以直接求出 $a_{1..n}$，然后倒着贪心一下就可以求出 $s_{1..n}$ 了。 可以列出同余方程 $$ a_1\equiv b_1r^{-1}\pmod{q} $$ 设 $z=v_2(b_1)$，$b'=\frac{b_1}{2^z}$，那么 $$ a_1\equiv2^zb'r^{-1}\pmod{q} $$ 因为 $r$ 是奇数，所以 $v_2(a_1)=z$，设 $a'=\frac{a_1}{2^z}$，那么 $$ a'\equiv b'r^{-1}\pmod{2^{64-z}} $$ 这样子可以解出 $r'=r^{-1}\bmod 2^{64-z}$，$r^{-1}$ 实际取值可能为 $r'+k2^{64-z}(0\leq k<2^z)$。于是我们再枚举 $k$，然后检查得到的 $a_{1..n}$ 是否合法即可。 这样子 $a_1$ 的总枚举量是 $2^{64-n-z}$，$k$ 的总枚举量是 $2^z$，所以总的枚举量是 $2^{64-n}$ 的。 于是我们把两个做法缝合一下，当 $n\leq B$ 时用做法一，否则用做法二，即可做到 $\mathcal{O}(q^{\frac{1}{3}})$。 Laminar Family 考虑把所有路径按照长度从大到小排序，则只有可能是前面的包含后面的。 我们依次加入所有路径，如果当前加入的路径上和两条或者更多条之前的路径有交，那么显然就 GG 了。 我们可以把加入一条路径看成染一种颜色，那么我们只需要支持 链修改颜色； 询问一条链上所有点颜色是否相同。 可以给每种颜色一个编号，然后维护最小值和最大值来解决询问，这样子直接树剖+线段树维护就好了。 NEERC 2016 Binary Code 每个 ? 可以填 $0$ 或 $1$，而且有一些限制，自然想到 2-SAT。然而朴素连边是 $\mathcal{O}(n^2)$ 的，需要优化。 把所有可能的串插入到一棵 Trie 中，那么相当于选出的点互相不能为祖先。 考虑利用 Trie 树优化连边。对于一条 $u\to \neg v$ 的限制，从 $u$ 向对应的节点连边，然后一路往上连到某个节点，再向 $\neg v$ 连边。因为是 2-SAT 所以还有反边，连边方式同理。 但是这并不能处理相同的串。我们想要相同的串只能选一个，朴素连边同样是 $\mathcal{O}(n^2)$ 的，前缀优化连边即可。这样子在 Trie 树上连边时需要拿自己最前面的点去连父节点最后的点。 Cactus Construction 不妨先考虑树的构造。不难得到一种需要 $3$ 种颜色的方案：先把 $u$ 的子树全部建成根是 $1$、其他节点是 $2$，再把 $u$ 改成 $3$，然后把 $u$ 与子节点合并后连 $(1,3)$，再把 $3$ 改成 $1$ 即可。这个构造是递归的。 扩展到仙人掌上时只需要考虑环的处理。我们先把环上的点连出去的子树都接好，然后把环上某个点染成 $4$，然后按照上面的方法连出一条链，最后连 $(1,4)$ 并把 $1$ 改成 $2$、$4$ 改成 $1$ 即可。 操作次数大概是 $4m$，完全能过。 Delight for a Cat 考虑线性规划。设 $x_i$ 为第 $i$ 小时是否吃饭，可以列出线性规划 $$ \begin{matrix} \mathrm{maximize } \sum_{i=1}^n x_i(e_i-s_i)+\sum_{i=1}^n s_i\\ \mathrm{s.t. }\begin{cases}x_1+x_2+\cdots+x_k\geq m_e\\x_1+x_2+\cdots+x_k\leq k-m_s\\\cdots\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n\geq m_e\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n\leq k-m_s\\0\leq x_1,x_2,\cdots,x_n\leq 1\end{cases} \end{matrix} $$ 发现是全幺模矩阵，所以一定有整数解，可以考虑费用流。 按照惯例添加辅助变量 $$ \begin{cases}x_1+x_2+\cdots+x_k-y_1=m_e\\x_1+x_2+\cdots+x_k+z_1=k-m_s\\\cdots\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n-y_{n-k+1}=m_e\\x_{n-k+1}+x_{n-k+2}+\cdots+x_n+z_{n-k+1}=k-m_s\end{cases} $$ 然后差分一下 $$ \begin{cases}x_1+x_2+\cdots+x_k-y_1=m_e\\z_1+y_1=k-m_s-m_e\\\cdots\\z_{n-k+1}+y_{n-k+1}=k-m_s-m_e\\-x_{n-k+1}-x_{n-k+2}-\cdots-x_n-z_{n-k+1}=m_s-k\end{cases} $$ 用 NOI2008 志愿者招募 一题的方法建图求最大费用最大流即可。 Mole Tunnels 可以想到一个费用流做法： 对于每只鼹鼠，从原点向 $p_i$ 连容量为 $1$、费用为 $0$ 的边； 对于相连的两个点，连容量为 $+\infty$、费用为 $1$ 的边； 对于每个点，向汇点连容量为 $c_i$、费用为 $0$ 的边。 注意到树高是 $\log$ 级别的，所以我们可以暴力枚举当前点与流向的点的 LCA。具体的，我们预处理每个点子树中到它费用最小的点，然后每次暴跳祖先找到流向的点，再连上反边并更新即可。 NEERC 2015 Binary vs Decimal 可以发现如果 $x$ 是合法的，那么 $x$ 的后缀也是合法的。 于是可以从 $0$ 和 $1$ 开始 BFS，每次加上 $10^k$ 判断是否合法即可。 注意到 $10^k$ 在二进制下末尾一定有 $k$ 个 $0$，所以我们只需要判断 $x$ 在十进制下的最高位一直到 $k$ 是否都为 $0$ 即可。 实现时只需要记录二进制和十进制最高位即可。 Cactus Jubilee 移动一条边等价于先删掉一条边再加入一条位置不同的边。不妨去掉位置不同的限制，最后将答案减去边数即可。 那么我们相当于要对每个断掉一条边后求出有多少种加边的方案，满足加边后是仙人掌。 分两种情况讨论： 如果断掉的边是桥，那么剩下的两部分之间任意连都可以，方案数为两部分点数之积。 如果断掉的边不是桥，根据 ZJOI2017 仙人掌 的结论，需要保证连边的两点路径上的边全为桥边。因此可以只保留桥边得到一个图，答案为 $\sum {sz_i-1\choose 2}$。 桥的情况可以一遍 DFS 求出，而非桥的情况似乎不好快速计算。注意到同一个环上的边断掉后保留桥边得到的连通分量相同，因此可以每次对一个环计算。这个环断掉一条边后相当于若干个连通块合并成了一个，只要找到环上的所有点，减去原来的贡献，再加上合并后的贡献即可。 Distance on Triangulation 对于这种图上多次询问最短路的题，显然考虑分治。 我们找到一条边，这样子就可以把图拆分成两部分，按照 ZJOI2016 旅行者 一题的方法更新询问的答案即可。因为边权全为 $1$ 所以只需要 BFS。 考虑复杂度。整个过程相当于在对偶图上做边分治，而三角剖分图的对偶图的最大度数为 $3$，所以每次分治大的一部分至多有 $\frac{2}{3}m$ 条边，因此复杂度是正确的。 Jump 我们只能先想办法问一个 $\frac{n}{2}$ 出来。先假设已经问出来了，稍后再来考虑怎么问。 规定一个串对应的集合就是它所有 $1$ 的下标集合，下面不再区分串和集合。 假设问出来的串是 $I$，考虑求出 $A=S\oplus I$。 考虑 $|A\oplus\{u,v\}|=|A|+|\{u,v\}|-2|A\cap\{u,v\}|$，即 $|A\oplus\{u,v\}|=\frac{n}{2}+2(1-|A\cap\{u,v\}|)$。那么每次可以确定一个二元组与 $A$ 的交是否 $=1$。 不妨令 $u=1$，那么可以得到其它的数是否可以同时和 $1$ 在 $A$ 内，这样子有两种可能的情况，都问一遍即可。 这里最坏会询问 $n+1$ 次，于是我们需要思考如何在 $499$ 次内找到一个 $I$。 考虑随机，那么一次问到一个 $\frac{n}{2}$ 的概率是 $\frac{{n\choose n/2}}{2^n}$，在 $n=1000$ 时约等于 $2.52\%$。于是随机 $499$ 次有很大的概率出解。 King’s Inspection 注意到出度为 $1$ 的点接下来该往哪走是确定的，我们只需要爆搜出度不为 $1$ 的点往哪走即可。 注意不要漏判无解的情况。 Landscape Improved 我们钦定一个横坐标最后是最高的，然后二分它的高度。 check 时只需要找出左右第一个不需要补的位置，然后算出区间内要填的数量，判断它是否 $\leq n$ 就好了。 然而直接暴力找显然不太行。考虑二分，把式子写出来移项后发现要求 $h_i-i$ 和 $h_i+i$ 的 $\max$，ST 表即可。 NEERC 2014 Epic Win! 如果初始状态确定，那么很容易造出一个 $n$ 个点、每个点只有一个转移的自动机来 $100\%$ 打败对手：每个节点的输出正好能战胜对方这个节点的输出，然后根据对方这个节点的输出转移到对应的节点即可。 如果直接拿这个自动机去打，那么可能某时刻没有转移边，这说明我们没有赢。于是我们只要根据对手的输出，转移到对手的节点对应的自己的节点去即可。 这样子会有一些问题，原因在于我们新加的转移边是会成环的，导致会重复到达某个没赢的状态。所以我们每次没赢时新复制一个自动机，然后转移到新自动机去即可。这样子新加的转移是一个外向树的结构，就不会有问题。 根据上面的分析可以知道，这样子至少可以赢 $10^9-n$ 次，可以通过本题。 Gomoku 人类智慧题。 simulator Hidden Maze 从小到大枚举所有边，将已经枚举到的（包括当前的）边的边权设为 $1$、仍未枚举到的边的边权设为 $-1$，则此时所有经过这条边的边权和为 $1$ 的路径的中位数就是这条边。 设 $s_{i, j}$ 表示以 $i$ 为根的子树中有多少个点到 $i$ 的边权和为 $j$。于是统计时只需要枚举 $u$ 的祖先作为路径两个端点的 LCA，然后很容易算出方案数（注意路径的两个端点不能在同一棵子树中，需要类似点分治的减掉），修改时直接暴力修改祖先即可。 因为树随机生成，所以期望树高是 $\mathcal{O}(\sqrt{n})$ 级别的，因此时间复杂度为期望 $\mathcal{O}(n \sqrt{n})$。 Improvements 经过一些手玩或者打表可以发现，合法当且仅当 $\forall i\in[1,n]$，$p_i$ 是一个后缀最小值或者后缀最大值。 必要性证明可以考虑找到 $p_i=n$ 的位置，则前面必然是 $p_1=1,p_2=2,\cdots,p_{i-1}=i-1,p_i=n$，后面是一个子问题，可以递归证明；充分性证明略。 这个结论等价于 $p^{-1}$ 是一个单峰的排列，因为 $p_n$ 前面比它小的数单增、比它大的数单减。 修改一个数和直接删掉没有区别。于是只要正反求两遍 LIS，然后枚举最高点即可。 NEERC 2013 Hack Protection 枚举右端点，那么往左的过程中 and 和只会变化 $\log$ 次。 求出前缀异或和，那么我们只需要对 $\log$ 个区间统计其中某个值的出现次数，可持久化 01 Trie 即可（好像可以直接二分）。 这 $\log$ 个区间可以记一下上一个某一位是 $0$ 的数来找出。 Interactive Interception 设速度为 $k$、起始点为 $b$，那么 $t$ 时刻的坐标 $f(t)=kt+b$。 考虑二分，把 $(k,b)$ 看成一组值，每次尽量划分出一半的值出来。 然而 $(k,b)$ 多达 $10^{10}$ 组，直接存下是不可能的。但是注意到任意时刻对于某个 $k$，可能的 $b$ 都是一个区间，因此我们可以对每个 $k$ 记下这个区间。 现在考虑如何划分。我们把所有可能的 $(k,b)$ 都拿出来并计算它们在 $t$ 处的取值，那么我们只需要询问 $[0,M]$（$M$ 是这些取值的中位数）就可以尽量划分成一半了。求中位数可以二分实现。 Kabaleo Lite 假设自己已经操作完了，考虑能否必胜。 这样考虑：其他人为了阻止自己胜利，一定会尽量把 $h$ 变成别的，并尽量多地造另一种。于是我们考虑求出最少会剩下多少个 $h$（记做 $A$），以及不是 $h$ 的出现次数最多的数出现多少次（记做 $B$）。 那么如果 $A>B$ 的话，则必胜。 先考虑如何求 $A$。设 $x$ 为 $b_{1..n}$ 中 $h$ 的数量，$y$ 为 $l_{2..p}$ 中不为 $h$ 的数量，那么有 $A=\max\{x-y,[l_p=h]\}$。 再考虑如何求 $B$。设 $x_i$ 为 $i$ 在 $b_{1..n}$ 中的出现次数，$y_i$ 为 $i$ 在 $l_{2..n}$ 中的出现次数，那么有 $B=\max_{i\neq h}\{x_i+y_i\}$。 直接做的话是 $\mathcal{O}(n^2)$ 的，考虑优化修改后算 $A,B$ 的过程。一次修改相当于把 $b_i$ 的出现次数减 $1$、$l_1$ 的出现次数加 $1$。 首先 $A$ 是很好维护的，可以发现只有可能 $x$ 变化，只要维护 $b_{1..n}$ 中 $h$ 的数量即可。 $B$ 就有些复杂。可以发现，修改后的最大值只有可能是原来的最大值、次大值和 $l_1$ 中的一个，三个取个 $\max$ 即可。注意不能和 $=h$ 的取 $\max$。 这样子就做完了。注意要特判 $n=1,l_p=h$ 的情况。 CERC 2017 Buffalo Barricades 我们首先求出每个栅栏实际包含的牛的数量（也就是不算被后面的栅栏包含的）。 从上往下扫描线，并用 set 维护所有往下的栅栏的横坐标。 如果当前点是牛，我们找到一个最小的 $x\geq$ 它的横坐标的栅栏，则最终这个栅栏包含这头牛； 如果当前点是栅栏，我们把它加入 set 中，然后模拟一遍往左延伸的过程，把编号比它大的连续的一段删掉。 接着求出每个栅栏加入时包含的牛的数量。可以发现，如果 A 包含 B，且 A 加入时间比 B 早，那么 B 的答案要加到 A 中去。可以发现这个东西实际构成一个树形关系，我们只需要从前往后扫，然后把父边断掉，这样子扫到每个点时它的 $size$ 就是答案了。可以直接 LCT 维护。 当然也可以不 LCT，直接倒过来变成加边，就很好用并查集维护了。 Cumulative Code 不妨先写出 $k=5$ 时的 Prufer 序列 $$ p^{(5)}=[8,8,4,9,9,4,2,10,10,5,11,11,5,2,1,{\color{red}{3}},12,12,6,13,13,6,3,{\color{red}{7}},14,14,7,{\color{red}{15}},15] $$ 红色的数与其它数不同——这些位置删除的节点是根。但是这些数只有 $k-2$ 个，我们可以单独考虑。下面我们只考虑黑色数的连续段中的情况。 可以发现这样的连续段等于左子树的后序遍历中每个数除以 $2$。 不妨把每个数写成关于根的父亲编号的一次函数的形式，如当 $k=4$ 时有 $$ p^{(4)}(x)=[8x,8x,4x,8x+1,8x+1,4x,2x,8x+2,8x+2,4x+1,8x+3,8x+3,4x+1,2x,x] $$ 考虑 $p^{(k)}(x)$ 与 $p^{(k-1)}(x)$ 的关系。可以发现，$[x]p^{(k)}(x)$ 等于 $\Big[2[x]p^{(k-1)}(x),2[x]p^{(k-1)}(x),1\Big]$，$[x^0]p^{(k)}(x)$ 等于 $\Big[[x^0]p^{(k)}(x),\frac{1}{2}[x]p^{(k)}(x)+[x^0]p^{(k)}(x),0\Big]$。 这样子我们就可以将求 $p^{(k)}$ 中若干等差数列项的和转为两个求 $p^{(k-1)}$ 中若干等差数列项的和的问题，可以直接递归计算。 然而如果递归到底的话是 $\mathcal{O}(2^k)$ 的。我们只需要在没有元素时及时返回，再加上记忆化即可。为了记忆化我们把询问拆成前缀相减，并记录深度与末项的位置。 这样子时间复杂度变为 $\mathcal{O}(2^{k/2})$。实际上我们只需要对前 $\frac{k}{2}$ 层记忆化即可，不影响复杂度。 Donut Drone 考虑先暴力走到第一列，然后倍增跳 $k/m$ 圈，再暴力走完剩下的。 那么我们要维护 $(i,1)$ 走 $2^km$ 步后会到哪里。考虑用线段树维护，每个区间维护从 $l$ 走到 $r+1$ 的哪一行，这样子根节点就是 $(i,1)$ 走 $2^0m$ 步后到的行，再倍增即可。 修改直接把前一列在线段树上修改一下即可。 复杂度大概是 $\mathcal{O}(Qn\log k)$，似乎挺能过的。 Intrinsic Interval 析合树模板题。 如果两个点在析合树上的 LCA 是析点，那么答案就是这个析点对应的段；否则还要找到两个点所在的两棵子树，LCA 的儿子序列中这两个子树间的子序列才是答案。 Kitchen Knobs 显然每个按钮要么最终位置唯一（因为 $7$ 是奇数），要么最后在哪都可以（这种情况当且仅当 $7$ 个数都相等）。后面那种我们可以直接去掉。 我们把每个按钮需要旋转的次数算出来，然后再差分一下（注意这里是在模 $7$ 意义下），问题变为每次可以给一个数加 $x$ 一个数减 $x$，求把所有数变成 $0$ 的最小次数。 $0$ 我们可以直接不管；对于剩下的数，显然我们会先把 $1,6$、$2,5$、$3,4$ 两两相消，这样子最后会剩下至多 $3$ 种数。 可以发现，如果剩下的 $3$ 种数和为 $7$ 的倍数，那么我们一定可以用数量减 $1$ 次操作把它们都消成 $0$。于是我们预处理所有这 $3$ 种数的和为 $7$ 的倍数的情况，然后直接 DP 即可。 Lunar Landscape 注意到值域很小，又和覆盖有关，所以猜测和差分有关。 A 类正方形很好差分处理；B 类正方形是斜着的，感觉不太好处理。 我们做坐标变换 $\begin{cases}x\leftarrow x+y\\y\leftarrow x-y\end{cases}$，那么 B 类正方形就变成正的了，同样可以差分处理。 算答案时，我们算出每个面积为 $0.25$ 的小三角形是否被覆盖，然后加起来即可。 CERC 2016 Bipartite Blanket 可以发现，左右两边点集的可行性是无关的，于是我们可以先预处理出两边的每个点集是否可能被一组匹配覆盖。 考虑这个东西怎么预处理。设 $f_S$ 表示左边点集 $S$ 能否被一组匹配覆盖。那么根据 Hall 定理，我们需要枚举 $S$ 的每个子集 $T$，然后判断 $|T|\leq |N(T)|$ 是否成立。然而这样显然无法通过。 但是仔细思考一下可以发现，$|T|\leq |S|-1$ 的 $T$ 是否都成立我们已经知道了（根据 $f_{S-\{i\}}$），我们只要判断 $|S|\leq |N(S)|$ 是否成立就好了。这样就可以在 $\mathcal{O}(n2^n)$ 的时间内求出 $f$。同理我们在 $\mathcal{O}(m2^m)$ 的时间内求出 $g$ 表示右边点集 $S$ 能否被一组匹配覆盖。 那么问题变为求有多少个 $(S,T)$ 满足 $f_S=1,g_T=1,s_S+s_T\geq t$，可以用 meet in the middle 的思想，把所有 $g_T=1$ 的 $T$ 按 $s_T$ 排序，然后枚举 $f_S=1$ 二分出满足条件的 $T$ 的个数即可。 Dancing Disks 设 $f_{i,j}$ 表示 $(i,j)$ 最多能让多少个数有序。显然 $(i,j)$ 可以多路归并左上方的所有柱子上的数，那么有 $$ f_{i,j}=\sum_{1\leq x\leq i,1\leq y\leq j,(x,y)\neq (i,j)}f_{x,y} $$ 显然 $f_{1,1}=f_{1,2}=f_{2,1}=1$，于是可以推出 $f_{6,6}=26928$，感觉不太行。 冷静分析一下发现，对于 $(1,2)$ 和 $(2,1)$，我们可以看 $(1,1)$ 最上面两个的大小关系，从而实现 $f_{1,2}=f_{2,1}=2$，这样 $f_{6,6}=42960$，非常好。 于是我们递归做这个过程，每次用堆维护多路归并即可。注意每个柱子实际上是一个栈，所以如果当前柱子需要从小到大排，则前面的柱子需要从大到小排，所以我们还要记一下排序方式。 Easy Equation 考虑一组解 $(x_0,y_0,z_0)$，把 $x$ 看成主元，有 $$ x^2-k(y_0+z_0)x+(y_0\!^2+z_0\!^2-ky_0z_0-1)=0 $$ 由韦达定理可知，$x$ 的另外一根为 $k(y_0+z_0)-x_0$。 显然原方程有一组解 $(0,0,1)$，我们只要从这个解出发，按照上面的方法扩展出两个更大的解，直到找到 $n$ 个解即可。 Jazz Journey 显然我们可以对所有 $u\to v$ 和 $v\to u$ 的路线单独拿出来算。 首先我们算出 $u\to v$ 的最小花费、$v\to u$ 的最小花费、$u\to v\to u$ 的最小花费、$v\to u\to v$ 的最小花费。需要注意的是前两种可以买双程票，后两种可以买两张单程票。 那么现在一定在不浪费的前提下尽量多买双程票更优，于是我们先做两遍类似括号匹配的过程，先尽量多买更便宜的那种双程票，再尽量多买另一种，剩下的就买单程票即可。 Lost Logic 如果一个变量取值全为 $0$，我们加一个 $x\to \neg x$，限制它只能为 $0$；同理，如果一个变量取值全为 $1$，我们加一个 $\neg x\to x$，限制它只能为 $1$。 然后一个自然的想法是枚举 $i,j$，如果 $i$ 为 $x$ 的时候 $j$ 全为 $y$，就加一个 $ix\to jy$。但是这个约束数是 $\mathcal{O}(n^2)$ 的，并不太行。 那么可以先把那些相同的或者互补的缩起来。具体的，如果 $i,j$ 相同就加 $i\to j$ 和 $\neg i\to \neg j$，如果 $i,j$ 互补就加 $i\to \neg j$ 和 $\neg i\to j$。 这样子只会剩下至多 $3$ 种（$0,0,1$、$0,1,0$ 和 $1,0,0$）。冷静分析一下发现：如果 $3$ 种都有，则不能构造出合法方案；如果只有 $1$ 种，则我们不需要再连边；如果只有 $2$ 种，我们直接枚举两种的取值（共 $4$ 种情况），然后判断是否需要连边即可。 CERC 2015 Export Estimate 考虑按边权从大到小加边。 先考虑算点数。观察一下这个过程，似乎所有度数是 $0$ 或 $2$ 的点都会被删掉？其实并不是，因为一个度数全是 $2$ 的点构成的环最后会留下一个点。所以点数实际上是 $n-cnt_0-cnt_2+cnt_{loop}$。 边数同理，所有度数为 $2$ 的点都会删去两条边再加上一条边，但一个度数全是 $2$ 的环最后会留下 $2$ 条边。所以边数是 $e-cnt_2+cnt_{loop}$，这里的 $e$ 是已经加入的边数。 那么唯一的问题就是如何维护 $cnt_{loop}$ 了。因为只有加边，所以可以用并查集很方便的维护（只需要维护每个连通块是否是度数全为 $2$ 的环即可）。 Frightful Formula 先考虑 $c=0$ 的情况。我们计算每个 $l_i$ 和 $t_i$ 对 $(n,n)$ 的贡献。 只考虑 $l_i$，那么相当于从 $(i,1)$ 走到 $(n,n)$，第一步必须往右，往右走一步乘 $a$，往下走一步乘 $b$，求所有路径的权值和。这个东西显然等于 $$ {2n-i-2\choose n-2}a^{n-1}b^{n-i} $$ 再考虑 $c$ 的贡献。同理可以知道，$(x,y)$ 对 $(n,n)$ 的贡献是 $$ c{2n-x-y\choose n-x}a^{n-y}b^{n-x} $$ 那么总贡献是 $$ \begin{aligned} &c\sum_{i=2}^n\sum_{j=2}^n{2n-i-j\choose n-i}a^{n-j}b^{n-i}\\ =&c\sum_{i=2}^n\sum_{j=2}^n(2n-i-j)!\frac{a^{n-j}}{(n-j)!}\frac{b^{n-i}}{(n-i)!}\\ =&c\sum_{d=4}^{2n}(2n-d)!\sum_{i+j=d}\frac{a^{n-j}}{(n-j)!}\frac{b^{n-i}}{(n-i)!} \end{aligned} $$ 后面是卷积的形式，于是直接 MTT 即可。 有的小青年就发问了，我不喜欢卷积，我不喜欢 MTT，我永远只爱组合意义，你这种推式子，我很不满意！ 很好！很有精神！那我们就来分析一下。 我们打个表看一下每一项对 $(n,n)$ 的贡献 $$ \begin{matrix} ca^0b^0{0+0\choose 0} & ca^1b^0{1+0\choose 1} & ca^2b^0{2+0\choose 2} & \cdots \\ ca^0b^1{0+1\choose 0} & ca^1b^1{1+1\choose 1} & ca^2b^1{2+1\choose 2} & \cdots \\ ca^0b^2{0+2\choose 0} & ca^1b^2{1+2\choose 1} & ca^2b^2{2+2\choose 2} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{matrix} $$ 可以发现，当 $i+j\leq n-2$ 时，贡献就是 $c(a+b)^{i+j}$；当 $i+j>n-2$ 时，可以把上一 / 的贡献乘上 $a+b$，然后再减去边上两项，就可以得到贡献了。 Greenhouse Growth 如果一段向日葵高度相同，那么它们在之后任意时刻高度都相同，因此可以缩成一段。 用链表维护这些连续段，每段维护如下信息： $l,r$：左右端点； $t,h$：在第 $t$ 天时高度为 $h$； $fl,fr$：光在左边 / 右边时是否会长高。 第 $i$ 天时的高度可以通过前 $i$ 天光在左边和右边的天数来求出。 我们逐天处理，每天把能合并的合并即可。对于两个相邻的连续段，我们可以根据它们的高度差求出它们会在什么时间合并。于是只要当发生改变时重新计算一下合并时间即可。 具体实现细节比较多，要注意各种奇奇怪怪的情况（比如之前要合并的现在不要合并了）。 Ice Igloos 注意到值域和 $r$ 都很小，所以我们可以只枚举那些圆心到直线距离 $<1$ 的圆。 具体地，我们需要找到所有满足 $$ \frac{\lvert Ax+By+C\rvert}{\sqrt{A^2+B^2}}<1 $$ 的圆。 因为值域很小，所以可以直接枚举 $x$，然后把 $y$ 的范围算出来就好了。注意端点需要特判。 Juice Junctions 看到这题的第一反应就是最小割树，然而这个 $n\leq 3000$ 的数据范围一看就很不能过。 注意到题目中有一个奇妙的度数 $\leq 3$ 的限制，这说明最大流 $\leq 3$，我们可以讨论一下： 如果两点不连通，最大流为 $0$； 如果两点不在同一个边双中，最大流为 $1$； 如果两点在同一个边三连通分量中，最大流为 $3$； 否则最大流为 $2$。 问题是这个“边三连通分量”怎么求。思考一下发现，如果断掉任意一条边后两点都在一个边双中，则它们在同一个边三中。我们可以枚举断掉的边，然后相当于判断两点所在边双是否一一相等，可以直接哈希判断。 实际上有线性求边三连通分量的算法，但是这题 $\mathcal{O}(m^2)$ 可以过所以就懒得去看了。 CERC 2014 Can't stop playing 可以发现游戏中的序列一定是一个 ^ 的形状。 对于一个单增或单减的只由 $2^k$ 构成的序列，我们只要知道它们的和即可还原出整个序列。 设 $f_{i,j}$ 表示前 $i$ 个数、最高点右边的和为 $j$ 是否可行。因为前 $i$ 个数的和已知所以可以求出左边的和。 转移时只需要看一下当前数是不是小于等于最左边 / 最右边的数即可。注意放在右边时可能会产生新的最大值使得右边的和变成 $0$。 在转移过程中记录一下转移点，倒推即可求出方案。 Pork barrel 把所有边从大到小排序，然后依次加入，并维护 MST。假设询问 $[l,r]$，则加入了所有 $\geq l$ 的边后 MST 上 $\leq r$ 的边权之和即为答案。 LCT 维护生成树、主席树维护每种边权的出现次数即可。 The Imp 实际上双方都知道对方的最优策略。 那么对于我方的某个策略 $(s_1,s_2,\cdots)$，显然有 $v_{s_i}<v_{s_{i+1}}$，否则一定更劣。 于是我们先把所有物品按 $v$ 从大到小排序，然后考虑 DP。设 $dp_{i,j}$ 表示前 $i$ 个物品，对方去掉了 $j$ 个的最大收益，转移为 $$ dp_{i,j}=\max\left\{dp_{i-1,j},\min\left\{w_i-v_i,dp_{i-1,j-1}-v_i\right\}\right\} $$ 答案即为 $dp_{n,k}$。 Outer space invaders 考虑 $d$ 最大的那个外星人，我们选一个时刻把它打了，那么剩下左右两端只剩下了被完全包含的外星人。 于是可以区间 DP。设 $dp_{i,j}$ 表示 $[i,j]$ 完全包含的外星人被打掉的最小代价，转移是 $$ dp_{i,j}=\max_{k=i}^j\left\{dp_{i,k-1}+x+dp_{k+1,j}\right\} $$ 这里的 $x$ 时被 $[i,j]$ 完全包含的外星人中最大的 $d$。 CERC 2013 Subway 似乎是 JSOI2015 地铁线路 的原题。当然那题把输入改简单了。 第一问考虑最短路。对于每条线路建一个点，线路上的站向线路连边权为 $1$ 的边，线路向线路上的站连边权为 $0$ 的边。因为边权只有 $0$ 和 $1$ 所以可以 BFS。 第二问考虑一个 DP。设 $dp_i$ 表示到达 $i$ 时最多乘坐多少分钟的地铁。 假设一条线路的 $dis$ 为 $d$，则我们可能在 $dis$ 为 $d-1$ 的站上车，在 $dis$ 为 $d$ 的站下车，所以我们要用 $dis$ 为 $d-1$ 的站更新 $dis$ 为 $d$ 的站。 把所有线路按 $dis$ 从小到大排序，然后对于每条线路转移：$dp_j\leftarrow dp_i+dis(i,j)\;(dis_i=d-1,dis_j=d)$。记一下前后缀最大值即可 $\mathcal{O}(L)$ 转移。 Chain & Co. 考虑按照平行的平面分成三类，那么每一类内部肯定只能在一个集合内。 于是我们枚举哪一类是单独的，然后暴力 check 一下就好了。 Captain Obvious and the Rabbit-Man 可以发现 $p_i$ 是 $k$ 阶常系数齐次线性递推数列，其特征多项式为 $p=(X-1)(X-2)\cdots (X-F_k)$。 设 $p=X^k+a_{k-1}X^{k-1}+\cdots+a_0$，则有 $$ p_{k+1}+a_{k-1}p_k+\cdots+a_0p_1=0 $$ 只需要 $\mathcal{O}(k^2)$ 求出 $p$ 的系数即可。 NEERC NSub 2017 Consonant Fencity 暴力是枚举每种字符是大写还是小写，然后扫一遍算答案，复杂度 $\mathcal{O}(2^{|\Sigma|}n)$。 实际上我们只需要知道每个字符对的出现次数，预处理后即可做到 $\mathcal{O}(2^{|\Sigma|}|\Sigma|^2)$。 然而 $|\Sigma|=26$。但是实际上元音字母的大小写是无关紧要的，我们只需要知道辅音字母的大小写即可。这样子就有 $|\Sigma|=19$，可以通过此题。 Equal Numbers 显然只有两种情况：要么是一个数全部变成了它的某个倍数，要么是一些数变成了它们的 LCM。 两种情况肯定都是先选个数少的，排序后扫一遍即可。 Fygon 2.0 对于一个 for i in range(a, b):，可以看成 $i$ 在 $[1,n]$ 内循环，但是只有 $a\leq i\leq b$ 时才算贡献。 我们从 $a$ 向 $i$、$i$ 向 $b$ 连边，则一个强连通分量内的变量取值必须相同，即 $k$ 即为强连通分量数。 然后 $C$ 感性理解一下就是缩点后的大小关系数除以点数的阶乘，而前面那个东西就等于 DAG 的拓扑序数，状压 DP 即可。具体证明可以看这里。 Grand Test 似乎和 CF521E Cycling City 一模一样。 首先 DFS 一遍求出一棵生成树，那么只会有一些返祖边。答案存在当且仅当有一条树边被至少两条非树边覆盖。 假设这两条非树边是 $(a,b)$ 和 $(c,d)$，$t$ 是 $a,c$ 的 LCA，如下图 那么 $3$ 条路径即为 $t\to b$、$t\to a\to b$、$t\to c\to d\to b$。 实现时可以直接暴力覆盖、暴力求 LCA，时间复杂度 $\mathcal{O}(n)$。 Hidden Supervisors 可以证明，包含根的最大匹配只会比不包含根的最大匹配大 $0$ 或 $1$。 于是我们对每棵树都求一个最大匹配（可以直接 DFS 求出），然后分成两类：根在匹配中的和根不在匹配中的。特别的，$1$ 并不能连父边，所以要强制看成第一类。 那么我们相当于要把第二类的根拿去匹配前面某个未匹配的点。第一类树中的未匹配点是可以匹配的，而第二类按照未匹配点的数量从大到小排序后加入一定是最优的。如果前面没有未匹配的点，那么可以连到 $1$ 上保证形成一棵树。 NEERC NSub 2016 Digital Addition 每一位的状态只有 $200$ 种，可以直接预处理出来。 考虑数位 DP。设 $f_{i,S,0/1}$ 表示 $[i,w]$ 位、第 $i$ 位左边黑色部分为 $S$、是否进位是否可行，转移直接枚举下一位的状态即可。 因为要输出方案，所以要记录一下每个状态是从哪里转移过来的。 Easy Reading 首先不是 u,d,l,r 的字符是没用的，可以直接去掉。 两个图案相同至少要黑格子数量相同，于是可以双指针求出所有黑格子数满足条件的区间。 在双指针的过程中可以维护出黑格子，但是我们并不能 $\mathcal{O}(nm)$ 的判断图案是否相同。 考虑哈希。设 $H_{x,y}=A^xB^y\pmod{p}$，那么我们只需要比较两个图案的哈希值即可。注意图像是可以平移的，所以我们还需要求出当前图案的黑格子中最小的 $x$ 和 $y$，然后乘上 $A^{-x}B^{-y}$ 平移到原点比较。 然而卡自然溢出，所以最好在哈希值相同时暴力比较一遍。 Gangsters in Central City 显然至少要断掉的边数就是 $1$ 的有强盗的子树数量，因为我们可以直接断掉与 $1$ 相连的边。 于是我们可以把 $1$ 的每棵子树分开考虑（下面的强盗只指 $1$ 的某棵子树中的）。为了满足第二个条件，断掉的边一定是最深的强盗全在其中的点的父边。这个点实际上就是强盗的 LCA。 可以考虑一个经典套路：对于每个强盗，把它到根的路径加上 $1$，那么这个点就是所有点权最大的点中最深的那个。 这样子就可以直接树剖+线段树维护了。删点后子树中没有强盗了的情况可能需要注意一下。 Integral Polygons 如果总面积不是整数则答案为 $0$，否则只要一侧面积为整数即满足条件。 那么也就是（$\times$ 是叉积） $$ \vec{p_i}\times\vec{p_{i+1}}+\vec{p_{i+1}}\times\vec{p_{i+2}}+\cdots+\vec{p_{j-1}}\times\vec{p_j}+\vec{p_j}\times\vec{p_i}\equiv 0\pmod{2} $$ 设 $$ s_n=\sum_{i=2}^n\vec{p_{i-1}}\times\vec{p_i} $$ 上面的条件即 $$ s_j-s_i+\vec{p_j}\times\vec{p_i}\equiv 0\pmod{2} $$ 把叉积也拆开，变成 $$ s_j-s_i+x_jy_i-y_jx_i\equiv 0\pmod{2} $$ 枚举 $j$，那么 $s_j,x_j,y_j$ 的奇偶性已知，我们只需要知道 $s_i,x_i,y_i$ 的奇偶性即可判断是否合法。这只有 $8$ 种情况，开一个桶记一下即可。 注意去掉 $i=j+1$ 和 $i=1,j=n$ 的情况，因为这样的情况面积一定是整数，所以只需要最后减 $n$ 即可。 Java2016 我们可以先对很多个 ? 取 max 来得到 $255$，然后把两个 $255$ 相除得到 $1$。因为代码长度限制需要套几层宏定义。 然后可以求出 $2,4,8,16,32,64,128$，直接把 $c$ 拆位即可。 $0$ 需要特判（直接把样例蒯下来即可）。 NEERC NSub 2015 Distribution in Metagonia 不是很晓得怎么想出来的，直接给算法了： 首先找到最大的 $2^x|n$； 然后找到最大的 $2^x3^y\leq n$； 把 $2^x3^y$ 作为一个答案，然后递归分解 $n-2^x3^y$。 可以发现 $n-2^x3^y$ 中 $2$ 的次数一定 $>x$（因为 $n$ 除掉 $2^x$ 后是奇数，再减掉奇数后是偶数，也就是 $(n-2^x3^y)/(2^x)$ 是偶数），而 $3$ 的次数一定 $<y$（因为数变小了 $2^x$ 还变大了），所以满足条件。 Fygon 易知答案是 $\leq 6$ 次的多项式，于是只要暴力模拟出 $n=0,1,\cdots,6$ 时的执行次数，然后拉格朗日插值即可。 Insider’s Information 考虑每次确定两边的一个元素。那么一个三元组 $(a,b,c)$ 相当于要求 $b$ 不是最早被确定的元素。 考虑先求出一个排列 $p$，满足对于每个三元组 $(a,b,c)$，$a,c$ 中都有一个在 $b$ 的前面。这个可以拓扑排序求出。 然后我们按照这个排列的顺序插入。一个三元组在排列中的顺序只有两种情况：$b$ 在第二个或者第三个。 假设第一个在左边。如果 $b$ 在第二个，那它应该插入到左边才能满足；如果 $b$ 在第三个，那它应该插入到右边才能满足。 这样子会有一些三元组要求当前元素插到左边、一些三元组要求当前元素插到右边，哪一种多就插到那边即可，这样子满足的三元组数一定不会少于不满足的。 NEERC NSub 2014 Fragmentation 如果 $i$ 与 $i+1$ 在同一段中，则连边 $(i,i+1)$，则我们相当于要最大化边数。 可以发现，如果 $a_i=a_{i+1}$，则两者在同一段内更优。下面设 $a_i\neq a_{i+1}$。 考虑怎样 $i$ 和 $i+1$ 才能连边： 首先显然要有 $a_i<a_{i+1}$。 如果存在一个 $j$ 使得 $a_i<a_j<a_{i+1}$，则不合法。为了方便可以先离散化，则应有 $a_i+1=a_{i+1}$。 如果 $a_{i-1}+1=a_i=a_{i+1}-1$，且 $a_i$ 出现次数大于 $1$，则不能同时连 $(i-1,i)$ 和 $(i,i+1)$。 对于一个 $c$，最多只能有一条边 $(i,i+1)$ 满足 $a_i=c,a_{i+1}=c+1$。 考虑 DP。设 $dp_i$ 表示只考虑权值 $\leq a_i$ 的边，且连了边 $(i-1,i)$ 时边数的最大值。 转移从 $a_j<a_i$ 的 $j$ 转移过来；如果 $a_i$ 出现超过一次，则还不能从 $a_i-1$ 转移。因此只需要维护一个最大值和次大值即可。 输出方案的时候不要忘记把之前去重去掉的加回来。 Kebeb House 设 $dp_{i,j}$ 表示前 $i$ 秒、做当前串时已经做了 $j$ 次梦的方案数。转移有两种： 如果这一秒不做梦，从 $dp_{i-1,j}$ 转移。 如果这一秒做梦，设 $p=i-t-1$，那么 如果 $p$ 时刻做的串不是当前串，那么那一串做几次梦都是可以的，所以从 $\sum dp_{p,k}$ 转移到 $dp_{i,1}$（这时一定有 $j=1$，因为 $i$ 是当前串第一个做梦的时刻）。 如果 $p$ 时刻做的串是当前串，从 $dp_{p,j-1}$ 转移。 NEERC NSub 2013 Heavy Chain Clusterization 把每种前后缀拿出来，对于每个串把它的前后缀连边，问题转化为求二分图最小点覆盖。
为了方便，下文中的多项式长度和 $n$ 均为 $2$ 的幂（多项式除法、三角函数和反三角函数除外），模数均为 $998244353$。 下面所有函数中（除了 NTT_init）传进去的 $n,m$ 都是多项式项数而不是次数。 多项式乘法 这是前置知识，如果不会建议「点开洛谷题面单击右边蓝色按钮题解」。 int r[N]; void NTT(int* A,int n,int op) { for (int i=0;i<n;++i) if (i<r[i]) swap(A[i],A[r[i]]); for (int i=1;i<n;i<<=1) { int rot=qpow(op==1?3:332748118,(mod-1)/(i<<1)); for (int j=0;j<n;j+=i<<1) for (int k=0,w=1;k<i;++k,w=1ll*w*rot%mod) { int x=A[j+k],y=1ll*w*A[j+k+i]%mod; A[j+k]=(x+y)%mod,A[j+k+i]=(x-y+mod)%mod; } } if (op==-1) { int inv=qpow(n,mod-2); for (int i=0;i<n;++i) A[i]=1ll*A[i]*inv%mod; } } int NTT_init(int n) { int lim=1,l=-1; for (;lim<n;lim<<=1,++l); for (int i=0;i<lim;++i) r[i]=(r[i>>1]>>1)|((i&1)<<l); return lim; } 多项式求导 $$ (x^a)'=ax^{a-1} $$ void getderi(int* F,int* G,int n) { for (int i=1;i<n;++i) G[i-1]=1ll*F[i]*i%mod; G[n-1]=0; } 多项式不定积分 $$ \int x^a\mathrm{d}x=\frac{x^{a+1}}{a+1} $$ void getinte(int* F,int* G,int n) { for (int i=1;i<n;++i) G[i]=1ll*F[i-1]*qpow(i,mod-2)%mod; G[0]=0; } 多项式牛顿迭代 已知 $G(x)$，求 $F(x)$ 满足 $G(F(x))\equiv 0\pmod{x^n}$。 假设我们已经求出了 $F_o(x)$ 满足 $G(F_0(x))\equiv 0\pmod{x^{\frac{n}{2}}}$，将 $G(x)$ 在 $F_0(x)$ 处泰勒展开得到 $$ G(F(x))=\sum_{i=0}^{+\infty}\frac{G^{(i)}(F_0(x))}{i!}(F(x)-F_0(x))^i $$ 可以发现 $i\geq 2$ 时在模 $x^n$ 意义下都为 $0$，所以 $$ G(F(x))\equiv G(F_0(x))+G'(F_0(x))(F(x)-F_0(x))\pmod{x^n} $$ 又 $G(F(x))=0$，化简得到 $$ F(x)=F_0(x)-\frac{G(F_0(x))}{G'(F_0(x))}\pmod{x^n} $$ 多项式求逆 已知 $F(x)$，求 $G(x)$ 满足 $F(x)G(x)\equiv 1\pmod{x^n}$。 Luogu 假设我们已经求出了 $G_0(x)$ 满足 $F(x)G_0(x)\equiv 1\pmod{x^{\frac{n}{2}}}$，那么 $$ F(x)(G(x)-G_0(x))\equiv 0\pmod{x^\frac{n}{2}} $$ 所以 $$ G(x)-G_0(x)\equiv 0\pmod{x^{\frac{n}{2}}} $$ 平方得到 $$ G(x)^2-2G(x)G_0(x)+G_0(x)^2\equiv 0\pmod{x^n} $$ 乘上 $F(x)$ 即可得到 $$ G(x)\equiv 2G_0(x)-F(x)G_0(x)^2\pmod{x^n} $$ 这样就可以由 $G_0(x)$求出 $G(x)$ 了。 void getinv(int* F,int* G,int n) { static int A[N],B[N]; if (n==1) { G[0]=qpow(F[0],mod-2); return; } getinv(F,G,n>>1); for (int i=0;i<n;++i) A[i]=F[i],B[i]=G[i]; int lim=NTT_init(n<<1); NTT(A,lim,1),NTT(B,lim,1); for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod*B[i]%mod; NTT(A,lim,-1); for (int i=0;i<n;++i) G[i]=(2ll*G[i]-A[i]+mod)%mod; for (int i=0;i<lim;++i) A[i]=B[i]=0; } 多项式对数函数 已知 $F(x)$，求 $G(x)$ 满足 $G(x)\equiv\ln F(x)\pmod{x^n}$。保证 $F(x)$ 常数项为 $1$。 Luogu 两边求导得到 $$ G'(x)\equiv\ln'(F(x))F'(x)\pmod{x^n} $$ 即 $$ G'(x)\equiv\frac{F'(x)}{F(x)}\pmod{x^n} $$ 求导+求逆后乘起来再不定积分回去即可。 void getln(int* F,int* G,int n) { static int A[N],B[N]; getderi(F,A,n),getinv(F,B,n); int lim=NTT_init(n<<1); NTT(A,lim,1),NTT(B,lim,1); for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod; NTT(A,lim,-1); getinte(A,G,n); for (int i=0;i<lim;++i) A[i]=B[i]=0; } 多项式指数函数 已知 $F(x)$，求 $G(x)$ 满足 $G(x)\equiv e^{F(x)}\pmod{x^n}$。保证 $F(x)$ 常数项为 $0$。 Luogu 两边取对数得到 $$ \ln G(x)-F(x)\equiv 0\pmod{x^n} $$ 不妨设 $H(G(x))\equiv \ln G(x)-F(x)\pmod{x^n}$，套牛顿迭代得到 $$ \begin{aligned} G(x)&\equiv G_0(x)-\frac{H(G_0(x))}{H'(G_0(x))}\pmod{x^n}\\ &\equiv G_0(x)-\frac{\ln G_0(x)-F(x)}{\frac{1}{G_0(x)}}\pmod{x^n}\\ &\equiv G_0(x)(1-\ln G_0(x)+F(x))\pmod{x^n} \end{aligned} $$ void getexp(int* F,int* G,int n) { static int A[N],B[N]; if (n==1) { G[0]=1; return; } getexp(F,G,n>>1); for (int i=0;i<n;++i) A[i]=G[i]; getln(G,B,n); for (int i=0;i<n;++i) B[i]=(mod-B[i]+F[i])%mod; B[0]=(B[0]+1)%mod; int lim=NTT_init(n<<1); NTT(A,lim,1),NTT(B,lim,1); for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod; NTT(A,lim,-1); for (int i=0;i<n;++i) G[i]=A[i]; for (int i=0;i<lim;++i) A[i]=B[i]=0; } 多项式幂函数 已知 $F(x)$ 和 $k$，求 $G(x)$ 满足 $G(x)\equiv F(x)^k\pmod{x^n}$。保证 $F(x)$ 常数项为 $1$。 Luogu 求 $\ln$ 后将系数乘上 $k$ 再 $\exp$ 回去即可。 void getpow(int* F,int* G,int n,int k) { static int A[N]; getln(F,A,n); for (int i=0;i<n;++i) A[i]=1ll*A[i]*k%mod; getexp(A,G,n); for (int i=0;i<n;++i) A[i]=0; } 如果不保证常数项为 $1$，可以先提一个 $a\times x^b$ 出来转化成常数项为 $1$ 的情况，最后再乘回去。 多项式开根 已知 $F(x)$，求 $G(x)$ 满足 $G(x)^2\equiv F(x)\pmod{x^n}$，多解保留常数项较小的那一个。 Luogu Luogu * 2 移项得到 $$ G(x)^2-F(x)\equiv 0\pmod{x^n} $$ 不妨设 $H(G(x))\equiv G(x)^2-F(x)\pmod{x^n}$，套牛顿迭代得到 $$ \begin{aligned} G(x)&\equiv G_0(x)-\frac{H(G_0(x))}{H'(G_0(x))}\pmod{x^n}\\ &\equiv G_0(x)-\frac{G_0(x)^2-F(x)}{2G_0(x)}\pmod{x^n}\\ &\equiv \frac{G_0(x)}{2}+\frac{F(x)}{2G_0(x)} \end{aligned} $$ void getsqrt(int* F,int* G,int n) { static int A[N],B[N]; if (n==1) { G[0]=Cipolla::calc(F[0]); return; } getsqrt(F,G,n>>1); for (int i=0;i<n;++i) A[i]=F[i]; getinv(G,B,n); int lim=NTT_init(n<<1); NTT(A,lim,1),NTT(B,lim,1); for (int i=0;i<lim;++i) A[i]=1ll*A[i]*B[i]%mod; NTT(A,lim,-1); for (int i=0;i<n;++i) G[i]=1ll*(A[i]+G[i])*inv2%mod; for (int i=0;i<lim;++i) A[i]=B[i]=0; } 那个 Cipolla::calc 是求二次剩余。 多项式除法 Luogu 根据题意有 $$ F(x)=G(x)Q(x)+R(x) $$ 即 $$ F(\frac{1}{x})=G(\frac{1}{x})Q(\frac{1}{x})+R(\frac{1}{x}) $$ 两边同乘 $x^n$ $$ x^nF(\frac{1}{x})=x^mG(\frac{1}{x})x^{n-m}Q(\frac{1}{x})+x^nR(\frac{1}{x}) $$ 可以发现 $x^nF(\frac{1}{x})$ 就是 $F(x)$ 系数翻转后得到的多项式，于是有 $$ F_R(x)=G_R(x)Q_R(x)+x^{n-m+1}R_R(x) $$ 因为 $Q_R(x)$ 是 $n-m$ 次式，所以我们模上 $x^{n-m+1}$ $$ F_R(x)\equiv G_R(x)Q_R(x)\pmod{x^{n-m+1}} $$ 即 $$ Q_R(x)\equiv\frac{F_R(x)}{G_R(x)}\pmod{x^{n-m+1}} $$ 多项式求逆即可。 求 $R(x)$ 就很简单了 $$ R(x)=F(x)-G(x)Q(x) $$ void getdiv(int *F,int *G,int n,int m,int *Q,int *R) { static int B[N],AR[N],BR[N],iBR[N]; for (int i=0;i<n;++i) AR[n-i-1]=F[i]; for (int i=0;i<m;++i) B[i]=G[i],BR[m-i-1]=G[i]; int lim1=1; for (;lim1<n-m+1;lim1<<=1); getinv(BR,iBR,lim1); int lim=NTT_init(n+lim1); NTT(iBR,lim,1),NTT(AR,lim,1); for (int i=0;i<lim;++i) Q[i]=1ll*iBR[i]*AR[i]%mod; NTT(Q,lim,-1); for (int i=n-m+1;i<lim;++i) Q[i]=0; reverse(Q,Q+n-m+1); lim=NTT_init(n); NTT(B,lim,1),NTT(Q,lim,1); for (int i=0;i<lim;++i) R[i]=1ll*B[i]*Q[i]%mod; NTT(Q,lim,-1),NTT(R,lim,-1); for (int i=0;i<lim;++i) R[i]=(F[i]-R[i]+mod)%mod; for (int i=m-1;i<lim;++i) R[i]=0; for (int i=0;i<lim;++i) B[i]=AR[i]=BR[i]=iBR[i]=0; } 多项式三角函数 Luogu 根据欧拉公式有 $$ e^{ix}=\cos x+i\sin x $$ 同理有 $$ e^{-ix}=\cos x-i\sin x $$ 所以 $$ \begin{aligned} \sin x&=\frac{e^{ix}-e^{-ix}}{2i}\\ \cos x&=\frac{e^{ix}+e^{-ix}}{2} \end{aligned} $$ 多项式 exp 即可。 有一个问题是这个 $i$ 是啥，其实就是 $-1$ 在模 $998244353$ 意义下的二次剩余。 void getsin(int *F,int *G,int n) { static int A[N],B[N],C[N]; for (int i=0;i<n;++i) A[i]=1ll*F[i]*img%mod; getexp(A,B,n),getinv(B,C,n); int inv=qpow(img<<1,mod-2); for (int i=0;i<n;++i) G[i]=1ll*(B[i]-C[i]+mod)*inv%mod; for (int i=0;i<n;++i) A[i]=B[i]=C[i]=0; } void getcos(int *F,int *G,int n) { static int A[N],B[N],C[N]; for (int i=0;i<n;++i) A[i]=1ll*F[i]*img%mod; getexp(A,B,n),getinv(B,C,n); int inv=qpow(2,mod-2); for (int i=0;i<n;++i) G[i]=1ll*(B[i]+C[i])*inv%mod; for (int i=0;i<n;++i) A[i]=B[i]=C[i]=0; } 多项式反三角函数 Luogu 先考虑 $\arcsin$。 $$ G(x)\equiv\arcsin F(x)\pmod{x^n} $$ 两边求导得到 $$ G'(x)\equiv\frac{F'(x)}{\sqrt{1-F(x)^2}}\pmod{x^n} $$ 再不定积分 $$ G(x)\equiv\int\frac{F'(x)}{\sqrt{1-F(x)^2}}\mathrm{d}x\pmod{x^n} $$ 多项式求导+开根+求逆+不定积分即可。 接着考虑 $\arccos$，同理可得 $$ G(x)\equiv-\int\frac{F'(x)}{\sqrt{1-F(x)^2}}\mathrm{d}x\pmod{x^n} $$ $\arctan$ 也一样 $$ G(x)\equiv\int\frac{F'(x)}{1+F(x)^2}\mathrm{d}x\pmod{x^n} $$ void getarcsin(int *F,int *G,int n) { static int A[N],B[N],C[N],D[N]; for (int i=0;i<n;++i) A[i]=F[i]; int lim=NTT_init(n<<1); NTT(A,lim,1); for (int i=0;i<lim;++i) A[i]=1ll*A[i]*A[i]%mod; NTT(A,lim,-1); for (int i=n;i<lim;++i) A[i]=0; for (int i=0;i<n;++i) A[i]=(mod-A[i])%mod; ++A[0]; getsqrt(A,B,n); getinv(B,C,n); getderi(F,D,n); lim=NTT_init(n<<1); NTT(C,lim,1),NTT(D,lim,1); for (int i=0;i<lim;++i) D[i]=1ll*C[i]*D[i]%mod; NTT(D,lim,-1); getinte(D,G,n); for (int i=0;i<lim;++i) A[i]=B[i]=C[i]=D[i]=0; } void getarccos(int *F,int *G,int n) { getarcsin(F,G,n); for (int i=0;i<n;++i) G[i]=(mod-G[i])%mod; } void getarctan(int *F,int *G,int n) { static int A[N],B[N],C[N]; for (int i=0;i<n;++i) A[i]=F[i]; int lim=NTT_init(n<<1); NTT(A,lim,1); for (int i=0;i<lim;++i) A[i]=1ll*A[i]*A[i]%mod; NTT(A,lim,-1); for (int i=n;i<lim;++i) A[i]=0; ++A[0]; getinv(A,B,n); getderi(F,C,n); lim=NTT_init(n<<1); NTT(B,lim,1),NTT(C,lim,1); for (int i=0;i<lim;++i) C[i]=1ll*B[i]*C[i]%mod; NTT(C,lim,-1); getinte(C,G,n); for (int i=0;i<lim;++i) A[i]=B[i]=C[i]=0; } 多项式多点求值 鸽了。 多项式快速插值 鸽了。