做题记录 25.9.18

szt100309 · 2025-09-18 11:45:37 · 个人记录

\textcolor{black}\odot AT_agc046_f [AGC046F] Forbidden Tournament

定义 \text{exlist}(u,v) 表示从 u 出发到 v 结束，中间经过若干点，且先经过的点向每个后经过的点连边的结构

显然竞赛图 \text{SCC} 缩点后得到 \text{exlist}=[a_1,a_2,\cdots,a_l]，每个 a_i 为一个 \text{SCC}

对于一个竞赛图上的 \text{SCC}，若其大小 \ge 3 则一定存在三元环

证明：显然一定存在一个长度 \ge 3 的环，若环长 >3 则取其任意一条弦，必然能得到更小的环，最终得到一个三元环

题目中禁止的结构为一个三元环指向一个点，若存在一个 |a_i|\ne 1(i<l) 则必然有 |a_i|\ge 3（两个点必然不是 \text{SCC}），即存在三元环，则该三元环一定指向 a_l，不合法，因此必有 a_{1\sim l-1} 为孤点

令 cal(n,k) 表示额外增加全图强连通的限制后 (n,k) 的答案，则原问题的答案为 [k=n-1]n!+\sum_{i=0}^{n-3} \binom ni i! cal(n-i,k-i)（其中枚举 l-1=i）

问题转化为如何求 cal(n,k)，即只考虑 a_k 的部分

用 ((p,q,r)) 表示三者构成三元环（p\to q\to r\to p），((p,q,r))\to s 表示一个题目中的结构

引理 1：对于 r\in P,p\in S,q\in S,p\to q，若 p\to r 则 q\to r

证明：

• 由于 r\in P,p\in S,q\in S，因此 r\to u,u\to p,u\to q
• 又 p\to q,p\to r，若 q\not\to r，则 q\gets r，有 ((u,p,r))\to q，不合法
• 因此必然有 q\to r

引理 2：P 为 \text{exlist}

证明：

• |P|\ge 3$ 时，若存在三元环 $((p,q,r))$，则 $((p,q,r))\to u$，不合法，因此 $P$ 不存在三元环，为 $\text{exlist}

引理 3：S 为 \text{exlist}

证明：

• 若不是，则存在三元环 ((p,q,r))\in S
• 若存在 d\in P,p\to d，根据引理 1 有 q\to d,r\to d，即 ((p,q,r))\to d，不合法，因此 p,q,r 没有向 P 的出边
• 若 |S|>3，对于任意 t\in S,t\notin((p,q,r))，必然不满足 ((p,q,r))\to t，因此有 t\to p/q/r，不妨设 t\to p，若 \exists s\in P,t\to s，则 p\to s，而 p 没有向 P 的出边，矛盾，因此 \forall s\in P,t\not \to s
• 从而 \forall x\in S,\nexists u\in P,x\to u，显然 \forall x\in S,x\not\to u，因此 S 为一个独立的 \text{SCC}，不满足要求
• 因此不存在这样的三元环，S 为 \text{exlist}

因此可以把 P 写为 x_{1\sim s}，S 写为 y_{1\sim t}，x_1\to x_2\to x_3\to\cdots\to x_s\to u\to y_1\to y_2\to y_3\to\cdots \to y_t，且 \forall x_i,x_i\to x_j(i<j)，\forall x_i,x_i\to u，\forall y_i,y_i\to y_j(i<j)，\forall y_i,u\to y_i

而 V=\{x_i\}\cup \{u\}\cup \{y_i\} 为一个 \text{SCC}，因此在 x 和 y 之间的边中必然存在 y\to x

引理 4：任意 x_i 恰好连向 y 的一个前缀

证明：

• 对于一个 x_i，若连向的不是 y 的前缀，则存在 j 使得 x_i\gets y_j,x_i\to y_{j+1}
• 显然 x_i\to u,u\to y_j,u\to y_{j+1},y_j\to y_{j+1}
• 因此 ((x_i,u,y_j))\to y_{j+1}，不合法

设 x_i\to y_{1\sim a_i}

引理 5：a 单调不降，且 a_1<t

