AtCoder 题解

ABC140F Many Slimes

每个细菌都有一个 $s$ 值。

最初只有一个细菌。每一天原先的细菌都会生一个孩子，且孩子的 $s$ 值小于母体的 $s$ 值。

给定 $n$ 和 $2^n$ 个数。

判断是否存在一种情况，经过 $n$ 天后所有细菌的 $s$ 值为给定的数。

$n \le 10^5,s_i \le 10^9$

首先最大的数一定是原始细菌的 $s$ 值。然后考虑第 $i$ 天的细菌，它们所选择的 $s$ 一定要尽可能的大，如果选小了会使它们的后代选择变少。

然后对于每一天产生的每个细菌都按顺序贪心地选择一个尽可能大的值。

同一天选择的顺序是无关紧要的，下面给出证明：

考虑第 $i$ 天有两个选择的顺序上相邻的细菌 $a, b$ ，记它们父亲的 s 分别为 $A, B (A < B)$ 。

如果让 $a$ 先选，且两者的 $s$ 分别为 $x,y(x<y)$ 。

若 $y < A$ ，那么交换顺序后两者的 $s$ 就为 $y,x$ 。

由于 $a, b$ 在同一天产生，它们在决定后续方案时的地位相同，那么选择的顺序也就无关紧要了。

若 $y > A$ ，那么交换顺序后两者的 s 不变，选择的顺序连方案都不会影响。

为了方便，把父亲编号为 $j(j<2^i)$ 的细菌编号为 $j+2^i$ 。

然后直接按编号顺序确定 $s$ 就行了，为了支持删除和查找前驱，可以用 multiset 来维护没被选择的 $s$ 。

code

#include <bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i++)
#define per(i, r, l) for(int i = (r); i >= (l); i--)
#define mem(a, b) memset(a, b, sizeof a)

using namespace std;

int main() {
    cin >> n, m = 1 << n;
    multiset <int, greater <int> > s;
    For(i, 0, m) s.insert(read());
    vector <int> c;
    c.push_back(*s.begin()), s.erase(s.begin());
    For(i, 0, m) {
        For(j, 0, 1 << i) {
            auto it = s.upper_bound(c[j]);
            if(it != s.end()) c.push_back(*it), s.erase(it);
            else return puts("No") < 0;
        }
    }
    return puts("Yes") < 0;
    return 0;
}

AGC021F Trinity

对于 $n\times m$ 的 $01$ 矩阵 $mat$ ，定义序列 $A,B,C$ ：

$A_i(1\le i \le n)$ 表示最小的 $j$ 满足 $mat_{i,j}=1$ （如果没有则为 $m+1$ ）。

$B_i(1\le i \le m)$ 表示最小的 $j$ 满足 $mat_{j,i}=1$ （如果没有则为 $n+1$ ）。

$C_i(1\le i \le n)$ 表示最大的 $j$ 满足 $mat_{j,i}=1$ （如果没有则为 $0$ ）。

有多少种不同的三元组 $(A,B,C)$ ？模 $998244353$ 。

$n \le 8000,m\le 200$

设 $dp_{m,n}$ 表示强制每行至少有一个黑格时 $n\times m$ 矩阵的答案。

那么答案就是 $\sum_{i=0}^N\binom Nidp_{M,i}$ 。

转移考虑哪些行的第一个黑格在最后一列，分两种情况：

没有任何一行的第一个黑格在最后一列，那么最后一列可以没有黑格，可以恰好有一个，也可以多于一个，三种的方案对应的情况数分别是 $1,n,\binom n2$ ，转移系数为 $1+n+\binom n2$ 。
有 $k(k\ge 1)$ 行的第一个黑格在最后一列，相当于最后一列已经事先填好了 $k$ 个黑格，设这些黑格中自上到下第一个在第 $a$ 行，最后一个在倒数第 $b$ 行，这种方案对应的情况数是 $ab$ ，转移系数为

\sum_{a,b}\binom a1\binom{n-a-b}{k-2}\binom b1=\binom{n+2}{k+2}=\binom{n+2}{n-k}

综上，转移式为

dp_{m,n}=dp_{m-1,n}(1+n+\binom n2)+\sum_{k=0}^{n-1}dp_{m-1,k}\binom{n+2}k

转移可以使用 NTT 优化，复杂度 $O(NM\log N)$ ，下面有复杂度更低的做法。

转移时乘的是组合数，考虑写成 EGF：记 $F_m(x)=\sum dp_{m,n}\frac{x^n}{n!}$ 。

dp_{m,n}=\sum_{k=0}^ndp_{m-1,k}\binom{n+2}k-ndp_{m-1,n}

设

\begin{aligned} G(x)&=\sum_n\frac{x^n}{n!}\sum_{k=0}^{n-2}dp_{m-1,k}\binom nk\\ &=F_{m-1}(x)(e^x-x-1) \end{aligned}

那么把 $G(x)$ 中 $\frac{x^n}{n!}$ 的系数左移 $2$ 就可以得到转移式的第一部分，可以用求导实现左移 $\frac{x^n}{n!}$ 的系数。

易得第二部分为 $-xF_{m-1}'(x)$ 。

得到 $F_m(x)$ 的转移式：

F_m(x)=(F_{m-1}(x)(e^x-1-x))''-xF_{m-1}'(x)

由于这个转移式中 $F_{m-1}(x)$ 只乘了 $e^x,x$ 两个和 $x$ 有关的东西，考虑把 $F_m(x)$ 写成 $\sum_{a,b}f_{a,b}e^{ax}x^b$ ，显然 $F_m'(x)$ 也可以写成这个形式，并且 $e^x$ 和 $x$ 和最高次幂都不会比 $F_m(x)$ 大，所以 $F_m(x)$ 中 $e^x$ 和 $x$ 的最高次幂最多比 $F_{m-1}(x)$ 中 $e^x$ 和 $x$ 的最高次幂大 $1$ ，即不超过 $m$ 。

在 $\sum_{a,b}f_{a,b}e^{ax}x^b$ 的形式下，乘 $e^x,x$ 以及求导都是简单的。至此，已经可以 $O(m^2)$ 地从 $F_{m-1}(x)$ 推出 $F_m(x)$ 的 $\sum_{a,b}f_{a,b}e^{ax}x^b$ 表示。

最后考虑算答案，设 $F_M(x)=\sum_{a,b}f_{a,b}e^{ax}x^b$ 。

\begin{aligned} &\sum_{i=0}^N\binom Nidp_{M,i}\\ =&\sum_{i=0}^N\binom Ni\left[\frac{x^i}{i!}\right]F_M(x)\\ =&\left[\frac{x^N}{N!}\right]e^xF_M(x)\\ =&N!\sum_{a=0}^M\sum_{b=0}^{\min(N,M)}f_{a,b}\frac{(a+1)^{N-b}}{(N-b)!}\\ =&\sum_{a=0}^M\sum_{b=0}^{\min(N,M)}f_{a,b}(a+1)^{N-b}N^{\underline b} \end{aligned}

计算答案复杂度 $O(M^2\log N)$ 或 $O(M^2+M\log N)$ ，总复杂度 $O(M^3)$ 。

AGC017F Zigzag

容易想到用位向量来表示折线， $0$ 表示这一步向左走， $1$ 表示向右，容易得到折线的形态只有 $2^{N-1}$ 种。

由于相邻两条折线 $S,T$ 的约束关系是 $T$ 的每个前缀和都大于等于 $S$ 的对应前缀和。

不难想到轮廓线 DP，设 $f_{i,j,k,S}$ 表示满足以下条件的方案数：

第 $i$ 条折线已经填了前 $j$ 位。
$S$ 的前 $j$ 位是第 $i$ 条折线的，后 $N-1-j$ 位是第 $i-1$ 条折线的。
第 $i-1$ 条折线前 $j$ 位之和为 $k$ 。

转移就枚举第 $i$ 条折线第 $j+1$ 为填什么。

复杂度 $O(n^32^n)$ ，无法通过。

再次考虑相邻两条折线 $S,T$ 的约束关系，发现从 $S$ 到 $T$ 是以下过程：

把每个 $1$ 都往前移或不动，并且不改变相对顺序。
最后一个 $1$ 之后的 $0$ 任意变成 $1$ 。

重新定义 DP 状态 $f_{i,j,S}$ 表示正在确定了第 $i$ 条折线，当前为 $S$ ，已经固定了前 $j$ 个 $1$ 的方案数。

转移为：

如果存在第 $j+1$ 个 $1$ ，就枚举它往前移多少位，不能跨过前一个 $1$ ，这个枚举量平均是 $O(1)$ 的。
如果不存在，要么确定第 $i$ 条折线，要么枚举最后一个 $1$ 之后的一个 $0$ 把它变成 $1$ ，这个枚举量平均也是 $O(1)$ 的。

当确定第 $i$ 条折线后把不合法的状态置成 $0$ 。

复杂度 $O(n^22^n)$ 。

ARC078D Mole and Abandoned Mine

考虑从 $1-n$ 只有一条点不重复的路径的充要条件：

把这条唯一路径上的边都断开后路径上的点两两不连通。

假设知道这条唯一路径是 $u_1,u_2,\cdots,u_k$ （ $u_1=1,u_k=n$ ），要将点集划分成 $k$ 份，第 $i$ 份包含 $u_k$ ，最大化每个点集内部的边权之和。

可以得到一个状压做法：

设 $g_S$ 表示两个端点都在点集 $S$ 内部的所有边的权值之和。
设 $f_S$ 表示点集 $S$ 已经被考虑时，最大的保留边权之和。
转移为： $f_S \leftarrow f_{S-T} + g_T({T \subseteq S})$ ，其中 $T$ 恰好包含一个关键点。

由于并不知道这条路径，所以需要改一下 DP 状态：

设 $f_{i,S}$ 表示点集 $S$ 已经被考虑且 $1-i$ 只有一条路径时，最大的保留边权之和。

转移为:

$f_{i,S \cup \{i\}} \leftarrow f_{j,S} + w(j,i)(j \not\in S)$ 。
$f_{i,S\cup T} \leftarrow f_{i,S}+g_{T\cup\{i\}}(S \cap T = \varnothing)$ 。

复杂度 $O(n3^n)$ 。

ARC107F Sum of Abs

由于一个连通块的贡献带有绝对值符号，不太好处理，变成枚举符号不会影响答案。

现在变成如下问题：

每个点有三种状态：正、负、删，代价分别为 $-B_i,A_i,B_i$ 。
对于相邻的点 $u,v$ ，如果它们的状态都不是删，就必须相同。
求最小代价。

想到最小割模型，由于每个点有三种状态，所以把每个点 $i$ 变成两个点 $U_i,V_i$ 。

用 $(S,U_i),(U_i,V_i),(V_i,T)$ 三条边表示三种状态。

令它们的代价分别为 $\infty-B_i,\infty+A_i,\infty+B_i$ ，那么这三条边一定恰好割掉一条。

对于相邻的点 $(i,j)$ ，有两个约束关系：

不能同时割 $(S,U_i),(V_j,T)$ ，如果要割 $(S,U_i)$ ，说明 $U_i$ 能到达 $T$ ，如果要割 $(V_j,T)$ ，说明 $S$ 能到达 $V_j$ ，所以连一条 $(V_j,U_i)$ ，代价为 $\infty^2$ 的边。
不能同时割 $(S,U_j),(V_i,T)$ ，同理连一条 $(V_i,U_j)$ ，代价为 $\infty^2$ 的边。