证明：

• 若 a_1=t，则 x_1\to x_{2\sim s},x_1\to u,x_1\to y_{1\sim t}，即 V/\{x_1\} 单独构成 \text{SCC}，不符合要求，因此 a_1<t
• 若 a 存在下降位置，设 a_i>a_{i+1} 为第一个下降位置
• 若 a_i<t，说明 x_i\to y_{a_i},x_i\not\to y_{a_i+1}，x_{i+1}\not\to y_{a_i},x_{i+1}\not\to y_{a_i+1}
• 即 x_i\to y_{a_i},x_i\gets y_{a_i+1}，x_{i+1}\gets y_{a_i},x_{i+1}\gets y_{a_i+1}
• 而 x_i\to x_{i+1},y_{a_i}\to y_{a_i+1}
• 因此 ((x_i,y_{a_i},y_{a_i+1}))\to x_{i+1}，不合法
• 若 a_i=t，由于 a_1<t，则 1<i，从而 x_1\gets y_t,x_i\to y_t,x_{i+1}\gets y_t，又 x_1\to x_i\to x_{i+1},x_1\to x_{i+1}，因此 ((x_1,x_i,y_t))\to x_{i+1} 不合法
• 综上，必有 a_i\le a_{i+1}，a 单调不降

然后考虑 k 的限制

对于 u，其入度为 s，因此 s\le k

对于 x_i，其入度为 i-1+t-a_i，因此若 i-1+t-a_i>k 则这组 a_{1\sim s} 不合法

对于 y_j，显然 j<t 且 j\ne a_i 时入度不大于 j=t 或 j=a_i 时，因此只需要考虑这些位置

若 j=a_i（有多个 i 则取最小的），则 x_{i\sim s}\to y_j，u\to y_j，y_{1\sim j-1}\to y_j，因此入度为 s-i+1+j，若 s-i+1+a_i>k 则这组 a 不合法

若 j=t，则其入度为 \sum_i[a_i=t]+t，必然要有 t\le k，若存在 a_i=t 则取到那个 a_i 时已经计入限制了

总上，对 a 的限制为：

1. a_{1\sim s}\in[0,t]$，$\max(s,t)\le k
2. \forall 1\le i<s,a_i\le a_{i+1}
3. \forall 1\le i\le s,i-1+t-a_i\le k\land s-i+1+a_i\le k

对于 cal(n,k)，钦定 u=1，枚举 1\le s<n-1，剩下 n-1 个点分为 s 和 t=n-1-s 大小的两组，点的排列方案数为 \binom{n-1}s s!t!，显然边的排列方案数和满足要求的 a 一一对应，因此对 a 计数即可，容易 dp 做到 O(k^2)（令 f_{i,j} 表示 a_{1\sim i} 满足要求且 a_i=j 的方案数，转移是容易的）

总时间复杂度 O(n^2k^2)

代码

参考

QOJ #11115. Grotesque Team Reconstruction / 怪诞组队法

特判整张图不连通的情况，连通块数量 \ge 3 时必然不合法，连通块数量等于 2 时合法当且仅当两个连通块大小 \bmod 3=2

整张图连通时，求出点双，建立圆方树，圆点权值为 1，方点权值为 0

若存在一个子树权值和 \bmod 3=2，则从对应位置分离一定得到两个连通块且满足要求

若不存在一个子树权值和 \bmod 3=2，即所有子树权值和 \bmod 3 为 0/1

考虑一个方点，它的所有邻居组成一个点双

假如以该方点为根，则它的所有邻居都有 0/1 权值

若只有一个 1 权值的点，显然无法划分

否则必然至少 4 个（因为总和 \bmod 3=1）

即一个点双中每个点有 0/1 权值，要将它划分为两个连通块，满足两部分点权和 \bmod 3=2

取其中两个 1 作为起点和终点进行双极定向，不断删 0 度点直到剩余部分恰好有两个 1，显然被删部分和剩余部分都连通

因此若存在一个方点，它的邻居中存在 \ge 2 个 1 权值的点，则一定存在合法方案

时间复杂度 O(\sum (n+m))

代码

参考