最后答案为最小割减去 $n\infty$ 。

AGC038E Gachapon

先考虑一个弱化版问题： $B_i=1$ 时怎么做。

这是一个经典问题，一般做法有两种：状压 DP 和 min-max 容斥。

它们的复杂度都是 $O(n2^n)$ 或 $O(2^n)$ 的，然而这题数据范围是 $400$ ，说明需要用的此题的特殊性质。

通过 min-max 容斥可以得出答案为

\sum_{S}(-1)^{|S|+1}\frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i}

发现分母是小于 $400$ 的非负整数！可以用背包数出每种分母的贡献 $\sum_S(-1)^{|S|+1}$ 。

设

f_{i,j} = \sum_{S \subseteq \{1,2,\cdots,i\}}(-1)^{|S|+1}[\sum_{i \in S}A_i=j]

转移为 $f_{i,j}=f_{i-1,j}-f_{i-1,j-A_i}$ ，答案为

(\sum_{i=1}^n A_i)\sum_{i=0}^{400}\frac{f_{n,i}}i

现在回到原问题，还是考虑 min-max 容斥，答案就是

$\sum_{S}(-1)^{|S|+1}[S$ 中第一次有元素达到目标时的期望步数 $]$

设 $p_i=\frac{A_i}{\sum_{j \in S}A_j}$ 。

根据期望的线性性质，期望步数可以分摊到经过每个状态上。所以后面那坨东西为：

$\sum_{\forall i \in S,c_i<B_i}[$ 到达 $c$ 状态的概率 $]\cdot[$ 离开 $c$ 状态的期望步数 $]$

\begin{aligned} &=\sum_{\forall i \in S,c_i<B_i}\frac{(\sum_{i \in S}c_i)!}{\prod_{i \in S} c_i!}\prod_{i \in S}p_i^{c_i} \cdot \frac{\sum_{i=1}^n A_i}{\sum_{i \in S} A_i}\\ &=\sum_{\forall i \in S,c_i<B_i}\frac{(\sum_{i \in S}c_i)!}{\prod_{i \in S} c_i!}\prod_{i \in S}A_i^{c_i} \cdot \frac{\sum_{i=1}^n A_i}{(\sum_{i \in S} A_i)^{(\sum_{i \in S}c_i)+1}} \end{aligned}

把前面说的东西拼起来，答案为：

\begin{aligned} &\sum_S(-1)^{|S|+1}\sum_{\forall i \in S,c_i<B_i}\frac{(\sum_{i \in S}c_i)!}{\prod_{i \in S} c_i!}\prod_{i \in S}A_i^{c_i} \cdot \frac{\sum_{i=1}^n A_i}{(\sum_{i \in S} A_i)^{(\sum_{i \in S}c_i)+1}}\\ &=(\sum_{i=1}^n A_i)\sum_S(-1)^{|S|+1}\sum_{\forall i \in S,c_i<B_i}\frac{(\sum_{i \in S}c_i)!}{(\sum_{i \in S} A_i)^{(\sum_{i \in S}c_i)+1}} \cdot \prod_{i \in S}\frac{A_i^{c_i}}{c_i!} \end{aligned}

式子中比较难转移的东西就是 $\sum_{i \in S} A_i$ 和 $\sum_{i \in S}c_i$ ，把它们记状态里就行了。

状态为

f_{i,j,k}=\sum_{S \subseteq \{1,2,\cdots,i\}}(-1)^{|S|+1}\sum_{\forall i \in S,c_i<B_i}\prod_{i \in S}\frac{A_i^{c_i}}{c_i!}[\sum_{i \in S} A_i=j \land \sum_{i \in S}c_i=k]

转移为

f_{i,j,k}=f_{i-1,j,k}-\sum_{c=0}^{B_i-1}f_{i-1,j-A_i,k-c}\frac{A_i^c}{c!}

答案为

(\sum_{i=1}^n A_i)\sum_{i=1}^{400}\sum_{j=0}^{400}\frac{j!f_{n,i,j}}{i^{j+1}}

分析一下时间复杂度，虽然每次转移的枚举量是 $B_i$ ，但由于 $\sum_{i=1}^nB_i$ 是 $O(n)$ 的，所以总复杂度是 $O(n^3)$ ，空间复杂度可以用滚动数组优化到 $O(n^2)$ 。

AGC037D Sorting a Grid

考虑第三次操作前第 $i$ 行一定由 $(i-1)m+1$ 到 $im$ 构成，记 $(i-1)m+1$ 到 $im$ 的颜色为 $i$ 。

第二次操作的目标就是使颜色为 $i$ 的数在第 $i$ 行，所以第一次操作的目标就是使每一列 $n$ 种都颜色各有一个。

先考虑如何确定第一列的颜色，这显然是一个行与颜色的完美匹配问题。由于任意选 $i$ 行，这 $i$ 行的颜色数至少为 $i$ ，根据 Hall 定理，一定存在完美匹配。每一列依次求完美匹配就可以构造出一组解。

然后第二三次操作就非常简单了，复杂度 $O(n^4)$ 。

UPD: 这本质是正则二分图匹配问题，有 $O(n^2\log n)$ 的算法。

AGC043D Merge Triplets

考虑什么样的排列 $P$ 是能被造出来的。

考虑构造过程：每次选择一个头元素最小的序列 $A_i$ ，删除 $A_i$ 开头单调递减的一段，再继续找头元素最小的序列。

这启发我们把同时删除的元素看成一段，分段具有如下性质：

每一段是长度不超过 $3$ 的单调递减序列。
每一段的头元素递增。
长度为 $1$ 的段不少于长度为 $2$ 的段（因为每一个长度为 $2$ 的段必须要对应一个长度为 $1$ 的段来一起构成一个 $A_i$ ）。

同时，只要满足上面三个条件，这个 $P$ 就能被造出来的，将每个段配配对就可以得到一个生成 $P$ 的 $A$ 序列。

由于 $P$ 和分段内容是一一对应的，问题转化为对合法的分段内容计数。

枚举长度分别为 $1,2,3$ 的段数 $cnt_1,cnt_2,cnt_3$ ，满足 $cnt_1+2cnt_2+3cnt_3=3n$ 和 $cnt_1 \ge cnt_2$ 。

贡献即为

\binom{cnt_1+cnt_2+cnt_3}{cnt_1,cnt_2,cnt_3}\frac{(3n)!}{(cnt_1+cnt_2+cnt_3)!2^{cnt_2}3^{cnt_3}}

前面的组合数是划分出每一段的方案数，除以 $(cnt_1+cnt_2+cnt_3)!$ 是保证每一段的头元素递增，除以 $2^{cnt_2}3^{cnt_3}$ 是保证每一段的头元素为最大值。

复杂度 $O(n^2)$ 。

AGC049D Convex Sequence

考虑如何描述一个非负凸序列。

枚举最小值 $c$ ，以及取到最小值的第一个位置 $i$ ，令 $A=(c,c,\cdots,c)$ 。
多次选一个位置 $j<i$ ，将 $A_j,A_{j-1},A_{j-2},\cdots,A_1$ 分别加上 $1,2,3,\cdots,j$ 。
多次选一个位置 $j>i$ ，将 $A_j,A_{j+1},A_{j+2},\cdots,A_n$ 分别加上 $1,2,3,\cdots,n-j+1$ ，若 $i>1$ 则 $i-1$ 必须被选到一次。

第三步可以事先选 $i-1$ 一次，对总和产生 $\frac {i(i-1)}2$ 的贡献，然后第三步就和第二步一样了。

先枚举 $i$ ，第二三步本质上就是完全背包，由于体积的特性，有用的物品数量是 $O(\sqrt m)$ 的，可以 $O(m\sqrt m)$ 预处理出背包数组，然后 $O(\frac mn)$ 枚举 $c$ ，计算贡献。

这样做的复杂度为 $O(nm\sqrt m)$ ，无法通过。

考虑 $i \rightarrow i+1$ 时，物品最多删一个，也最多添一个，并且总改变次数是 $O(\sqrt m)$ 的，动态维护背包即可做到 $O(m\sqrt m)$ 的复杂度。

AGC050D Shopping

设 $f_{i,a,b,j}$ 表示从以下局面出发，还没有赢的人中从左到右第 $j$ 个人最终赢的概率。

有 $a$ 个人还没有赢且已经排除了 $i$ 个错误选项。
有 $b$ 个人还没有赢且已经排除了 $i+1$ 个错误选项。

转移就枚举这 $a$ 个人中下一个人是赢还是输即可（这里 $f_{i,0,b,j}=f_{i+1,b,0,j}$ ）。

$f_{i,a,b,j}=win \cdot f_{i,a-1,b,j-[j>b]} + lost \cdot f_{i,a-1,b+1,j}(j\ne b+1)$
$f_{i,a,b,b+1}=win + lost \cdot f_{i,a-1,b+1,b+1}(j\le b)$

复杂度 $O(n^4)$ 。

AGC041D Problem Scores

考虑任意 $k$ 道题的总分都小于任意 $k+1$ 道题的总分这个限制，发现它等价于前 $\lceil\frac n2\rceil$ 道题的总分小于后 $\lceil\frac n2\rceil-1$ 道题的总分。

考虑如何生成一个合法的序列 $A$ ：

枚举第 $\lfloor\frac n2\rfloor+1$ 道题的分值 $c$ ，令 $A=(c,c,\cdots,c)$ 。
多次选一个位置 $j<\lfloor\frac n2\rfloor+1$ ，将 $A_1,A_2,\cdots,A_j$ 全部减一。
多次选一个位置 $j>\lfloor\frac n2\rfloor+1$ ，将 $A_j,A_{j+1},\cdots,A_n$ 全部加一。
由于 $A_1 \ge 1$ ，所以第二种操作的次数不得超过 $c-1$ ，同理第三种操作的次数不得超过 $n-c$ 。
设前 $\lceil\frac n2\rceil$ 道题的总分减后 $\lceil\frac n2\rceil-1$ 道题的总分为 $x$ ，第一步后 $x=c$ ，第二种操作每一次都会使 $x$ 减小 $j$ ，第三种操作每一次都会使 $x$ 减小 $n-j+1$ ，因此第二、三种操作的总贡献要小于 $c$ 。

可以看出这是一个完全背包，第二种操作就是添加体积为 $1,2,\cdots,\lfloor\frac n2\rfloor$ 的物品，而且最多添加 $c-1$ 个，第三种操作就是添加体积为 $1,2,\cdots,\lceil\frac n2\rceil-1$ 的物品，最多添加 $n-c$ 个，总体积要小于 $c$ 。

对于第二种操作，考虑预处理 $L_{i,j}$ 表示选择 $i$ 个物品，总体积为 $j$ 的方案数。用传统背包做复杂度肯定不行，事实上它能直接转移：

L_{i,j}=L_{i-1,j-1}+L_{i,j-i}-L_{i-1,j-i-\lfloor\frac n2\rfloor}

对于第三种操作，同理可以预处理 $R_{i,j}$ 。

然后就可以枚举 $c$ 后 $O(n)$ 计算合法方案数。

复杂度 $O(n^2)$ 。

AGC027D Modulo Matrix

构造的思路是先黑白染色，然后填好黑格，再让每个白格满足：

它大于周围四个黑格。
它模周围四个黑格都等于 $1$ 。

填白格的过程是容易的，对于一个白格，先算出周围四个黑格的 $\text{lcm}$ ，然后尝试填 $\text{lcm}+1$ ，如果已经填过了，就继续尝试 $2\text{lcm}+1,3\text{lcm}+1,\cdots$ 。

如果没有值域限制，这题就做完了，考虑怎样让填的数尽可能小。

填白格没有什么好优化的（尝试过优先填 $\text{lcm}$ 较大的格子，但完全没有效果），所以考虑如何填黑格，才能使 $\text{lcm}$ 比较小。

填法一：顺序填或随机填，大概只能构造 $N$ 等于一百多。
填法二：考虑到一个白格周围四个黑格有两个是同一行的，有两个是同一列的，令 $A_{i,j}$ 是 $\text{lcm(i,j)}$ 的倍数，具体怎么确定，像确定白格那样确定，大概能构造 $N$ 等于两百多。
填法三：考虑到一个白格周围四个黑格只涉及四条斜线，令 $A_{i,j}$ 是 $\text{lcm}(i+j,i-j+n)$ 的倍数，大概能构造 $N$ 等于 $425$ 左右。
填法四：经过一番尝试，令 $A_{i,j}$ 是 $\text{lcm}(i+(n-j+1),i-(n-j+1)+n)$ （就是把列编号倒过来）可以通过。
填发五：考虑给每条斜线分配一个质数，黑格就等于所在的两条斜线质数的乘积，白格就等于周围四条斜线质数的乘积加一，一定不会有数重复。

填发四需要用 set 维护哪些数填过，复杂度 $O(n^2\log n)$ 。

填发五复杂度 $O(n^2)$ 。

AGC025D Choosing Points

对于两个距离为 $\sqrt D$ 的点 $(x_1,y_1),(x_2,y_2)$ ，考虑 $x_1-x_2,y_1-y_2$ 的奇偶性：

\begin{aligned} x_1 &\equiv x_2 \pmod 2,y_1 \equiv y_2 \pmod 2 \iff D \equiv 0 \pmod 4\\ x_1 &\equiv x_2 \pmod 2,y_1 \not\equiv y_2 \pmod 2 \iff D \equiv 1 \pmod 4\\ x_1 &\not\equiv x_2 \pmod 2,y_1 \not\equiv y_2 \pmod 2 \iff D \equiv 2 \pmod 4 \end{aligned}

因此 $D \bmod 4$ 说明了两点坐标差的奇偶性。

引理：将平面上距离为 $\sqrt D$ 的点对连边后是一张二分图。

考虑构造一个黑白染色方案，设 $\text{color}(x,y,D)=0/1$ 表示点 $(x,y)$ 的颜色。

当 $D\equiv 3\pmod 4$ 时，没有边， $\text{color}(x,y,D)=0$ 。
当 $D\equiv 2\pmod 4$ 时， $\text{color}(x,y,D)=x\bmod 2$ ，这样距离为 $\sqrt D$ 的点对就必然异色。
当 $D \equiv 1\pmod 4$ 时， $\text{color}(x,y,D)=(x+y)\bmod 2$ ，这样距离为 $\sqrt D$ 的点对就必然异色。
当 $D\equiv 0\pmod 4$ 时， $\text{color}(x,y,D)=\text{color}(\lfloor\frac x2\rfloor,\lfloor\frac y2\rfloor,\frac D4)$ ，下面证明为什么合法：

对于两个距离为 $\sqrt D$ 的点 $(x_1,y_1),(x_2,y_2)$ ，由于 $x_1 \equiv x_2 \pmod 2,y_1 \equiv y_2 \pmod 2$ ，所以
$\begin{aligned} \lfloor\frac {x_1}2\rfloor-\lfloor\frac {x_2}2\rfloor&=\frac 12(x_1-x_2)\\ \lfloor\frac {y_1}2\rfloor-\lfloor\frac {y_2}2\rfloor&=\frac 12(y_1-y_2) \end{aligned}$
进一步：
$\begin{aligned} &(x_1-x_2)^2+(y_1-y_2)^2=D\\ \Rightarrow &(\lfloor\frac {x_1}2\rfloor-\lfloor\frac {x_2}2\rfloor)^2+(\lfloor\frac {y_1}2\rfloor-\lfloor\frac {y_2}2\rfloor)^2=\frac D4\\ \Rightarrow &\text{color}(\lfloor\frac {x_1}2\rfloor,\lfloor\frac {y_1}2\rfloor,\frac D4)\ne\text{color}(\lfloor\frac {x_2}2\rfloor,\lfloor\frac {y_2}2\rfloor,\frac D4) \end{aligned}$

对于 $D_1$ 和 $D_2$ 分别黑白染色后本质有 $4$ 种颜色，这 $4$ 种颜色中肯定有一种点数大于等于 $n^2$ ，输出这种颜色的 $n^2$ 个点即可。

复杂度 $O(n^2)$ 。

AGC036D Negative Cycle

没有负环等价于差分约束有解，假设解为 $d_1,d_2,\cdots,d_n$ ，不妨令 $d_1=0$ 。

由于 $i\rightarrow i+1$ 的边是不能被删的，所以 $d$ 是单调不增的，也就是一段 $0$ ，一段 $-1$ ，一段 $-2\cdots$ 的形式。

考虑一段一段的枚举 $d$ ，上一段是 $[a,b]$ ，即 $d_{a,a+1,\cdots,b}=x+1$ ，枚举了新的一段 $[b+1,c]$ ，即 $d_{b+1,b+2,\cdots,c}=x$ ，分析哪些边需要删：

对于 $b+1\le i < j \le c$ ，边 $(i,j)$ 需要删除。
对于 $b+1\le i\le c,j<a$ ，边 $(i,j)$ 需要删除。

然后就可以 DP 了，设 $f_{a,b}$ 表示填的最后一段为 $[a,b]$ 时的最小代价，转移为

f_{a,b}+\text{cost}_1(b+1,c)+\text{cost}_2(b+1,c,a-1)\rightarrow f_{b+1,c}

其中 $\text{cost}_1$ 和 $\text{cost}_2$ 在预处理二维前缀和后可以 $O(1)$ 算。

复杂度 $O(n^3)$ 。

AGC045D Lamps and Buttons

如果 Snuke 按到了 $p_i=i$ 的位置就死了，所以他要最小化有解时死的概率，分析 Snuke 的最优策略：

最初需要按下一个按钮，由于 Snuke 不知道排列，所以按每个按钮都是一样的，不妨按 $1$ 。
如果按下了 $p_i=i$ 的按钮就死了。
否则， $p_i$ 一定是一个安全的按钮，继续按下 $p_i$ ，这样就可以安全地按下许多按钮。
又需要尝试一个按钮时就按没按过的编号最小的按钮。

于是，得到了 Snuke 胜利的充要条件：假设 $1-A$ 中第一个满足 $p_i=i$ 的 $i$ 为 $\min$ ， $\forall i>A,\exists j<\min$ 使得 $j$ 能到达 $i$ 。

容易想到枚举 $\min$ ，把排列看成若干个循环，要求 $\min$ 前面没有孤立点，这个可以容斥：

钦定 $i$ 个孤立点，系数为 $(-1)^i\binom{\min-1}i$ 。
对于 $[1,\min-1]$ 中剩下的 $\min-1-i$ 个点先生成若干个循环，方案数为 $(\min-1-i)!$ 。
对于 $[A+1,n]$ 中的点，它们只能加入前面的循环，方案数为 $(\min-1-i)^{\overline{n-A}}$ 。
对于 $[\min+1,A]$ 中的点，它们既可以加入前面的循环，又可以新建一个环，方案数为 $(\min-1-i+n-A)^{\overline{A-\min}}$ 。

综上，得到 $\min$ 的贡献为：

\sum_{i=0}^{\min-1}(-1)^i\binom{\min-1}i\frac{(n-1-i)!(\min-1-i)}{\min-1-i+n-A}

当 $\min$ 不存在时需要特判，贡献为：

\sum_{i=0}^A(-1)^i\binom Ai(n-i)!

复杂度 $O(A^2+n)$ 。

AGC041E Balancing Network

对于 $T=1$

将网络抽象成一张有向图：

将每条线的起点、终点和平衡器的端点抽象成结点。
同一条线上的结点后面向前面连边。
平衡器抽象成两个方向的边。

考虑暴力怎么做，枚举最终汇聚到第 $t$ 条线，判断 $t$ 的终点是否可以到达所有的起点。

可以用一个 bitset 来压哪些汇点能到达这个点，然后 DFS 来求这些 bitset。可以做到 $O(\frac {nm}{\omega})$ 的复杂度。

对于 $T=2$

$n=2$ 时显然无解，下面构造说明了 $n>2$ 时一定有解。

考虑从右往左依次插入每个平衡器，维护 $size_i$ 表示当前网络有多少个起点会到达第 $i$ 条线的终点。

初始时， $size_i=1$ 。
加入平衡器 $(x,y)$ 时，要么 $size_x+1$ ，要么 $size_y+1$ ，选择 $size_x$ 和 $size_y$ 中较小的一个 $+1$ 。一定不会出现 $size_x=n-1\land size_y=n-1$ 的情况，因为 $size_x+size_y\le n$ 。

复杂度 $O(n+m)$ 。

ABC214G Round Robin

以下解法可以解决 $n \le 10^5$ 的问题。

设 $F_k$ 表示确定 $k$ 个位置的值 $r_{i_1},r_{i_2},\cdots,r_{i_k}(i_1<i_2<\cdots<i_k)$ 满足以下条件的方案数：

\forall x\in[1,k],r_{i_x}=p_{i_x}\lor r_{i_x}=q_{i_x}

根据二项式反演，答案为

\sum_{i=0}^n(-1)^iF_i(n-i)!

将 $p_i,q_i$ 连边，得到一张由若干个环组成的图，选择一个满足 $r_i=p_i\lor r_i=q_i$ 的位置 $i$ 就是选择一条边并占用一个端点，这对于每个环是独立的，所以对每个环求出 $F$ 数组，再用分治 FFT 合并就可以得到整张图的 $F$ 数组。

考虑求一个大小为 $m$ 的环的 $F$ 数组，假设点编号为 $1,2,\cdots,m$ ，边为 $(1,2),(2,3),\cdots,(m-1,m),(m,1)$ ，将选择 $i$ 条边的方案分为以下两类：

不选边 $(1,2)$ ，把边 $(2,3)$ 占用 $2$ 的方式编号为 $1$ ，边 $(2,3)$ 占用 $3$ 的方式编号为 $2$ ，边 $(3,4)$ 占用 $3$ 的方式编号为 $3$ ，边 $(3,4)$ 占用 $4$ 的方式编号为 $4$ ，依次类推。方案就是从 $2m-2$ 种选择方式选 $i$ 种，限制就是编号相邻的不能同时选择。

引理：从 $n$ 个物品中选 $r$ 个，编号相邻的不能同时选择的方案数为 $\binom {n-r+1}r$ 。

证明：将选择的第 $i$ 个物品的编号减去 $i-1$ 就得到了从 $n-r+1$ 个物品中选 $r$ 个的方案数。

这部分方案数为 $\binom{2m-i-1}i$ 。
选边 $(1,2)$ ，那么边 $(1,2)$ 可以占用 $1$ 或 $2$ ，但两种方式是等价的，不妨假设占用了 $1$ 。方案就是从 $2m-3$ 种选择方式选 $i-1$ 种，限制还是编号相邻的不能同时选择。

这部分方案数为 $2\binom{2m-i-1}{i-1}$ 。

对于一个大小为 $m$ 的环

F_i=\binom{2m-i-1}i+2\binom{2m-i-1}{i-1}=\binom{2m-i}i+\binom{2m-i-1}{i-1}

然后每个环的 $F$ 就可以 $O(n)$ 求了，复杂度瓶颈在于分治 FFT，复杂度 $O(n\log^2n)$ 。

分治 FFT 有两种优化：

由于每个环的大小之和为 $n$ ，故只有 $O(\sqrt n)$ 种大小不同的环，大小相同的环可以通过快速幂 $O(n\log n)$ 地算出乘积。
整个分治过程形成一棵二叉树的结构，总时间就是 $\sum_{u\in \mathbb{leaf}}\text{degree}_u\text{depth}_u$ ，最小化时间就是 Huffman 树，每次贪心地将两个次数最小的多项式乘起来。

ABC214H Card Deck Score

走到了一个强连通分量就肯定会走完内部的所有点，缩点后图就变成了 DAG，假设原图就是 DAG。

想到用最小费用流解决：

把每个点 $u$ 拆成 $\text{in}_u$ 和 $\text{out}_u$ 。
$\text{in}_u$ 向 $\text{out}_u$ 连一条容量为 $1$ ，费用为 $-X_u$ 的边，再连一条容量为 $K$ ，费用为 $0$ 的边。
对于原图中的边 $(u,v)$ ， $\text{out}_u$ 向 $\text{in}_v$ 连一条容量为 $K$ ，费用为 $0$ 的边。
$S$ 向 $\text{in}_1$ 连一条容量为 $K$ ，费用为 $0$ 的边， $\text{out}_u$ 向 $T$ 连一条容量为 $K$ ，费用为 $0$ 的边。

SSP 算法肯定是通过不了的，考虑变成 Primal-Dual 算法可以做的问题。

Sol 1

初始图是一张 DAG，可以跑一遍 DP 预处理最短路作为点的初始势能。

Sol 2

求出 DAG 的一组拓扑序，然后给每个点按拓扑序从大到小重新编号（也就是缩完点后的编号）。

容易构造一组满足差分约束的初始势能：

$S$ 势能为 $\sum X_u$ ， $T$ 势能为 $0$ 。
$\text{in}_u$ 的势能为 $\sum_{i=1}^uX_i$ ， $\text{out}_u$ 的势能为 $\sum_{i=1}^{u-1}X_i$ 。

上述两种做法复杂度都是 $O(nK\log n)$ 。

AGC027E ABBreviate

考虑什么样的串能变成单个字母 $a$ 或 $b$ 。

打表发现能变成 $a$ 的串 $S$ 满足的 $a,b$ 数量关系是 $a$ 的数量减 $b$ 的数量模 $3$ 余 $1$ ，并且这个条件在 $|S|$ 为偶数时也是充分条件，当 $|S|$ 为奇数时恰好多了一个串 $ababab\cdots aba$ 。

引理一：记 $p(S)$ 表示 $S$ 中 $a$ 的个数减 $b$ 的个数模 $3$ ， $S$ 能变成单个字母 $c$ 当且仅当：

$p(S)=p(c)$

$S=c$ 或 $S$ 中有相邻的相同字母。

必要性显然，下面证明充分性：当 $|S|\le 3$ 时显然成立，当 $|S|>3$ 时取出 $S$ 中最长的连续相同子串，不妨假设它是 $n$ 个 $a$ ，分两种情况讨论：

$n \ge 4$ ，直接将前两个 $a$ 合并， $|S|$ 减小了 $1$ ，并且还满足引理条件。
$n\le 3$ ，由于 $|S|>3$ ，这个子串不可能前后都没有字母，不妨假设它不在开头，那么它前面必然是 $b$ ，将前两个 $a$ 合并成 $b$ ，那么此时有两个 $b$ 会相邻， $|S|$ 减小了 $1$ ，并且还满足引理条件。

然后问题就转化成了有多少个串 $T$ 满足以下条件：

存在一种将 $S$ 划分为 $|T|$ 段的方式，使得每一段与 $T$ 中的对应字母满足引理一。

这个问题的主要难点在于引理一的条件二。

事实上，当 $S$ 中有相邻的相同字母时，忽略引理一的条件二 不会影响答案。

引理二：若 $S$ 中有相邻的相同字母， $S$ 能够变成 $T$ 当且仅当：

存在一种将 $S$ 划分为 $|T|$ 段的方式，设 $S$ 被划分成了 $S_1,S_2,\cdots,S_{|T|}$ ， $T$ 中每个字母分别为 $T_1,T_2,\cdots,T_{|T|}$ 。

满足 $\forall i,p(S_i)=p(T_i)$ 。

必要性显然，下面证明充分性：

假设存在一组满足上述条件的划分 $(S_1,S_2,\cdots,S_{|T|})$ 。
将 $S_1,S_2,\cdots,S_{|T|-1}$ 的长度最小化得到新的划分 $(S_1',S_2',\cdots,S_{|T|}')$ 。
由于最小化，容易发现 $S_1,S_2,\cdots,S_{|T|-1}$ 已经满足了引理一。
此时 $S_{|T|}$ 有可能不合法，比如 $S_{|T|}=abab\cdots aba$ ，由于不合法时 $|T|>1$ ，可以让 $S_{|T|}$ 只保留最后一个字母，把前面的部分扔给 $S_{|T|-1}$ ，于是 $T$ 删去最后一个字母对于 $S$ 删去最后一个字母满足引理二，故 $S$ 可以变成 $T$ 。

有了引理二就很好做了，特判掉 $S$ 中没有相邻的相同字母的情况，容易用一个自动机来判断 $T$ 是否合法，计数可以在自动机上 DP。

复杂度 $O(n)$ 。

ABC215H Cabbage Master

如何判定当前的卷心菜是否能满足所有公司？

$S$ 向卷心菜 $i$ 连容量为 $A_i$ 的边。
公司 $i$ 向 $T$ 连容量为 $B_i$ 的边。
如果 $c_{i,j}=1$ ，那么卷心菜 $i$ 向公司 $j$ 连容量为 $\infty$ 的边。
$\max flow=\sum_{i=1}^mB_i$ 。

也等价于 $T$ 的所有入边不是最小割。由于 $S$ 的出边很少，考虑枚举最小割中有哪些 $S$ 的出边，假设这些边为 $mask$ ，割掉 $mask$ 后有一些 $T$ 的入边就不需要割了，假设这些边的容量和为 $sum$ ，那么需要吃点的卷心菜数量就是 $\sum_{i\in mask}A_i-sum+1$ ，要求 $sum>0$ 。

这时就可以解决第一问了，考虑对于所有 $mask$ ，怎么求它们的 $sum$ ，注意到 $B_i$ 贡献给 $mask$ 的条件是 $mask$ 包含所有能供应给公司 $i$ 的卷心菜，可以用子集前缀和 (FMT) 求出。然后枚举 $mask$ 用 $\sum_{i\in mask}A_i-sum+1$ 更新第一问的答案即可。

第二问还要进一步分析，为了不算重，我们枚举一个 $mask$ 表示被吃的卷心菜品种的集合，一个 $mask$ 可行当前仅当存在一个取到第一问答案的 $S$ ，使得 $mask\subseteq S$ ，这个同样可以用 FMT 做。设第一问答案为 $ans$ ，最后是对于一个 $mask$ ，求有多少种从 $mask$ 中吃掉 $ans$ 个卷心菜的方式，满足 $mask$ 中的每种卷心菜至少被吃一个。容易想到容斥，钦定一些卷心菜品种不吃，然后不考虑每种卷心菜必吃的限制，但对每个 $mask$ 都通过容斥来计算复杂度高达 $O(3^n)$ 。

设 $f_S$ 表示有多少种从 $S$ 中吃掉 $ans$ 个卷心菜的方式，满足 $mask$ 中的每种卷心菜至少被吃一个，发现

\sum_{T\subseteq S}f_T=\binom{\sum_{i\in S}A_i}{ans}

对右边做 IFMT 就可以求得 $f$ 数组。

复杂度 $O(n2^n+nm)$ 。

AGC020E Encoding Subsets

先考虑对于一个串 $S$ 如何单独计算答案，这个不难，容易想到用区间 DP 做。设 $f_{l,r}$ 表示子串 $[l,r]$ 的改写方案数，转移分两种：

$s_l$ 没有参与改写，贡献为 $f_{l+1,r}$ 。
$s_l$ 参与改写了，枚举最外层的覆盖 $s_l$ 的改写：周期 $T$ 和循环次数 $i>1$ ，如果合法，则贡献为 $f_{l,l+T-1}\cdot f_{l+Ti,r}$ 。

当尝试用区间 DP 做原问题的时候，发现做不了，因为当 $s_l$ 参与改写时，原来的 $f_{l,l+T-1}$ 不再是一个区间的 DP 值。详细地说，设 $f(s)$ 表示字符串 $s$ 的答案（子集的改写方案数总和），设 $suf(i)$ 表示 $s$ 从 $s_i$ 开始的后缀，转移为两种：

第一个字符没有参与改写，贡献为 $(s_0+1)f(suf(1))$ 。
第一个字符参与了，枚举最外层的覆盖 $s_l$ 的改写：周期 $T$ 和循环次数 $i>1$ ，由于每个周期内要相等，所有子集的限制要叠加，设 $s[l,r]$ 表示 $s$ 的第 $l$ 个字符到第 $r$ 个字符的子串，设
$t=s[0,T-1]\&s[T,2T-1]\&\cdots\&s[T(i-1),Ti-1](\&\ is\ \text{bitand})$
那么贡献为 $f(t)\cdot f(suf(Ti))$ 。

这里的复杂度上限看起来是 $O(2^{n+1})$ ，这个题最重要的地方就是，你要看出来这个做法其实是 $O($ 能过 $)$ 的，进而分析出其真正的复杂度，而不是被假上限给吓跑了。

下面证明，有一个上界是 $O(n^3+2^{\frac n8})$ 。首先长度小于等于 $\frac n8$ 的串最多有 $2^{\frac n8}$ 个，长度大于等于 $\frac n8$ 的串最多被压缩两次（因为每压缩一次长度减半），只有三种压缩方式：

先选择一个子段划分成 $2$ 段，再选择一个子段划分成 $2$ 段。
先选择一个子段划分成 $2$ 段，再选择一个子段划分成 $3$ 段。
先选择一个子段划分成 $3$ 段，再选择一个子段划分成 $2$ 段。

显然第一种压缩方式可以得到的串是最多的，考虑第一种压缩方式得到的串是怎样的，形如：

$s[a,a+k-1]\&s[a+k,a+2k-1]\&s[b,b+k-1]\&s[b+k,b+2k-1]$

显然它是由 $a,b,k$ 三个参数决定的，故数量是 $O(n^3)$ ，因此三种压缩方式的总和也是 $O(n^3)$ 。

另外，通过打表可以求出长度大于 $12$ 的串更为精准的上界为 $41703$ 。

对于 T=1T=1T=1

对于 T=2T=2T=2

Sol 1

Sol 2

对于 $T=1$

对于 $T=2$