做题记录 5 / 世间所有路都将与你相逢

Priestess_SLG · 2026-08-04 18:39:57 · 个人记录

注：黑+ 上面还有 彩- / 彩 / 彩+ 三个等级（）

应某人要求，跳过了一些敏感的编号。

2026 超新星战队 B & B+ 队暑假集训模拟赛 day5

A

:::info[Description] Link :::

:::info[Solution]{open} 考虑一个元素一个元素的归位。

设当前要处理的位置是 i，值为 i 的元素位于位置 p。若此时 i\neq p 则一个暴力的做法是直接每次交换相邻两个元素把 p 位置的元素换到 i 位置来。

考虑优化操作次数。容易想到折半，每次对 [i,p] 区间处理，如果区间长度是奇数先交换 p-1,p 两个位置让需要处理的区间长度变为偶数，然后直接对整个区间做一次交换，此时位置 p 到 i 的距离减半。因此只需要 O(\log n) 次操作就可以把 p 位置的元素移动到 i 位置上。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int a[N], pos[N];
inline void gao(int l, int r) {
    for (int i = l; i <= (l + r) / 2; ++i) {
        swap(a[i], a[i + (r - l + 1) / 2]);
        swap(pos[a[i]], pos[a[i + (r - l + 1) / 2]]);
    }
}

inline void sol([[maybe_unused]]int __testcase_id) {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], pos[a[i]] = i;
    vector<pair<int, int>> op;
    for (int i = 1; i <= n; ++i) {
        while (pos[i] != i) {
            int l = i, r = pos[i];
            if ((r - l + 1) & 1) {
                op.emplace_back(r - 1, r);
                op.emplace_back(l, r - 1);
                gao(r - 1, r), gao(l, r - 1);
            } else {
                op.emplace_back(l, r);  
                gao(l, r);
            }
        }
    } cout << op.size() << '\n';
    for (auto &[i, j] : op) cout << i << ' ' << j << '\n';
}

} // namespace lowspeed_song

:::

难度：绿

鲜活指数：8

B

:::info[Description] Link :::

:::info[Solution]{open}

:::

C

D

E

:::info[Description] Link :::

:::info[Solution]{open} 为了方便，这里把 A 数组降序排序。

设在某一时刻当前还没有被弹出的 A 集合内最大的元素为 A_j，则之后插入一个不属于 A 的数 x 时必须满足 x>A_j。证明考虑如果插入了一个数 x<A_j 且 x\not\in A 则以后想要把 A_j 弹出来之前必须先弹出来 x，此时 Y 中出现了不属于 A 集合中的元素。

如果某一时刻 - 操作之前堆中有 A 集合内的元素，并且所有插入的非 A 集合元素都大于当前最大的没有被弹出的 A_j 则 - 操作弹出的元素必然属于 A 集合。

考虑维护当前时刻的 A_j 值。考虑贡献延后处理，插入一个属于 A 集合中的元素时先只确定这个位置放的是 A 集合内元素，暂时不确定具体放的是哪一个数。只有当前最大没有被弹出的 A_j 被弹掉的时候再统一给之前的位置分配具体的 A 值。

具体的：设 f_{i,j,k,o} 表示当前已经处理完了串 S 的前 i 个操作，当前还没有进入 Y 集合的最大 A 元素是 A_j，当前 X 集合中有 k 个属于 A 集合的元素，A_j 自己目前是否已经在 X 集合中（o=1/0），有多少种不同的合法加入集合顺序。

初始条件显然就是 f_{0,0,0,0}=1。这里 X 集合中其他属于 A 集合的元素暂时先不考虑是谁。

然后考虑如果当前遇到了一个 + 操作，则先设前 i 次操作中有 p 个 + 操作和 q 个 - 操作，则当前 X 集合的大小就是 p-q。

考虑如果插入非 A 集合的元素，则只能选择 x>A_j\land x\not\in A 的元素 x 插入，这样的元素 x 的数量为 n-A_j-j。而此时用掉的非 A 集合元素数是 p-q-k，这些元素显然都在当前满足条件 x>A_j\land x\not\in A，因此这次操作可选的非 A 集合元素个数就是 n-A_j-j-p+q+k，转移就是 f_{i+1,j,k,o}\leftarrow f_{i+1,j,k,o}+f_{i,j,k,o}(n-A_j-j-p+q+k)。

如果当前插入 A 集合中的元素，则状态中的 k 值肯定会自增 1。如果当前插入的值恰好就是 A_j 则只有 o=0 的时候才是被允许，此时让 o\leftarrow 1 即可，转移就是 f_{i+1,j,k+1,1}\leftarrow f_{i+1,j,k+1,1}+f_{i,j,k,o}。

如果当前插入的值恰好不是 A_j，则先不管这个插入的元素是谁也暂时先不考虑贡献，直接转移即 f_{i+1,j,k+1,o}\leftarrow f_{i+1,j,k+1,o}+f_{i,j,k,o}。

然后考虑如果当前遇到了一个 - 操作，则此时因为弹出的元素必须属于 A 集合，所以这里必须先保证 k>0 才能继续转移。

同样考虑分类讨论：

如果当前弹出的元素不是 A_j，则：

• 如果当前 o=0，则 A_j 根本就不在堆里，当然不会弹出 A_j 元素。
• 否则，如果 o=1\land k>1 则堆里除了 A_j 以外还有其他属于 A 集合内的元素，她们全都小于 A_j 因此小根堆里肯定会先弹出其他元素。

总结一下，如果当前 k>0 且 k=1,o=1 两个条件不同时成立，这次操作就会弹出一个匿名的 A 集合内元素，转移就是 f_{i+1,j,k-1,o}\leftarrow f_{i+1,j,k-1,o}+f_{i,j,k,o}。这里继续不乘 k 是因为当前小根堆弹哪个元素实际上由具体的值唯一确定，而各个匿名元素的具体值继续延后考虑，暂时不处理。

如果当前弹出的值是 A_j 则由上面的分析可知此时必然满足 k=1\land o=1，此时堆中唯一一个属于 A 集合的元素就是 A_j 所以这次 - 操作一定必须把 A_j 弹出。弹出后 X 集合中就没有任何属于 A 集合内的元素了。

考虑之前一共有 q-j 个已经被弹出，但是具体值还没有被确定的 A 集合内匿名元素，则现在考虑枚举其中有多少个原始的值属于紧接的 A_{j+1},A_{j+2},A_{j+3},\ldots。假设选择 m 个匿名位置分别赋值为 A_{j+1},A_{j+2},\ldots,A_{j+m} 则说明这连续的 m 个元素在之前已经被弹出来，新的没有被弹出的最大元素就是 A_{j+m+1}。简单组合一下，从 q-j 个匿名位置中选择 m 个位置然后把 m 个不同的值排列进去的方案数就是 \binom{q-j}mm!=\frac{(q-j)!}{(q-j-m)!}。因此此时堆所有 m\in[0,\min(M-j-1,q-j)] 都有转移 f_{i+1,j+m+1,0,0}\leftarrow f_{i+1,j+m+1,0,0}+f_{i,j,k,o}\times\frac{(q-j)!}{(q-j-m)!}。

:::success[Code]

namespace lowspeed_song {

int fac[N], inv[N], ifac[N];

inline void init() {
    fac[0] = inv[0] = ifac[0] = 1;
    fac[1] = inv[1] = ifac[1] = 1;
    for (int i = 2; i < N; ++i) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        ifac[i] = ifac[i - 1] * inv[i] % mod;
    }
}

inline int binom(int a, int b) {
    if (b < 0 || a < b) return 0;
    return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}

char s[610];
int f[2][310][310][2], a[310];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, m, q = 0; cin >> n >> m;
    scanf("%s", s);
    for (int i = 0; i < m; ++i) cin >> a[i];
    sort(a, a + m, greater<>());
    f[1][0][0][0] = 1;
    for (int i = 0; i < n + m; ++i) {
        memset(f[i & 1], 0, sizeof f[i & 1]);
        for (int j = 0; j <= m; ++j)
            for (int k = 0; k <= m; ++k)
                for (int o : {0, 1}) {
                    if (s[i] == '+') {
                        if (n - a[j] - j - i + q + q + k > 0) f[i & 1][j][k][o] = (f[i & 1][j][k][o] + (n - a[j] - j - i + q + q + k) * f[~i & 1][j][k][o]) % mod;
                        if (j < m && !o && m - q - k > 0) f[i & 1][j][k + 1][1] = (f[i & 1][j][k + 1][1] + f[~i & 1][j][k][o]) % mod;
                        if (m - q - k + o > 1) f[i & 1][j][k + 1][o] = (f[i & 1][j][k + 1][o] + f[~i & 1][j][k][o]) % mod;
                    } else if (k) {
                        if (k != 1 || o != 1) f[i & 1][j][k - 1][o] = (f[i & 1][j][k - 1][o] + f[~i & 1][j][k][o]) % mod;
                        else for (int p = 0; p <= min(q - j, m - j - 1); ++p) f[i & 1][j + p + 1][0][0] = (f[i & 1][j + p + 1][0][0] + f[~i & 1][j][k][o] * fac[q - j] % mod * ifac[q - j - p] % mod) % mod;
                    }
                }
        if (s[i] == '-') ++q;
    } cout << f[~(n + m) & 1][m][0][0] << '\n';
}

} // namespace lowspeed_song

:::

难度：黑

鲜活指数：9

2026 超新星战队 B & B+ 队暑假集训模拟赛 day6

E

:::info[Description] 有一个序列 a_1,a_2,\ldots,a_n。一开始所有元素的值都为 0。

每次可以选择一个前缀或者后缀增加 1。具体的：

• 选择前缀 [1,i]：把 a_1,a_2,\ldots,a_i 的值都增加 1，代价为 p_i。
• 选择后缀 [i,n]：把 a_i,a_{i+1},\ldots,a_n 的值都增加 1，代价为 s_i。

:::info[Solution]{open} 记 x_i 表示前缀 [1,i] 操作的次数，y_i 表示后缀 [i,n] 操作的次数。则最后位置 i 的值 a_i=\sum\limits_{j=i}^nx_j+\sum\limits_{j=1}^iy_j。因为题目只要求了 a_i\ge b_i 没有禁止加多，因此考虑记 w_i=a_i-b_i\ge 0 也就是 a_i=b_i+w_i。

考虑相邻两个位置，有 a_i-a_{i+1}=x_i-y_{i+1} 也就是 y_{i+1}+w_i-x_i-w_{i+1}=b_{i+1}-b_i。考虑对这个式子做费用流建模，考虑把 y_{i+1},w_i 看作是从 i 流出去的边，x_i,w_{i+1} 看作是流入 i 的边。具体来说：

先考虑 w_i 的取值。在结点 i 的式子中其的取值为 +w_i，i-1 的式子中其的取值为 -w_i 因此可以直接建立边 i\to i-1，其流量为 w_i。

然后在考虑 x_i 的取值。对 1\le i<n 她只会在结点 i 的式子中以 -x_i 出现，因此考虑从源点 0 出发建一条流向 i 的边，流量为 x_i。起点从源点 0 出发的道理是条件满足 a_1=b_1+w_1 可以推出 a_1=x_1+x_2+\ldots+c_n+y_1 也就是 x_1+x_2+\ldots+x_n+y_1-w_1=b_1，可以看出所有的 x_i 在 0 号结点这里都是正好，因此正好对应从 0 流出到 i 点，流量为 x_i 的边。

同理，y_i 在结点 i-1 的式子中是正号，所以应该从结点 i-1 开始向 n 点连一条流量为 y_i 的边。

总结一下，问题可以被转化为下面的图论模型：

• 对每个结点 i，由 0 号结点向 i 号结点连一条流量为 x_i 费用为 p_i 的边。
• 对每个结点 i，由 i 号结点向 i-1 号结点连一条流量为 w_i 费用为 0 的边。
• 对每个结点 i，由 i-1 号结点向 n 号结点连一条流量为 y_i 费用为 s_i 的边。

记源点 S=0，汇点 T=n，对上图跑 MCMF，答案就是 MCMF 得到的费用。

但是直接建边时间复杂度爆炸了，考虑挖掘图的性质来优化。维护最优费用流每个结点 i 对应的势能函数 q_i。显然费用流最优的时候可以找到一组势能使得每条边 u\to v 都满足 q_u-q_v\le c(u,v)，这里 c(u,v) 表示 <u,v> 这条边的单位费用。

然后对势能做差分，记 z_i=q_{i-1}-q_i。则此时前缀边 0\to i 可以得到 q_0-q_i\le p_i 这个关系式，也就是 \sum\limits_{j=1}^iz_j\le p_i；后缀边 i-1\to n 可以得到 q_{i-1}-q_n\le s_i 也就是 \sum\limits_{j=i}^nz_j\le s_i；免费边 i\to i-1 可以得到 q_i-q_{i-1}\le 0 也就是 z_i\ge 0。

与此同时费用流的最优费用还可以被表示为 \sum\limits_{i=0}^n(b_{i+1}-b_i)q_i=\sum\limits_{i=1}^nb_i(q_{i-1}-q_i)=\sum\limits_{i=1}^nb_iz_i。因此原题也就等价于找到非负整数 z_i 然后最大化 \sum b_iz_i 的值，使得其同时满足 \sum\limits_{j=1}^iz_j\le p_i 和 \sum\limits_{j=i}^nz_j\le s_i。

此时考虑把限制变为单调的。具体来说：

对前缀限制而言，后面更小的 p_j 同样会限制前面，因此记 P_i=\min\limits_{j\ge i}p_j。同样的对后缀记 S_i=\min\limits_{j\le i}s_j。此时可以把 z_i 理解为在位置 i 上放 z_i 个点使得每个点价值都为 b_i。设一共放了 T 个点，从左往右的位置为 r_1\le r_2\le \ldots\le r_T。则此时再维护 L_k=\min\lbrace i\mid P_i\ge k\rbrace,R_k=\max\lbrace i\mid S_i\ge k\rbrace。则此时一定有 r_k\in [L_k,R_{T-k+1}]。为了让答案尽量大因此贪心的希望她取到区间中的最大的 b_i。因此固定区间的总点数 T 时最优值就是 F(T)=\sum\limits_{k=1}^T\max\limits_{i\in[L_k,R_{T-k+1}]}b_i。

然后考虑求出 T 的范围。对 i,i+1 两个位置之间的切口，左边最多放 P_i 个点，右边最多放 S_{i+1} 个点，因此此时必须有 T\le P_i+S_{i+1}。规定 P_0=0,S_{n+1}=0 则最大的合法点数 T_{\max}=\min\limits_{0\le i\le n}P_i+S_{i+1}。

因为费用流是凸函数，因此 F(T) 同样也是凸函数，直接求导 / 差分然后二分求出峰值即可。

问题在于如何快速的计算 F(T)=\sum\limits_{k=1}^T\max\limits_{i\in[L_i,R_{T-k+1}]}b_i。显然此时不能枚举 k=1,2,3,\ldots,T，但是可以注意到 L_k 的值只会变化 O(n) 次。假设 L_k=i 则根据 L_k 的定义可知如果 k\le P_i 则左端点就一定一直不会变化。再设当前 R_{T-k+1}=j，则此时随着 k 的值增大，T-k+1 的值会逐渐减小，则当前右端点保持为 j 的条件就是 T-k+1>S_{j+1} 也就是 k\le T-S_{j+1}。

:::success[Code]

:::

难度：黑+

鲜活指数：6

nfls CSP2026模拟赛6

A

:::info[Description] 请勿将OJ的题目搬到其他地方，如有发现封号处理。在博客写题解的同学，请不要写题目描述。 :::

:::info[Solution]{open} 直接双向搜索即可。 :::

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int n, s, a[20], res;
map<int, int> mp;
inline void dfs(int now, int End, int prod) {
    if (now == End + 1) {
        ++mp[prod];
        return;
    } int inner = a[now];
    for (int i = 1; prod + inner <= s; ++i) {
        dfs(now + 1, End, prod + inner);
        inner *= a[now];
    }
}

inline void dfs2(int now, int End, int prod) {
    if (now == End + 1) {
        auto it = mp.upper_bound(s - prod);
        if (it != mp.begin()) res += prev(it)->second;
        return;
    } int inner = a[now];
    for (int i = 1; prod + inner <= s; ++i) {
        dfs2(now + 1, End, prod + inner);
        inner *= a[now];
    }
}

inline void sol([[maybe_unused]]int __testcase_id) {
    cin >> n >> s;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    dfs(1, n / 2, 0);
    int las = 0;
    for (auto &[x, y] : mp) y += las, las = y;
    dfs2(n / 2 + 1, n, 0);
    cout << res << '\n';
}

} // namespace lowspeed_song

:::

难度：绿

鲜活指数：0

B

:::info[Description] 请勿将OJ的题目搬到其他地方，如有发现封号处理。在博客写题解的同学，请不要写题目描述。 :::

:::info[Solution]{open} 先把树上的距离拆开，得到 \operatorname{dist}(u,v)=\operatorname{dep}(u)+\operatorname{dep}(v)-2\operatorname{dep}(\operatorname{lca}(u,v))。

考虑先求 \mathbb E[\operatorname{dep}(u)] 的值。这个是容易的，枚举 u 的父亲结点 i 转移即可。具体的，有 \mathbb E[\operatorname{dep}(u)]=\sum\limits_{i=1}^{u-1}a_i(b_u+b_i+\mathbb E[\operatorname{dep}(i)])\times\frac{1}{\sum\limits_{i=1}^{u-1}a_i}，然后拿前缀和优化一下转移即可。

然后再求 \mathbb E[\operatorname{dep}(\operatorname{lca}(u,v))] 的值。特判掉 u=v 的情况，然后根据 ARC195E 的结论可知若钦定 u<v，则 \mathbb E[\operatorname{dep}(\operatorname{lca}(u,v))] 的值此时只和 u 有关，和 v 是无关的。具体而言，让 v 向上跳父亲结点，直到满足 v\le u 为止。此时若 v=u 则期望就是 \mathbb E[\operatorname{dep}(u)]，否则 v 的取值在 [1,i) 范围中，问题转化为求 \mathbb E[\operatorname{dep}(\operatorname{lca}(u,i))] 的值，直接向上递归即可。然后这个同样可以线性处理，钦定 u<v 后记 g_u 为答案，则同样可以用前缀和把转移方程优化到线性解决。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int a[N], b[N], E[N], E_lca[N], pre[N];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    E[1] = E_lca[1] = 0, pre[1] = a[1];
    int sum_E = a[1] * b[1] % mod, sum_Elca = 0;
    for (int i = 2; i <= n; ++i) {
        E[i] = (b[i] + sum_E * inversion(pre[i - 1]) % mod) % mod;
        pre[i] = (pre[i - 1] + a[i]) % mod;
        E_lca[i] = (a[i] * E[i] % mod + sum_Elca) % mod * inversion(pre[i]) % mod;
        sum_E = (sum_E + a[i] * (E[i] + b[i]) % mod) % mod;
        sum_Elca = (sum_Elca + a[i] * E_lca[i] % mod) % mod;
    }
    while (q--) {
        int u, v; cin >> u >> v;
        if (u == v) cout << 0 << '\n';
        else cout << (E[u] + E[v] - 2 * E_lca[min(u, v)] % mod + mod) % mod << '\n';
    }
}

} // namespace lowspeed_song

:::

难度：蓝

鲜活指数：7

C

:::info[Description] 请勿将OJ的题目搬到其他地方，如有发现封号处理。在博客写题解的同学，请不要写题目描述。 :::

:::info[Solution]{open}

:::

:::success[Code]

:::

难度：

鲜活指数：

D

:::info[Description] 请勿将OJ的题目搬到其他地方，如有发现封号处理。在博客写题解的同学，请不要写题目描述。 :::

:::info[Solution]{open} 考虑 dp。先不求恰好第几次连通，设 d_{n,k} 表示当前图有 n 个点，且连了 k 次边之后图仍然不连通的概率。有经典公式是设最终连通所需次数为 X 则有 \mathbb E[X]= :::

:::success[Code]

:::

难度：

鲜活指数：

Misc

107. P10992 [蓝桥杯 2023 国 Python A] 最长同类子串

:::info[Description] Link. :::

:::info[Solution]{open} 感觉比较套路。考虑二分答案，设当前二分的答案长度为 x，则先考虑怎么判断两个串是否是相似的。容易想到集合哈希，维护串内相邻两个字符之间间隔的距离，判断这两个东西组成的集合哈希值是否相等即可（这个部分用集合哈希或者多项式哈希都是可以的）。快速维护直接滑动窗口即可。

:::success[Code]

namespace lowspeed_song {

constexpr u64 base = 1333331;

u64 pwr[N];
char s[N], t[N];
int n, m, ne[N], ne2[N], pre[N], pre2[N], buc[N];

inline void init() {
    pwr[0] = 1;
    for (int i = 1; i < N; ++i) pwr[i] = pwr[i - 1] * base;
}

inline int chk(int x) {
    set<u64> se;
    u64 Hash = 0;
    for (int i = 1; i <= x; ++i)
        if (pre[i]) Hash += (i - pre[i]) * pwr[x - i];
    se.emplace(Hash);
    // cerr << "awa " << Hash << ' ' << x << '\n';
    for (int l = 2, r = x + 1; r <= n; ++l, ++r) {
        if (ne[l - 1] <= r - 1) Hash -= (ne[l - 1] - l + 1) * pwr[r - ne[l - 1] - 1];
        Hash = Hash * base;
        if (pre[r] >= l) Hash += r - pre[r];
        se.emplace(Hash);
        // cerr << "qwq " << l << ' ' << r << " : " << Hash << '\n';
    }
    Hash = 0;
    for (int i = 1; i <= x; ++i)
        if (pre2[i]) Hash += (i - pre2[i]) * pwr[x - i];
    // cerr << "Hash = " << Hash << ' ' << x << '\n';
    if (se.count(Hash)) return 1;
    for (int l = 2, r = x + 1; r <= m; ++l, ++r) {
        if (ne2[l - 1] <= r - 1) Hash -= (ne2[l - 1] - l + 1) * pwr[r - ne2[l - 1] - 1];
        Hash *= base;
        if (pre2[r] >= l) Hash += r - pre2[r];
        if (se.count(Hash)) return 1;
    } return 0;
}

inline void sol() {
    scanf("%s%s", s + 1, t + 1);
    n = strlen(s + 1), m = strlen(t + 1);
    for (int i = 1; i <= n; ++i) pre[i] = buc[s[i] - 'a'], buc[s[i] - 'a'] = i;
    memset(buc, 0, sizeof buc);
    for (int i = n; i; --i) ne[i] = buc[s[i] - 'a'], buc[s[i] - 'a'] = i;
    memset(buc, 0, sizeof buc);
    for (int i = 1; i <= m; ++i) pre2[i] = buc[t[i] - 'a'], buc[t[i] - 'a'] = i;
    memset(buc, 0, sizeof buc);
    for (int i = m; i; --i) ne2[i] = buc[t[i] - 'a'], buc[t[i] - 'a'] = i;
    for (int i = 1; i <= n; ++i)
        if (!ne[i]) ne[i] = n + 1;
    for (int i = 1; i <= m; ++i)
        if (!ne2[i]) ne2[i] = m + 1;
    int l = 1, r = min(n, m), best = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        chk(mid) ? (best = mid, l = mid + 1) : (r = mid - 1);
    } cout << best << '\n';
}

} // namespace lowspeed_song

:::

难度：紫-

鲜活指数：4

108. P9523 [JOIST 2022] 复制粘贴 3 / Copy and Paste 3

:::info[Description] Link. :::

:::info[Solution]{open} 考虑区间 dp。设 f_{i,j} 表示让区间 [l,r] 内的字符串正确所需要花费的最小时间，则初始条件显然为 f_{i,j}=A(j-i+1)。转移有下面的几种形式：

• 如果 [x,y]\subseteq[i,j] 且 [x,y] 在 [i,j] 中无交的出现了 k 次，则有转移 f_{i,j}=f_{x,y}+(j-i+1-k(y-x+1))A+B+kC。

考虑先优化一下转移的形式。钦定转移时 j=y 且 [x,y] 是满足 [i,y] 出现了 k 次的最大的位置 i，则转移最终的答案一定和原来的转移完全相同。此时如果不考虑找位置 x 的时间复杂度，其余转移部分的时间复杂度为 O(n^2\log n)。

现在考虑怎么对区间 [i,j] 和出现次数 k 快速找到合法的转移点 x。考虑预处理出 lcp_{i,j} 表示从第 i 个位置开始的后缀和从第 j 个位置开始的后缀的最长公共前缀长度是多少，显然可以 O(n^2) 直接转移。然后再设 pre_{i,len} 表示子串 S[i:i+len-1] 在左边最靠右的不相交出现位置是什么，枚举 p<i 令 v=\min(lcp_{p,i},i-p) 表示位置 p 对所有长度不超过 v 的子串都是合法的前一次出现，因此先让 pre_{i,v}=\max(pre_{i,v},p) 然后再对长度从大到小做后缀最大值就可以 O(1) 时间复杂度找到前一次出现位置。

对当前区间 [i,j] 令 len=j-i+1，从 p=i 开始不断执行 p\leftarrow pre_{p,len}，每跳一次就找到了一个更靠左且不相交的出现位置，假设这个时候一共找到了 k 次那么转移形如 f_{p,j}\leftarrow\min(f_{p,j},f_{i,j}+B+kC+(j-p+1-klen)A)。

:::success[Code]

namespace lowspeed_song {

char s[N];
int lcp[3010][3010], f[3010][3010], pre[3010][3010];

inline void init() {
}

inline void sol() {
    int n; cin >> n;
    scanf("%s", s + 1);
    int A, B, C; cin >> A >> B >> C;
    for (int i = n; i; --i)
        for (int j = n; j > i; --j)
            if (s[i] == s[j]) lcp[i][j] = lcp[i + 1][j + 1] + 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j < i; ++j) pre[i][min(lcp[j][i], i - j)] = max(pre[i][min(lcp[j][i], i - j)], j);
        for (int j = n - 1; j; --j) pre[i][j] = max(pre[i][j], pre[i][j + 1]);
    } 
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n - i + 1; ++j) f[j][j + i - 1] = A * i;
    for (int len = 1; len <= n; ++len)
        for (int i = 1, j = len; j <= n; ++i, ++j) {
            if (len > 1) f[i][j] = min({f[i][j], f[i][j - 1] + A, f[i + 1][j] + A});
            int pos = i, k = 1;
            while (pre[pos][len]) {
                pos = pre[pos][len], ++k;
                f[pos][j] = min(f[pos][j], f[i][j] + B + C * k + A * (j - pos + 1 - k * len));
            }
        }
    cout << f[1][n] << '\n';
}

} // namespace lowspeed_song

:::

难度：紫

鲜活指数：10

109. P7361 「JZOI-1」拜神

:::info[Description] Link. :::

:::info[Solution]{open} 回顾一下后缀数组的一些定义和性质：

• height_{rk_i}\ge height_{rk_{i-1}}-1
• \operatorname{lcp}(sa_i,sa_j)=\min\limits_{k=i+1}^jheight_k
• 序列中不同子串的数量为 \frac{n(n+1)}2-\sum\limits_{i=2}^nheight_i。

问题可以被转化为每次询问区间 [l,r] 中出现至少两次的最长子串长度是多少。容易想到二分答案，设当前二分的答案为 L，则因为一个长度为 L 的子串必须完全位于 [l,r] 区间中，因此其起点只能在 [l,r-L+1] 范围中。设 R=r-L+1 那么 L 合法当且仅存在两个不同的位置 p,q\in[l,R] 满足 \operatorname{lcp}(s[p:r],s[q:r])\ge L。

套路的求出后缀数组 rk,sa 和高度数组 height，对当前二分到的 L 把所有满足 height_i\ge L 的相邻后缀 sa_{i-1},sa_i 连一条边（此时这两个后缀的 lcp 长度至少为 L）。

对原串的每个位置 i 记录 nxt_i 表示最小的位置 j 满足 j>i 且 i,j 在前面建出的图中属于同一个连通块。那么区间 [l,R] 中存在两个属于同一块的位置当且仅当 \min\limits_{k=l}^{R-1}nxt_k\le R。

考虑用数据结构来维护这个结构。对 L 做扫描线，先从大到小扫描所有 L，将所有 height_i=L 的变加入并查集，每个连通块用 set 维护其中的原串位置，每次合并直接启发式合并两个 set 更新其中受影响位置的 nxt，修改的位置直接用可持久化线段树新开一个版本来存储即可。

最后二分 L 的时候查询可以直接在线段树版本 root_L 上查询。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

char s[N];

int root[N];
int lc[M], rc[M], tot;
u16 mi[M];

namespace Suffix_Array {
    int sa[N], rk[N], buc[N], height[N], n, idx;
    struct Node {
        int x[2], buc;
        inline Node() { x[0] = x[1] = buc = 0; }
        inline Node(int a, int b, int c) { x[0] = b, x[1] = a, buc = c; }
    } a[N], b[N];
    inline void sort(int up) {
        for (int i : {0, 1}) {
            memset(buc, 0, sizeof buc);
            for (int j = 1; j <= n; ++j) ++buc[a[j].x[i]];
            for (int j = 1; j <= up; ++j) buc[j] += buc[j - 1];
            for (int j = n; j; --j) b[buc[a[j].x[i]]--] = a[j];
            for (int j = 1; j <= n; ++j) a[j] = b[j];
        }
        int idx = 1;
        rk[a[1].buc] = 1;
        for (int i = 2; i <= n; ++i)
            if (a[i].x[0] == a[i - 1].x[0] && a[i].x[1] == a[i - 1].x[1]) rk[a[i].buc] = idx;
            else rk[a[i].buc] = ++idx;
    }
    inline void build() {
        for (int i = 1; i <= n; ++i) a[i] = Node(s[i], 1, i);
        sort(128);
        for (int i = 1; i < n; i <<= 1) {
            for (int j = 1; j <= n; ++j) a[j] = Node(rk[j], (i + j <= n) ? rk[i + j] : 0, j);
            sort(n);
        } for (int i = 1; i <= n; ++i) sa[rk[i]] = i;
        for (int i = 1; i <= n; ++i)
            if (rk[i] == 1) height[rk[i]] = 0;
            else {
                int p = sa[rk[i] - 1], l = max<int>(0, height[rk[i - 1]] - 1);
                while (s[i + l] == s[p + l]) ++l;
                height[rk[i]] = l;
            }
    }
} using namespace Suffix_Array;

vector<int> e[N];

inline int mdf(int rt, int l, int r, int pos, int val) {
    int nw = ++tot;
    lc[nw] = lc[rt], rc[nw] = rc[rt], mi[nw] = mi[rt];
    if (l == r) return mi[nw] = val, nw;
    int mid = l + r >> 1;
    if (pos <= mid) lc[nw] = mdf(lc[rt], l, mid, pos, val);
    else rc[nw] = mdf(rc[rt], mid + 1, r, pos, val);
    mi[nw] = min(mi[lc[nw]], mi[rc[nw]]);
    return nw;
}

inline int qry(int rt, int l, int r, int ll, int rr) {
    if (!rt) return inf;
    if (ll <= l && r <= rr) return mi[rt];
    int mid = l + r >> 1, res = inf;
    if (ll <= mid) res = qry(lc[rt], l, mid, ll, rr);
    if (mid < rr) res = min(res, qry(rc[rt], mid + 1, r, ll, rr));
    return res;
}

int fa[N];
set<int> se[N];
inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
int tag_idx, tag[N], cp[N];
inline void chg(int pos, int v) {
    if (!tag[pos]) cp[++tag_idx] = pos;
    tag[pos] = v;
}
inline void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return;
    if (se[x].size() < se[y].size()) swap(x, y);
    fa[y] = x;
    for (const int &p : se[y]) {
        auto it = se[x].lower_bound(p);
        if (it != se[x].end()) chg(p, *it);
        if (it != se[x].begin()) chg(*prev(it), p);
        se[x].emplace(p);
    } se[y].clear();
}

inline void sol() {
    int q; cin >> n >> q;
    scanf("%s", s + 1);
    build();
    mi[0] = 64000;
    for (int i = 2; i <= n; ++i)
        if (height[i]) e[height[i]].emplace_back(i);
    for (int i = 1; i <= n; ++i) fa[i] = i, se[i].emplace(i);
    for (int len = n - 1; len; --len) {
        tag_idx = 0;
        for (int &i : e[len]) merge(sa[i - 1], sa[i]);
        root[len] = root[len + 1];
        for (int i = 1; i <= tag_idx; ++i) {
            root[len] = mdf(root[len], 1, n, cp[i], tag[cp[i]]);
            tag[cp[i]] = 0;
        }
    }
    while (q--) {
        int l, r; cin >> l >> r;
        int L = 1, R = r - l + 1, best = 0;
        while (L <= R) {
            int mid = L + R >> 1;
            if (qry(root[mid], 1, n, l, r - mid + 1) <= r - mid + 1) best = mid, L = mid + 1;
            else R = mid - 1;
        } cout << best << '\n';
    }
}

} // namespace lowspeed_song

:::

难度：黑-

鲜活指数：7

110. AT_arc158_d [ARC158D] Equation

:::info[Description] Link. :::

:::info[Solution]{open} 没有人类了。考虑记 F(x,y,z)=(x+y+z)(x^n+y^n+z^n)(x^{2n}+y^{2n}+z^{2n}),G(x,y,z)=x^{3n}+y^{3n}+z^{3n}。注意到 F(x,y,z) 和 G(x,y,z) 的次数只差 1 而且都是齐次式，因此考虑直接任取一组 a,b,c，记 x=ta,y=tb,z=tc。因为 F 的总次数为 3n+1 而 G 的总次数为 3n 因此 F(ta,tb,tc)=t^{3n+1}F(a,b,c),G(ta,tb,tc)=t^{3n}G(a,b,c)。因此只需要满足 t^{3n+1}F(a,b,c)=t^{3n}G(a,b,c) 且 t\neq 0 就可以在等式左右两侧同时约掉 t^{3n} 得到 tF(a,b,c)=G(a,b,c)。因此直接取 t=\frac{G(a,b,c)}{F(a,b,c)} 则 (ta,tb,tc) 就一定能够满足原等式。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

inline void sol() {
    int n, p; cin >> n >> p;
    mt19937 mt(time(0));
    uniform_int_distribution<int> dist(1, p - 1);
    int a[3];
    while (1) {
        a[0] = dist(mt), a[1] = dist(mt), a[2] = dist(mt);
        sort(a, a + 3);
        if (a[0] == a[1] || a[1] == a[2]) continue;
        int x = (a[0] + a[1] + a[2]) % p * (power(a[0], n, p) + power(a[1], n, p) + power(a[2], n, p)) % p * (power(a[0], n + n, p) + power(a[1], n + n, p) + power(a[2], n + n, p) % p) % p, y = (power(a[0], n + n + n, p) + power(a[1], n + n + n, p) + power(a[2], n + n + n, p)) % p, div = y * inversion(x, p) % p;
        if (div) { a[0] = a[0] * div % p, a[1] = a[1] * div % p, a[2] = a[2] * div % p; break; }
    } sort(a, a + 3);
    cout << a[0] << ' ' << a[1] << ' ' << a[2] << '\n';
}

} // namespace lowspeed_song

:::

难度：无法评定

鲜活指数：无法评定

111. P6698 [BalticOI 2020] 病毒 (Day2)

:::info[Description] Link. :::

:::info[Solution]{open} 这个真难吧。。。。。。直接复读题解了

设 f_{x.s,t} 表示从一个基因 x 开始，经过若干次变异最终得到一个 01 串 w 而且满足 AC 自动机一开始处于状态 s，把 w 从左往右放入 AC 自动机中，中途不能经过任何一个匹配到抗体的危险状态，最后自动机停在状态 t，最短的串 w 长度是多少。如果不存在这样的串 w 则记 f_{x,s,t}=+\infin。

为了方便，后面记 go(s,c) 表示在 AC 自动机上从 s 状态出发，沿着 c 字符的方向扩展一步后状态的位置是哪里。

初始条件就是对基因 0,1，如果从 s 状态走过去不会进入危险状态的话，那么就有 f_{c,s,go(s,c)}=1。

然后考虑处理变异规则。假设有规则 a\to b_1b_2\ldots b_k，则考虑固定初始状态 s 设 g_u 表示处理完当前的若干个基因后，停在状态 u 所需要的最短长度。每次加入一个基因 b_i 时直接转移 g'_v\leftarrow\min\limits_u(g_u+f_{b_i,u,v}) 即可。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int idx = 0, fail[N];
struct Node {
    int ne[2], bad;
    inline Node() { ne[0] = ne[1] = bad = 0; }
} tree[102];
struct Info {
    int x;
    vector<int> a;
} rule[102];
int G, n, m, f[52], g[52], h[102][102][52], vis[N];
vector<int> adj[N];

inline void ins() {
    int n, now = 0; cin >> n;
    while (n--) {
        int c; cin >> c;
        if (!tree[now].ne[c]) tree[now].ne[c] = ++idx;
        now = tree[now].ne[c];
    } tree[now].bad = 1;
}

inline void build() {
    queue<int> q;
    for (int i = 0; i < 2; ++i)
        if (tree[0].ne[i]) q.emplace(tree[0].ne[i]);
    while (q.size()) {
        int t = q.front(); q.pop();
        tree[t].bad |= tree[fail[t]].bad;
        for (int i = 0; i < 2; ++i)
            if (tree[t].ne[i]) fail[tree[t].ne[i]] = tree[fail[t]].ne[i], q.emplace(tree[t].ne[i]);
            else tree[t].ne[i] = tree[fail[t]].ne[i];
    }
}

inline int gao(int id) {
    auto &[x, a] = rule[id];
    memset(f, 0, sizeof f), memset(g, 0, sizeof g);
    int ok = 0;
    for (signed i = 0; i <= idx; ++i) {
        for (signed j = 0; j <= idx; ++j) f[j] = inf;
        f[i] = 0;
        for (int &j : a) {
            #pragma GCC unroll 8
            for (signed k = 0; k <= idx; ++k) g[k] = inf;
            #pragma GCC unroll 8
            for (signed k = 0; k <= idx; ++k)
            #pragma GCC unroll 8
                for (int p = 0; p <= idx; ++p)
                    g[p] = min(g[p], f[k] + h[j][k][p]);
            for (signed k = 0; k <= idx; ++k) f[k] = g[k];
        }
            #pragma GCC unroll 8
        for (signed j = 0; j <= idx; ++j)
            if (f[j] < h[x][i][j]) h[x][i][j] = f[j], ok = 1;
    } return ok;
}

inline void sol() {
    memset(h, 0x3f, sizeof h);
    cin >> G >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> rule[i].x;
        int k; cin >> k;
        while (k--) {
            int x; cin >> x;
            rule[i].a.emplace_back(x);
            adj[x].emplace_back(i);
        }
    } while (m--) ins();
    build();
    memset(f, 0x3f, sizeof f);
    for (int i = 0; i <= idx; ++i)
        for (int j = 0; j < 2; ++j)
            if(!tree[i].bad && !tree[tree[i].ne[j]].bad) h[j][i][tree[i].ne[j]] = 1;
    queue<int> q;
    q.emplace(0), q.emplace(1), vis[0] = vis[1] = 1;
    while (q.size()) {
        int t = q.front(); q.pop(), vis[t] = 0;
        for (int &id : adj[t]) if (gao(id) && !vis[rule[id].x]) vis[rule[id].x] = 1, q.emplace(rule[id].x);
    }
    for (int i = 2; i < G; ++i) {
        int res = inf;
        for (int j = 0; j <= idx; ++j) res = min(res, h[i][0][j]);
        if (res < inf / 2) cout << "NO " << res << '\n';
        else cout << "YES\n";
    }
}

} // namespace lowspeed_song

:::

难度：黑

鲜活指数：9

112. CF1286E Fedya the Potter Strikes Back

:::info[Description] Link. :::

:::info[Solution]{open} 太棒了我不会 KMP。

考虑每次只处理新加入字符对答案额外的贡献。设当前处理到的位置为 i，则区间 [l,i] 是合法的当且仅当其是字符串的一个 border。加入新字符后以前的 border 有两种情况：

• 她期待的下一个字符等于当前字符，则继续延长长度。
• 否则，将会永久失效。

考虑类比 KMP 的结构，用 KMP 的失配链维护所有的 border，然后按照下一步期待哪个字符来分类以快速的删除所有失配的 border。因为每个 border 最多会被删除一次，因此均摊一下可得总删除次数为 O(n)。

然后考虑怎么算贡献。每个 border 对应一段区间，其贡献是区间权值最小值。考虑用 map 来对每个最小值 x 维护最小值为 x 的 border 有多少个，然后每次更新操作把所有大于 w_i 的值合并到 w_i 中即可。border 失效时用 ST 表查询其原来区间最小值然后从贡献中删除即可。

:::success[Code]

namespace lowspeed_song {

int lg[N];

inline void init() {
    lg[0] = -1;
    for (int i = 1; i < N; ++i) lg[i] = lg[i >> 1] + 1;
}

inline void out(i128 x) {
    if (x < 10) cout.put(x + '0');
    else out(x / 10), cout.put(x % 10 + '0');
}
inline void write(i128 x) {
    if (x < 0) x = -x, cout.put('-');
    if (!x) cout.put('0');
    else out(x);
}

char s[N];
int st[N][20], pi[N], ne[N][26], sum;
map<int, int> mp;
inline void add(int x, int v) {
    sum += x * v;
    if (!(mp[x] += v)) mp.erase(x);
}
inline void cap(int x) {
    int cnt = 0;
    for (auto it = mp.upper_bound(x); it != mp.end(); it = mp.erase(it))
        cnt += it->second, sum -= it->first * it->second;
    if (cnt) add(x, cnt);
}
inline int qry(int l, int r) {
    int lgx = lg[r - l + 1];
    return min(st[l][lgx], st[r - (1 << lgx) + 1][lgx]);
}

inline void sol() {
    i128 res = 0;
    int n, pre = inf; cin >> n;
    for (int i = 1; i <= n; ++i) {
        char c; int w; cin >> c >> w;
        s[i] = (char)('a' + (c - 'a' + res % 26) % 26), w ^= (int)(res & ((1 << 30) - 1));
        pre = min(pre, st[i][0] = w);
        for (int j = 1; (1 << j) <= i; ++j)
            st[i - (1 << j)][j] = min(st[i - (1 << j)][j - 1], st[i - (1 << (j - 1))][j - 1]);
        if (i > 1) {
            int p = pi[i - 1];
            while (p && s[p + 1] != s[i]) p = pi[p];
            if (s[p + 1] == s[i]) ++p;
            pi[i] = p;
            for (int j = 0; j < 26; ++j) ne[i][j] = ne[p][j];
            if (p) ne[i][s[p + 1] - 'a'] = p;
            for (int j = 0; j < 26; ++j) if (j != s[i] - 'a')
                for (int k = ne[i - 1][j]; k; k = ne[k][j]) add(qry(i - k, i - 1), -1);
            if (s[i] == s[1]) add(w, 1);
            cap(w);
        } res += sum + pre, write(res), cout << '\n';
    }
}

} // namespace lowspeed_song

:::

难度：黑

鲜活指数：9

113. P5770 [JSOI2016] 无界单词

:::info[Description] Link. :::

:::info[Solution]{open} 无界单词其实就是没有真 border 的字符串。第一问考虑 dp，设 f_i 表示长度为 i 的无界单词的数量，则转移考虑正难则反做，总共有 2^i 个字符串，对每一个有 border 的字符串设其最短 border 的长度为 j，则这个长度为 j 的串一定是无界单词，剩下的 i-2j 个字符可以随便填写，转移就是 f_i=2^i-\sum\limits_{j=1}^{\lfloor\frac i2\rfloor}f_j2^{i-2j}。直接做就是 O(n^2) 的（可以优化到 O(n)）。

upd：第一问可以做到 O(\log^3n)。

:::success[Code]

namespace lowspeed_song {

int n;
char s[N];
u64 f[N], g[N], pwr[N];

inline void init() {
    pwr[0] = 1;
    for (int i = 1; i <= 63; ++i) pwr[i] = pwr[i - 1] * 2;
    for (int i = 1; i <= 64; ++i) {
        f[i] = pwr[i];
        for (int j = 1; j + j <= i; ++j) f[i] -= f[j] * pwr[i - j - j];
    }
}

inline int same(int l1, int r1, int l2) {
    for (int i = 0; i <= r1 - l1; ++i)
        if (s[l1 + i] != s[l2 + i]) return 0;
    return 1;
}

inline int good(int len) {
    for (int i = 1; i <= len / 2; ++i)
        if (same(1, i, len - i + 1)) return 0;
    return 1;
}

inline u64 calc(int len) {
    for (int i = 1; i <= n; ++i) {
        if (i <= len) g[i] = good(i);
        else {
            g[i] = pwr[i - len];
            for (int j = 1; j <= i / 2; ++j)
                if (j <= i - len) g[i] -= g[j] * pwr[i - j - max(len, j)];
                else if (same(1, len - i + j, i - j + 1)) g[i] -= g[j];
        }
    } return g[n];
}

inline void sol() {
    u64 k; cin >> n >> k;
    cout << f[n] << '\n';
    for (int i = 1; i <= n; ++i) {
        s[i] = 'a';
        u64 cnt = calc(i);
        if (cnt < k) k -= cnt, cout.put('b'), s[i] = 'b';
        else cout.put('a'), s[i] = 'a';
    } cout << '\n';
}

} // namespace lowspeed_song

:::

难度：青

鲜活指数：5

114. QOJ10333 Divide Digit String

:::info[Description] Link. :::

:::info[Solution]{open} 先考虑 k=1 的情况。此时记 L=\lfloor\frac nm\rfloor 则如果 n\bmod m\neq 0 容易证明最优划分一定是有 n\bmod m 段的长度是 L+1 其余段长度为 L，否则所有段的长度都是 L。记这个最长的长度为 len 则答案必然在 s 的 n-len+1 个长度为 len 的子串中选取。

把长度为 len 的子串按照字典序排序然后二分答案，设当前二分到的子串为 X，则考虑贪心，如果当前位置往后 L 个字符组成的长度为 L 的子串 \le X 那么就贪心的选长度为 L 的子串（当然如果长度为 L 的子串选完了的话就不能选了），否则选长度为 L-1 的子串。贪心的正确性是容易证明的。

子串字典序排序可以 SA 或者 二分 + Hash，因此 k=1 时时间复杂度为 O(n\log^2n)。

然后考虑 k>1。此时容易证明答案字符串肯定长度只有 1，因此考虑直接枚举答案串是 x=1,2,3,\ldots,9，然后能做到第 k 大 \le x 等价于至少有 m-k+1 个位置的值 \le x 并且选出 m-k+1 个位置后其余段最多只有 k-1 段，直接做就能做到 O(n)。

:::success[Code]

namespace lowspeed_song {

const u64 base = 13331;
u64 h[N], bit[N];

inline void init() {
    bit[0] = 1;
    for (int i = 1; i < N; ++i) bit[i] = bit[i - 1] * base;
}

char s[N];

int m, k;

namespace Suffix_Array {
    int sa[N], rk[N], buc[N], height[N], n, idx;
    struct Node {
        int x[2], buc;
        inline Node() { x[0] = x[1] = buc = 0; }
        inline Node(int a, int b, int c) { x[0] = b, x[1] = a, buc = c; }
    } a[N], b[N];
    inline void sort(int up) {
        for (int i : {0, 1}) {
            for (int j = 0; j <= up + 1; ++j) buc[j] = 0;
            for (int j = 1; j <= n; ++j) ++buc[a[j].x[i]];
            for (int j = 1; j <= up; ++j) buc[j] += buc[j - 1];
            for (int j = n; j; --j) b[buc[a[j].x[i]]--] = a[j];
            for (int j = 1; j <= n; ++j) a[j] = b[j];
        }
        int idx = 1;
        rk[a[1].buc] = 1;
        for (int i = 2; i <= n; ++i)
            if (a[i].x[0] == a[i - 1].x[0] && a[i].x[1] == a[i - 1].x[1]) rk[a[i].buc] = idx;
            else rk[a[i].buc] = ++idx;
    }
    inline void build() {
        for (int i = 1; i <= n; ++i) a[i] = Node(s[i], 1, i);
        sort(128);
        for (int i = 1; i < n; i <<= 1) {
            for (int j = 1; j <= n; ++j) a[j] = Node(rk[j], (i + j <= n) ? rk[i + j] : 0, j);
            sort(n);
        } for (int i = 1; i <= n; ++i) sa[rk[i]] = i;
        for (int i = 1; i <= n; ++i)
            if (rk[i] == 1) height[rk[i]] = 0;
            else {
                int p = sa[rk[i] - 1], l = max<int>(0, height[rk[i - 1]] - 1);
                while (s[i + l] == s[p + l]) ++l;
                height[rk[i]] = l;
            }
    }
} using namespace Suffix_Array;

inline u64 get(int l, int r) {
    return h[r] - h[l - 1] * bit[r - l + 1];
}

int buc_[N];

inline void sol() {
    cin >> n >> m >> k;
    scanf("%s", s + 1);
    if (k > 1) {
        for (int i = 1; i <= 9; ++i) {
            for (int j = 0; j <= n; ++j) buc_[j] = 0;
            int l = 1, r = n, cnt = m - k + 1;
            while (l <= r && s[l] - '0' <= i) ++l, --cnt;
            while (l <= r && s[r] - '0' <= i) --r, --cnt;
            int lx = 0;
            for (int j = l; j <= r; ++j)
                if (s[j] - '0' > i) ++buc_[lx], lx = 0;
                else ++lx;
            int used = 0;
            for (int j = n; j; --j)
                while (cnt > 0 && buc_[j]) --buc_[j], cnt -= j, ++used;
            if (used < k - 1 && cnt <= 0) {
                cout << i << '\n';
                return;
            }
        } throw;
    } else {
        build();
        for (int i = 1; i <= n; ++i) h[i] = h[i - 1] * base + s[i];
        int len = (n + m - 1) / m, v1 = n - m * (len - 1), v2 = m - v1;
        vector<int> vec;
        for (int i = 1; i <= n; ++i)
            if (sa[i] + len - 1 <= n) vec.emplace_back(sa[i]);
        function<bool(int, int)> comp = [&](int l, int r) {
            if (get(l, l + len - 1) == get(r, r + len - 1)) return true;
            return rk[l] < rk[r];
        };
        function<int(int)> chk = [&](int o) {
            int pos = 1, x = v1, y = v2;
            while (x || y) {
                if (x && comp(pos, o)) --x, pos += len;
                else if (y) --y, pos += len - 1;
                else return 0;
            } return 1;
        };
        // cerr << "???\n";
        int l = 0, r = vec.size() - 1, best = -1;
        while (l <= r) {
            int mid = l + r >> 1;
            chk(vec[mid]) ? (best = mid, r = mid - 1) : (l = mid + 1);
        }
        for (int i = vec[best]; i < vec[best] + len; ++i) cout << s[i];
        cout << '\n';
    }
}

} // namespace lowspeed_song

:::

难度：紫-

鲜活指数：5

115. P11284 「GFOI Round 2」Strings

:::info[Description] Link. :::

:::info[Solution]{open} 题目的条件可以看作是存在整数 l 满足 3l\le k 且前 2l 个数构成回文串，因此问题可以看作是统计长度不超过 n 的序列中存在一个足够短的偶数长度回文前缀的序列数量。

考虑 dp，设 f_i 表示长度为 2i 且最短偶回文串恰好为整个串的序列的数量。长度为 2i 的回文串一共有 m^i 个，但是其中某些回文串可能有更短的偶回文前缀。假设最短回文前缀的长度为 2j，则序列的前 2j 位有 f_j 种填写方案，为了将其补全成长度为 2i 的回文串，中间还有 i-2j 个位置可以随便填，因此该类的不合法方案数就是 f_jm^{i-2j} 种。

把上面东西合起来写可以得到递推式 f_i=m^i-\sum\limits_{j=1}^{\lfloor\frac i2\rfloor}f_jm^{i-2j}。

然后考虑枚举最短回文前缀的长度 2l。序列的总长度为 k 时因为要求 3l\le k，而前 2l 位有 f_l 种填法，后 k-2l 位随便填，方案数就是 f_lm^{k-2l}。

因此总的答案就是 \sum\limits_{i=1}^{\lfloor\frac n3\rfloor}f_i\sum\limits_{k=3i}^nm^{k-2i}，直接算时间复杂度是 O(n^2) 的，考虑优化。答案内层是一个等比数列求和的形式，因此还可以被表示为 \sum\limits_{i=1}^{\lfloor\frac n3\rfloor}f_i\frac{m^i-m^{n-2i+1}}{1-m} 的形式，也就是 \frac1{1-m}(\sum\limits_{i=1}^{\lfloor\frac n3\rfloor}f_im^i-\sum\limits_{i=1}^{\lfloor\frac n3\rfloor}f_im^{n-2i+1})，求和部分可以优化到线性时间复杂度。

（我想到这里就不会了）

记 S(n,t)=\sum\limits_{i=1}^nf_im^{ti}，则答案可以表示为 \frac{S(\lfloor\frac n3\rfloor,1)-m^{n+1}S(\lfloor\frac n3\rfloor,-2)}{1-m} 的形式。

先考虑怎么优化递推的时间复杂度。已知 f_l=m^l-\sum\limits_{i=1}^{\lfloor\frac l2\rfloor}f_im^{l-2i}，则把递推公式直接带入到 S(*,*) 中，可得 S(n,t)=\sum\limits_{l=1}^n(m^l-\sum\limits_{i=1}^{\lfloor\frac l2\rfloor}f_im^{l-2i})m^{tl}=\sum\limits_{i=1}^nm^lm^{tl}-\sum\limits_{l=1}^n\sum\limits_{i=1}^{\lfloor\frac l2\rfloor}f_im^{l-2i}m^{tl}=m^{(t+1)l}-\sum\limits_{l=1}^n\sum\limits_{i=1}^{\lfloor\frac l2\rfloor}f_im^{(t+1)l-2i}。

现在考虑怎么优化算 \sum\limits_{l=1}^n\sum\limits_{i=1}^{\lfloor\frac l2\rfloor}f_im^{(t+1)l-2i} 的值。考虑交换求和顺序，可得 \sum\limits_{i=1}^{\lfloor\frac n2\rfloor}\sum\limits_{l=2i}^nf_im^{(t+1)l-2i}=\sum\limits_{i=1}^{\lfloor\frac n2\rfloor}f_im^{-2i}\sum\limits_{l=2i}^nm^{(t+1)l}。换元记 q=m^{t+1}，则内层求和可以看作是 \sum\limits_{l=2i}^nq^l=\frac{q^{2i}-q^{n+1}}{1-q}，因此双重和式的值为 \sum\limits_{i=1}^{\lfloor\frac n2\rfloor}f_im^{-2i}\frac{q^{2i}-q^{n+1}}{1-q}=\frac{1}{1-q}(\sum\limits_{i=1}^{\lfloor\frac n2\rfloor}f_im^{-2i}q^{2i}-q^{n+1}\sum\limits_{i=1}^{\lfloor\frac n2\rfloor}f_im^{-2i})。

然后考虑分别算两个求和的值。第一个求和中，m^{-2i}q^{2i}=m^{-2i}(m^{t+1})^{2i}=m^{2ti}，因此第一项可以变为 \sum\limits_{i=1}^{\lfloor\frac n2\rfloor}f_im^{2ti}=S(\lfloor\frac n2\rfloor,2t)；第二个求和中 \sum\limits_{i=1}^{\lfloor\frac n2\rfloor}f_im^{-2i}=S(\lfloor\frac n2\rfloor,-2)。又因为 q^{n+1}=m^{(n+1)(t+1)},\sum\limits_{l=1}^nm^{(t+1)l}=\frac{m^{t+1}-m^{(n+1)(t+1)}}{1-m^{t+1}}，因此可得整个双重和式的值为 S(n,t)=\frac{m^{t+1}-m^{(n+1)(t+1)}}{1-m^{t+1}}-\frac{S(\lfloor\frac n2\rfloor,2t)-m^{(n+1)(t+1)}S(\lfloor\frac n2\rfloor,-2)}{1-m^{t+1}}，边界情况是 S(0,t)=0。

考虑分析一下时间复杂度。看上去很爆炸，但是考虑使用记忆化搜索来优化，设递归深度为 dep 则每次递归 n 的值都会除以 2，因此有 dep\sim O(\log n)。而在第 d 层可能出现的不同 t 值的状态也只有 O(d) 级别，因此总状态数就是 \sum\limits_{d=0}^{O(\log n)}O(d)=O(\log^2n) 的。每次递归内层还需要做快速幂和记忆化（需要开 map 维护）等操作，因此总时间复杂度可以近似看作是 O(\log^3n) 级别的。

需要单独处理 m^{t+1}\equiv 1\pmod{10^9+7} 的情况，这个时候不能直接套上面的公式除过去，需要做一些特殊的处理。

递推过程中可能出问题的地方有下面三类：\frac 1m,\frac1{1-m},\frac1{1-m^{t+1}}，考虑什么时候会出现问题：

第一类显然当且仅当 m\equiv 0\pmod{10^9+7} 时会出问题，第二类显然当且仅当 m\equiv 1\pmod{10^9+7} 时会出问题，第三类比较困难，可以想到如果 m\equiv 1\pmod{10^9+7} 或 m\equiv -1\pmod{10^9+7} 时会出问题。下面可以证明会出问题的情况只有这两类，即证明除了 m\equiv \pm 1\pmod{10^9+7} 不存在其余 m 满足 m^{t+1}\equiv 1\pmod{10^9+7}。考虑上述做法一开始递归的时候只会调用 S(L,1) 和 S(L,-2) 两个值，在递归的过程中会从 S(n,t) 开始不停的调用 S(\lfloor\frac n2\rfloor,2t) 和 S(\lfloor\frac n2\rfloor,-2) 两个函数，因此所有可能取到的 t 只有 t=2^j(j\in\mathbb N) 和 t=-2^j(j\in\mathbb N_+) 两类情况。因为递归每次回将 n 除以 2，而题目中保证 n\le 10^{18} 因此这里可能出现的 j 不会超过单 \log 级别也就是 60。

现在假设 m\not\equiv 0\pmod{10^9+7}，设 m 在模 10^9+7 意义下的乘法群中的阶是 d（也就是最小的满足 m^d\equiv1\pmod{10^9+7} 的正整数 d），根据费马小定理可知 d\mid 1000000006，而 1000000006 的质因数分解形式为 2\times 500000003，因此 d 的所有可能取值只有 1,2,500000003,1000000006 四种。

当 d=1 时显然只能取 m\equiv 1\pmod{10^9+7}，当 d=2 时有 m^2\equiv 1\pmod{10^9+7}\land m\not\equiv 1\pmod{10^9+7}，因此只能取 m\equiv -1\pmod{10^9+7}。

比较复杂的情况是 d 的后两个取值。如果有 m^{t+1}\equiv 1\pmod{10^9+7}，则必有 d\mid t+1。当 d 是 500000003 或者 1000000006 时都必然有 500000003\mid t+1。考虑对 t 的值做分类讨论：

如果 t=2^j，则必须满足 2^j+1\equiv0\pmod{500000003} 即 2^j\equiv-1\pmod{500000003}；如果 t=-2^j 则必须满足 1-2^j\equiv0\pmod{500000003} 即 2^j\equiv 1\pmod{500000003}。因为 \operatorname{ord}_{500000003}(2)=500000002（500000002=2\times 41^2\times 148721 对三个质因子 q\in\lbrace 2,41,148721\rbrace 验证都有 2^{500000002/q}\not\equiv 1\pmod{500000003}），因此此时必须满足 500000002\mid j。而 2^j\equiv -1\pmod{500000003} 必须满足 j\equiv 250000001\pmod{500000002}。而因为在题目限制下递归满足 j\le60，因此不需要处理后两种情况。

现在考虑特判这三个 corner case：

• 然后考虑算答案。当 m\equiv -1 时固定 l 值后剩余部分的贡献为 \sum\limits_{k=3l}^n(-1)^{k-2l}=\sum\limits_{k=3l}^n(-1)^k，只有 l\equiv n\pmod 2 时上式的值不为 0。此时考虑进一步分类讨论：
  • 如果 2\mid n 则只需要枚举偶数 l=2i，最终的答案可以表示为 \lfloor\frac L2\rfloor-G(\lfloor\frac L2\rfloor) 的形式，其中 L=\lfloor\frac n3\rfloor。
  • 如果 2\nmid n 则只需要枚举奇数 l=2i+1，最终的答案可以表示为 \lfloor\frac{L+1}2\rfloor-G(\lfloor\frac{L-1}2\rfloor) 的形式，其中 L=\lfloor\frac n3\rfloor。

• 很显然 G(n) 可直接递归 O(\log n) 时间复杂度求解，因此该部分算答案的总时间复杂度也是 O(\log n) 的。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int n, m;
map<pair<int, int>, int> mp;

inline int S(int n, int t) {
    if (!n) return 0;
    if (mp.count({n, t})) return mp[{n, t}];
    int a = power(m, ((t + 1) % (mod - 1) + mod - 1) % (mod - 1), mod), b = power(m, ((i128)(n + 1) * (t + 1) % (mod - 1) + mod - 1) % (mod - 1), mod);
    return mp[{n, t}] = inversion(mod + 1 - a) * (a - b - S(n / 2, t * 2) + mod * 2 + b * S(n / 2, -2) % mod) % mod;
}

inline int sumF(int n) {
    if (!n) return 0;
    return (mod + mod - sumF(n >> 1) - (n + 1) * i2 % mod) % mod;
}

inline int calc(int n) {
    if (n & 1) return ((n / 3 + 1) / 2 % mod + mod - sumF(n / 2)) % mod;
    return (n / 3 % mod + mod - sumF(n / 2)) % mod;
}

inline void sol() {
    cin >> n >> m; m %= mod;
    if (!m) cout << 0 << '\n';
    else if (m == 1) cout << (n - 2) % mod << '\n';
    else if (m == mod - 1) cout << calc(n) << '\n';
    else {
        mp.clear();
        cout << inversion((1 - m + mod) % mod) * (S(n / 3, 1) - power(m, n + 1, mod) * S(n / 3, -2) % mod + mod) % mod << '\n';
    }
}

} // namespace lowspeed_song

:::

难度：彩-

鲜活指数：-15

116. P10896 移言丁真：Unavoided linyue

:::info[Description] Link. :::

:::info[Solution]{open} 套路的考虑把括号串放到二维平面上考虑，记 ( 的权值为 1，) 的权值为 -1，权值数组为 w_i，前缀和数组为 S_i，则括号串可以看作是一条过 (i,S_i) 点的折线。则此时路径最低点到起点的纵坐标高度差就是无法匹配的右括号数量，路径最低点到终点的纵坐标高度差就是无法匹配的左括号数量。记上面两个值分别为 x,y，则这个串的权值（即能匹配的括号数）就是 \frac{l_i-x-y}2。

因此一个括号串可以用一个三元组 (a_i,b_i,c_i) 来表示，其中 a_i 表示无法匹配的右括号数量，b_i 表示无法匹配的左括号数量，c_i 表示已经确定可以匹配的权值。则显然原串中左括号数量是 b_i+c_i，右括号数量是 a_i+c_i。

接下来考虑这些括号串已经确定时，怎么排列才能让最终的权值最小。假设拼接后整条路径的最低点在第 p 个括号串中，对其他括号串而言，若其 a_i>b_i 则说明这个串整体在折线上向下走，应该放在第 p 个串的左边，否则这个串整体在折线上往上走，应该放在第 p 个串右边。此时第 p 个串对起点终点到全局最低点的高度差的和贡献了 a_p+b_p 的代价，其余串则贡献了 |a_i-b_i| 的代价。因此这样对答案的贡献就是 a_p+b_p+\sum\limits_{i\neq p}|a_i-b_i|=\sum\limits_i|a_i-b_i|-2\min(a_p,b_p)。为了让最终的权值尽量小，容易想到让 \min(a_p,b_p) 值最大的 p 作为中间的串 p，因此确定所有串后最小的权值就是 \frac{\sum\limits_il_i-\sum\limits_i|a_i-b_i|}2-\max\limits_i\min(a_i,b_i)。记 L_i=b_i+c_i,R_i=a_i+c_i 即第 i 个串的左右括号数量，则权值还可以被表示为 \sum\limits_i\min(L_i,R_i)-\max\limits_i\min(a_i,b_i) 的形式。

考虑分别计算两个部分的期望值。对长度为 l 的随机括号串，枚举其中的左括号数 j 可得 \mathbb E[\min(L,R)]=\frac1{2^l}\sum\limits_{j=0}^l\min(j,l-j)\binom lj。因为所有 l_i 的总和为 n，因此对每个串直接枚举 j 的时间复杂度还是线性的。

然后考虑算 \mathbb E[\max\limits_i\min(a_i,b_i)] 的值。这个部分相对比较困难。设 t_i=\min(a_i,b_i) 则有 \mathbb E[\max\limits_i t_i]=\sum\limits_{k\ge 1}P(\max\limits_i t_i\ge k)=\sum\limits_{k\ge 1}(1-\prod\limits_iP(t_i<k))。现在问题在于如何快速计算一个长度为 l 个随机括号串中 t=\min(a_i,b_i) 各个取值分布的概率情况。

考虑继续在折线图上考虑问题。把原来的折线路径整体向上平移 a_i 个单位，则此时路径从高度 a_i 出发，在高度 b_i 结束，整条路径任意时刻都不在 x 轴的下方且至少碰到过一次 x 轴。因此 t=\min(a_i,b_i) 就可以看作是平移后起点和终点高度的较小值。设 h=\lfloor\frac l2\rfloor，固定 t=r 相当于起点和终点中至少有一个高度为 r 且另一个高度至少为 r。这个东西可以直接枚举另一个高度然后用反射容斥来算折线数量，省略中间的 dirty work，最后的答案就是：

记上面的东西值为 F(l,r)。

因为总共存在 2^l 个长度为 l 的括号串，所以 P(t<k)=\frac{\sum\limits_{r=0}^{k-1}F(l,r)}{2^l}。枚举 k 的过程中顺带维护 F(l,*) 的前缀和即可线性得到当前字符串的所有 P(t<k) 的值。

记 G_k=\prod\limits_i P(t_i<k)，则因为各个括号串之间互相独立，因此 G_k 就是所有 t_i<k 的概率即 G_k=P(\max\limits_i t_i<k)。因此 \mathbb E[\max\limits_i t_i]=\sum\limits_{k\ge 1}(1-G_k)。具体实现过程中维护数组 G_k 的值，初始所有 G_k 的值都为 1，处理一个长度为 l 的串时枚举 k\le\lfloor\frac k2\rfloor 维护 F(l,r) 的前缀和，从而求出 P(t<k) 然后乘入 G_k 中即可。

:::success[Code]

namespace lowspeed_song {

int fac[N], inv[N], ifac[N], pwr[N], ipwr[N];

inline void init() {
    fac[0] = inv[0] = ifac[0] = 1;
    fac[1] = inv[1] = ifac[1] = 1;
    for (int i = 2; i < N; ++i) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        ifac[i] = ifac[i - 1] * inv[i] % mod;
    }
    pwr[0] = ipwr[0] = 1;
    for (int i = 1; i < N; ++i) {
        pwr[i] = pwr[i - 1] * 2 % mod;
        ipwr[i] = ipwr[i - 1] * i2 % mod;
    }
}

inline int binom(int a, int b) {
    if (b < 0 || a < b) return 0;
    return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}

int f[N], a[N];

inline void sol() {
    int n = 0, m, res = 0, mx = 0; cin >> m;
    for (int i = 1; i <= m; ++i) cin >> a[i], n += a[i], mx = max(mx, a[i] / 2);
    for (int i = 0; i < N; ++i) f[i] = 1;
    for (int i = 1; i <= m; ++i) {
        res = (res + a[i] * i2 % mod + mod - a[i] * binom(a[i] - 1, (a[i] - 1) / 2) % mod * ipwr[a[i]] % mod) % mod;
        int pre = 0;
        for (int j = 1; j <= a[i] / 2; ++j) {
            pre = (pre + ((a[i] & 1) ? 2 * binom(a[i], a[i] / 2 - j + 1) % mod : binom(a[i] + 1, a[i] / 2 - j + 1))) % mod;
            f[j] = f[j] * pre % mod * ipwr[a[i]] % mod;
        }
    } for (int i = 1; i <= mx; ++i) res = (res + mod - 1 + f[i]) % mod;
    cout << res << '\n';
}

} // namespace lowspeed_song

:::

难度：黑

鲜活指数：10

117. CF1762E Tree Sum

:::info[Description] Link. :::

:::info[Solution]{open} 容易发现 n 是奇数的时候答案一定为 0。

然后如果树的形态确定，则固定树的根为 1 号结点，一条边的权值可以不被其切出的子树内点的数量唯一确定。具体的，设没被切出的部分有 l 个点，则对这一侧所有的点都必须满足其和其相邻的点的边的权值的乘积必须为 -1。现在把这一侧 l 个点的 l 个等式全部相乘，则一条完全在这一侧内的边的贡献被全部抵消，因此左侧最后只剩下当前边的权值，而等式右侧则是 (-1)^l。因此当前边的权值就是 (-1)^l。

也就是说，边权之和一侧点的数量的奇偶性有关，和树的具体形态无关。而且当 n 为偶数的时候每个树都可以恰好对应一种合法的给边赋权值方式。

:::success[Code]

namespace lowspeed_song {

int fac[N], inv[N], ifac[N], pwr[N], ipwr[N];

inline void init() {
    fac[0] = inv[0] = ifac[0] = 1;
    fac[1] = inv[1] = ifac[1] = 1;
    for (int i = 2; i < N; ++i) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        ifac[i] = ifac[i - 1] * inv[i] % mod;
    }
    pwr[0] = ipwr[0] = 1;
    for (int i = 1; i < N; ++i) {
        pwr[i] = pwr[i - 1] * 2 % mod;
        ipwr[i] = ipwr[i - 1] * i2 % mod;
    }
}

inline int binom(int a, int b) {
    if (b < 0 || a < b) return 0;
    return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}

inline void sol() {
    int n; cin >> n;
    if (n & 1) { cout << 0 << '\n'; return; }
    int res = 0;
    for (int i = 1; i < n; ++i) {
        int val = binom(n - 2, i - 1) * power(i, i - 1, mod) % mod * power(n - i, n - i - 1, mod) % mod;
        if (i & 1) res = (res + mod - val) % mod;
        else res = (res + val) % mod;
    } cout << res << '\n';
}

} // namespace lowspeed_song

:::

难度：紫

鲜活指数：8

118. P14368 [JOISC 2018] 修行 / Asceticism

:::info[Description] Link. :::

:::info[Solution]{open} 问题可以看作是问有多少个 1\sim n 的排列满足其可以被恰好划分为 k 个极长上升子段。

设答案为 f_k 则根据 Worpitzky 恒等式 m^n=\sum\limits_{i=1}^mf_k\binom{n+m-i}n，即固定一个有 k-1 个下降的排列，对应值域为 1\sim m 的序列数为 \binom{n+m-k}n。

:::success[Code]

namespace lowspeed_song {

int fac[N], inv[N], ifac[N], pwr[N], ipwr[N];

inline void init() {
    fac[0] = inv[0] = ifac[0] = 1;
    fac[1] = inv[1] = ifac[1] = 1;
    for (int i = 2; i < N; ++i) {
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        ifac[i] = ifac[i - 1] * inv[i] % mod;
    }
    pwr[0] = ipwr[0] = 1;
    for (int i = 1; i < N; ++i) {
        pwr[i] = pwr[i - 1] * 2 % mod;
        ipwr[i] = ipwr[i - 1] * i2 % mod;
    }
}

inline int binom(int a, int b) {
    if (b < 0 || a < b) return 0;
    return fac[a] * ifac[b] % mod * ifac[a - b] % mod;
}

inline void sol() {
    int n, k; cin >> n >> k;
    int res = 0;
    for (int i = 0; i <= k; ++i) {
        int val = binom(n + 1, i) * power(k - i, n, mod) % mod;
        if (i & 1) res = (res + mod - val) % mod;
        else res = (res + val) % mod;
    } cout << res << '\n';
}

} // namespace lowspeed_song

:::

难度：紫-

鲜活指数：2

119. CF1548C The Three Little Pigs

:::info[Description] Link. :::

:::info[Solution]{open} 题目中给的式子相当于是 \sum\limits_{i=0}^n\binom{3i}x。直接算肯定是不行的，容易想到把这个东西用 GF 或者 dp 来求，这里给出一个 dp 求的做法：

设 f_{i,j}=\sum\limits_{k=0}^n\binom{3k+j}i（j\in\lbrace 0,1,2\rbrace），则要求的式子就是 f_{x,0}。考虑对着这个和式做一些手脚让这个 dp 是可以递推的：

假设存在某个 j\in[l,r] 满足 a_j>x 则根据前面的结论 v_{j,x} 是 S 类点。此时存在不会被割掉的边 v_{j,x}\to P，因此 P 点也是 S 类点。所以此时 P\to T 这条边一定被割掉了，容量为 c。

没有房子的高度 >x

此时所有的 j\in[l,r] 都不满足 a_j>x 则根据前面的结论 v_{j,x} 都是 T 类点，因此 P 点也同样是 T 类点，P\to T 这条边一定不会被割掉。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

namespace Flow {

int S, T, dep[N], cur[N];
struct edg {
    int e, f, o;
    edg(int a, int b) { e = a, f = b, o = 0; }
} ; vector<edg> adj[N];
inline void link(int s, int e, int f) {
    adj[s].push_back({edg(e, f)}), adj[e].push_back(edg(s, 0));
    int s1 = adj[s].size() - 1, s2 = adj[e].size() - 1;
    adj[s][s1].o = s2, adj[e][s2].o = s1;
}
inline bool bfs() {
    queue<int> q;
    memset(dep, 0, sizeof dep), memset(cur, 0, sizeof cur);
    dep[S] = 1, q.emplace(S);
    while (q.size()) {
        int p = q.front(); q.pop();
        for (auto &[r, f, _] : adj[p]) if (f && !dep[r]) {
            dep[r] = dep[p] + 1, q.emplace(r);
            if (r == T) return 1;
        }
    } return 0;
}
inline int dfs(int p, int f) {
    if (p == T) return f;
    int s = 0;
    for (int &i = cur[p]; i < adj[p].size(); ++i) {
        if (!f) break;
        int q = adj[p][i].e, fx = adj[p][i].f;
        if (fx && dep[p] + 1 == dep[q]) {
            int delta = dfs(q, min(f, fx));
            if (!delta) continue;
            adj[p][i].f -= delta, adj[q][adj[p][i].o].f += delta;
            f -= delta, s += delta;
        }
    }
    return s ? s : (dep[p] = 0);
}
inline int dinic() {
    int s = 0;
    while (bfs()) s += dfs(S, inf);
    return s;
}

} // namespace Flow

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, h, m; cin >> n >> h >> m;
    Flow::S = N - 1, Flow::T = N - 2;
    function<int(int, int)> get = [&](int i, int j) { return (i - 1) * (h + 2) + j; };
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= h + 1; ++j)
            Flow::link(get(i, j), get(i, j + 1), h * h - (j - 1) * (j - 1));
    for (int i = 1; i <= n; ++i) {
        Flow::link(Flow::S, get(i, 1), inf);
        Flow::link(get(i, h + 2), Flow::T, inf);
    }
    int idx = n * (h + 2);
    while (m--) {
        int l, r, x, c; cin >> l >> r >> x >> c;
        if (x == h) continue;
        Flow::link(++idx, Flow::T, c);
        for (int i = l; i <= r; ++i) Flow::link(get(i, x + 2), idx, inf);
    } cout << n * h * h - Flow::dinic() << '\n';
}

} // namespace lowspeed_song

:::

难度：紫

鲜活指数：7

131. P11531 [THUPC 2025 初赛] 检查站

:::info[Description] Link. :::

:::info[Solution]{open} 套路的考虑最小割建模求解。把每个分部点 i 拆成入点 in_i 和出点 out_i，然后从入点向出点连一条容量为 1 的边。割掉这条边就代表选择这个分部设立检查站，花费代价为 1。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

namespace Flow {

int S, T, dep[N], cur[N];
struct edg {
    int e, f, o;
    edg(int a, int b) { e = a, f = b, o = 0; }
} ; vector<edg> adj[N];
inline void link(int s, int e, int f) {
    adj[s].push_back({edg(e, f)}), adj[e].push_back(edg(s, 0));
    int s1 = adj[s].size() - 1, s2 = adj[e].size() - 1;
    adj[s][s1].o = s2, adj[e][s2].o = s1;
}
inline bool bfs() {
    queue<int> q;
    memset(dep, 0, sizeof dep), memset(cur, 0, sizeof cur);
    dep[S] = 1, q.emplace(S);
    while (q.size()) {
        int p = q.front(); q.pop();
        for (auto &[r, f, _] : adj[p]) if (f && !dep[r]) {
            dep[r] = dep[p] + 1, q.emplace(r);
            if (r == T) return 1;
        }
    } return 0;
}
inline int dfs(int p, int f) {
    if (p == T) return f;
    int s = 0;
    for (int &i = cur[p]; i < adj[p].size(); ++i) {
        if (!f) break;
        int q = adj[p][i].e, fx = adj[p][i].f;
        if (fx && dep[p] + 1 == dep[q]) {
            int delta = dfs(q, min(f, fx));
            if (!delta) continue;
            adj[p][i].f -= delta, adj[q][adj[p][i].o].f += delta;
            f -= delta, s += delta;
        }
    }
    return s ? s : (dep[p] = 0);
}
inline int dinic() {
    int s = 0;
    while (bfs()) s += dfs(S, inf);
    return s;
}

} // namespace Flow


inline void sol([[maybe_unused]]int __testcase_id) {
    int n, m, c; cin >> n >> m >> c;
    Flow::S = 1, Flow::T = n;
    for (int i = n + 1; i <= n + c; ++i) Flow::link(i, i + c, 1);
    for (int i = 1; i <= c; ++i) { int t; cin >> t; }
    for (int i = 1; i <= m; ++i) {
        int a, b, r; cin >> a >> b >> r;
        Flow::link(a, r + n, inf), Flow::link(n + c + r, b, inf);
    } cout << Flow::dinic() << '\n';
}

} // namespace lowspeed_song

:::

难度：紫-

鲜活指数：4

132. CF1061E Politics

:::info[Description] Link. :::

:::info[Solution]{open} 先把子树限制拆分成若干个互相独立的块，则一个块只有一个限制条件。此时对每个树都可以把所有点恰好分割到若干个块内，并知道每个块内必须恰好选多少个点。然后考虑一个城市 i，如果其在第一个树中属于块 x，第二个树中属于块 y。则选城市 i 相当于第一个树的块 x 用掉一个名额，第二个树的块 y 用掉一个名额。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

namespace MCMF {

int S, T, hhh[N], e[N], f[N], ne[N], w[N], idxx, q[N], d[N], pre[N], incf[N], st[N];
inline void ae(int a, int b, int c, int d) {
    e[idxx] = b, w[idxx] = d, f[idxx] = c, ne[idxx] = hhh[a], hhh[a] = idxx++;
    e[idxx] = a, w[idxx] = -d, f[idxx] = 0, ne[idxx] = hhh[b], hhh[b] = idxx++;
}
inline int spfa() {
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = inf;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = 0;
        for (int i = hhh[t]; ~i; i = ne[i]) {
            int v = e[i];
            if (f[i] && d[v] > d[t] + w[i]) {
                d[v] = d[t] + w[i];
                pre[v] = i, incf[v] = min(incf[t], f[i]);
                if (!st[v]) {
                    q[tt++] = v;
                    if (tt == N) tt = 0;
                    st[v] = 1;
                }
            }
        }
    }
    return incf[T] > 0;
}
inline void ek(int &F, int &C) {
    F = C = 0;
    while (spfa()) {
        int tt = incf[T];
        F += tt, C += tt * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1]) f[pre[i]] -= tt, f[pre[i] ^ 1] += tt;
    }
}
}

vector<int> adj[N], adj2[N];
int n, r1, r2, a[N], req[N], req2[N], bel[N], bel2[N], need[N], need2[N];
inline void dfs(int u, int fa, int las, vector<int> adj[N], int req[N], int bel[N], int need[N]) {
    if (~req[u]) {
        if (~las) need[las] -= req[u];
        las = u;
    } bel[u] = las;
    for (int &v : adj[u]) if (v != fa) dfs(v, u, las, adj, req, bel, need);
}
inline int build(vector<int> adj[N], int rt, int req[N], int bel[N], int need[N]) {
    for (int i = 0; i <= n + 1; ++i) bel[i] = -1, need[i] = 0;
    for (int i = 1; i <= n; ++i) if (~req[i]) need[i] = req[i];
    dfs(rt, 0, -1, adj, req, bel, need);
    for (int i = 1; i <= n; ++i)
        if (need[i] < 0 && ~req[i]) return 0;
    return 1;
}
inline void sol([[maybe_unused]]int __testcase_id) {
    memset(MCMF::hhh, -1, sizeof MCMF::hhh);
    cin >> n >> r1 >> r2;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b;
        adj[a].emplace_back(b), adj[b].emplace_back(a);
    } for (int i = 1; i < n; ++i) {
        int a, b; cin >> a >> b;
        adj2[a].emplace_back(b), adj2[b].emplace_back(a);
    }
    memset(req, -1, sizeof req);
    memset(req2, -1, sizeof req2);
    int q; cin >> q;
    while (q--) {
        int k, x; cin >> k >> x;
        req[k] = x;
    } cin >> q;
    while (q--) {
        int k, x; cin >> k >> x;
        req2[k] = x;
    }
    if (req[r1] != req2[r2]) cout << -1 << '\n';
    else if (!build(adj, r1, req, bel, need)) cout << -1 << '\n';
    else if (!build(adj2, r2, req2, bel2, need2)) cout << -1 << '\n';
    else {
        MCMF::S = 0, MCMF::T = n << 1 | 1;
        for (int i = 1; i <= n; ++i)
            if (~req[i]) MCMF::ae(MCMF::S, i, need[i], 0);
        for (int i = 1; i <= n; ++i)
            if (~req2[i]) MCMF::ae(n + i, MCMF::T, need2[i], 0);
        for (int i = 1; i <= n; ++i)
            MCMF::ae(bel[i], bel2[i] + n, 1, -a[i]);
        int F, C; MCMF::ek(F, C);
        cout << ((F != req[r1]) ? -1 : -C) << '\n';
    }
}

} // namespace lowspeed_song

:::

难度：紫-

鲜活指数：5

133. CF2068K Amusement Park Rides

:::info[Description] Link. :::

:::info[Solution]{open} 相同的 a_i 对应到开放时刻集合是相同的，因此直接合并相同 a_i 即可。

设不同的值为 p_1,p_2,\ldots,p_m，出现次数为 c_1,c_2,\ldots.c_m。对 i 而言，其可以选择的时间是 p_i,2p_i,3p_i,\ldots，因此可以把问题看作是一个二分图匹配，左边是每一种 p_i，右边是每一个可以使用的时间 t。如果 p_i\mid t 说明 i 类项目可以被安排在时间 t 上，直接在左部点中的 p_i 和右部点中的 t 之间连一条流量为 1 的边。然后从源点 S 向左部点 i 连一条流量为 c_i 的边，右部点 t 向汇点 T 连一条流量为 1 的边即可。

一个简单的想法是直接二分答案时刻为 t 然后对每个 t 建出网络流图跑 dinic 验证流量是否满流，但是时间复杂度不太能接受。考虑进一步优化，维护集合 mp_t 表示由多少个种类的项目需要尝试时间 t。一开始每个 p_i 的第一个可以尝试的时间就是 p_i，因此在 mp_{p_i} 集合中加入项目 i。之后每次取出 mp 中最小的可用时间 t 建立一个新的时间点，然后把 mp_t 集合中的所有项目类边连向这个时间点，在原来的残量网络上直接跑 dinic 即可。

因为一次只会新增一个时间点，而且其到汇点 T 的边的容量为 1，因此最大流也最多只会增加 1。如果加入该时间点后最大流成功的增加了 1 则说明时间 t 是有用的，对所有 i\in mp_t 继续考虑其下一个倍数 p_i+t，然后把这些点扔到 mp_{p_i+t} 集合里即可。如果没有变化则说明增广失败，不需要继续生成其后面的倍数。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

namespace Flow {

int S, T, dep[N], cur[N];
struct edg {
    int e, f, o;
    edg(int a, int b) { e = a, f = b, o = 0; }
} ; vector<edg> adj[N];
inline void link(int s, int e, int f) {
    adj[s].push_back({edg(e, f)}), adj[e].push_back(edg(s, 0));
    int s1 = adj[s].size() - 1, s2 = adj[e].size() - 1;
    adj[s][s1].o = s2, adj[e][s2].o = s1;
}
inline bool bfs() {
    queue<int> q;
    memset(dep, 0, sizeof dep), memset(cur, 0, sizeof cur);
    dep[S] = 1, q.emplace(S);
    while (q.size()) {
        int p = q.front(); q.pop();
        for (auto &[r, f, _] : adj[p]) if (f && !dep[r]) {
            dep[r] = dep[p] + 1, q.emplace(r);
            if (r == T) return 1;
        }
    } return 0;
}
inline int dfs(int p, int f) {
    if (p == T) return f;
    int s = 0;
    for (int &i = cur[p]; i < adj[p].size(); ++i) {
        if (!f) break;
        int q = adj[p][i].e, fx = adj[p][i].f;
        if (fx && dep[p] + 1 == dep[q]) {
            int delta = dfs(q, min(f, fx));
            if (!delta) continue;
            adj[p][i].f -= delta, adj[q][adj[p][i].o].f += delta;
            f -= delta, s += delta;
        }
    }
    return s ? s : (dep[p] = 0);
}
inline int dinic() {
    int s = 0;
    while (bfs()) s += dfs(S, inf);
    return s;
}

} // namespace Flow

int id[N];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n; cin >> n;
    map<int, int> cnt;
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        ++cnt[x];
    }
    vector<int> p, c;
    for (auto &[x, y] : cnt) p.emplace_back(x), c.emplace_back(y);
    Flow::S = 0, Flow::T = 1;
    int idx = 2;
    for (int i = 0; i < p.size(); ++i) id[i] = idx++, Flow::link(Flow::S, id[i], c[i]);
    map<int, vector<int>> mp;
    for (int i = 0; i < p.size(); ++i) mp[p[i]].emplace_back(i);
    int flow = 0, res = 0;
    while (flow < n) {
        auto [t, v] = *mp.begin();
        mp.erase(mp.begin());
        int u = idx++;
        for (int &i : v) Flow::link(id[i], u, 1);
        Flow::link(u, Flow::T, 1);
        if (Flow::dinic()) {
            ++flow;
            for (int &i : v) mp[t + p[i]].emplace_back(i);
        } res = t;
    } cout << res << '\n';
    for (int i = 0; i <= idx; ++i) Flow::adj[i].clear();
}

} // namespace lowspeed_song

:::

难度：紫

鲜活指数：6

134. CF1525F Goblins And Gnomes

:::info[Description] Link. :::

:::info[Solution]{open} 套路的考虑把每个点拆成左部点和右部点，对原图的边 u\to v 连一条二分图边，即从左部点 u 连边向右部点 v。设二分图最大匹配大小为 M 则 DAG 的最小路径覆盖就是 n-M。也就是说至少需要 n-M 个哥布林才能用若干条互不相交的路径把所有点全部走完。因此第 i 轮有 i 个哥布林时如果想要活下来就必须满足 i<n-M 即 i+M<n。

然后考虑封锁一个点对答案的影响。如果操作 +u 封锁 u 点的所有出边，相当于把二分图的左部点 u 从图中删除；如果操作 -u 封锁 u 点的所有入边相当于把二分图的右部点 u 从图中删除。很显然删除一个二分图结点后，最大匹配数要么不变要么减少 1。

由 Konig 定理可知二分图最大匹配大小等于最小电覆盖大小，因此如果删除最小点覆盖终点任意一个点，那么剩下的点覆盖大小最多为 M-1 即新的最大匹配最多为 M-1。因此如果最大匹配满足 M>0 则一定可以找到一个点使得删除她后最大匹配变为 M-1。考虑求出这样的一个删点序列，因为 n 很小所以考虑直接暴力的尝试删除每个左部点 / 右部点然后重新跑最大匹配即可。记这个处理出的操作序列为 op_0,op_1,op_2,\ldots,op_M。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int f[55][55], pre[55][55], zx[55], x[55], y[55], banL[55], banR[55], mat[55], used[55], mp[55][55], n, m, k;

inline int dfs(int u) {
    for (int i = 1; i <= n; ++i) {
        if (!mp[u][i] || banR[i] || used[i]) continue;
        used[i] = 1;
        if (!mat[i] || dfs(mat[i])) return mat[i] = u, 1;
    } return 0;
}

inline int calc() {
    memset(mat, 0, sizeof mat);
    int res = 0;
    for (int i = 1; i <= n; ++i)
        if (!banL[i]) memset(used, 0, sizeof used), res += dfs(i);
    return res;
}

vector<int> adj[N];


inline void sol([[maybe_unused]]int __testcase_id) {
    cin >> n >> m >> k;
    while (m--) {
        int a, b; cin >> a >> b;
        adj[a].emplace_back(b), mp[a][b] = 1;
    } for (int i = 1; i <= k; ++i) cin >> x[i] >> y[i];
    vector<int> op;
    int M = calc();
    for (int i = M; i; --i) {
        for (int j = 1; j <= n; ++j) {
            if (!banL[j]) {
                banL[j] = 1;
                if (calc() < i) { op.emplace_back(j); break; }
                banL[j] = 0;
            } if (!banR[j]) {
                banR[j] = 1;
                if (calc() < i) { op.emplace_back(-j); break; }
                banR[j] = 0;
            }
        }
    }
    // cerr << "!!!\n";
    memset(f, -0x3f, sizeof f);
    memset(pre, -1, sizeof pre);
    f[0][0] = 0;
    for (int i = 1; i <= k; ++i)
        for (int j = 0; j <= M; ++j) {
            for (int jj = j; jj <= M; ++jj) {
                if (i + M - jj >= n) continue;
                int w = max<int>(0, x[i] - (jj - j) * y[i]);
                if (f[i][jj] < f[i - 1][j] + w) f[i][jj] = f[i - 1][j] + w, pre[i][jj] = j;
            }
        }
    // cerr << "???\n";
    zx[k] = max_element(f[k], f[k] + M + 1) - f[k];
    for (int i = k; i; --i) zx[i - 1] = pre[i][zx[i]];
    vector<int> res;
    for (int i = 1; i <= k; ++i) {
        for (int j = zx[i - 1]; j < zx[i]; ++j) res.emplace_back(op[j]);
        res.emplace_back(0);
    } cout << res.size() << '\n';
    for (int &i : res) cout << i << ' ';
    cout << '\n';
}

} // namespace lowspeed_song

:::

难度：紫+

鲜活指数：7

135. CF1766F MCF

:::info[Description] Link. :::

:::info[Solution]{open} 题目要求对每条边 i 都满足其流量 f_i 和容量 c_i 的奇偶性相同。容易想到对 c_i 是计数的边先提前流 1 的流量，这样所有边的流量限制就都是偶数，然后一次流 2 的流量即可。因此行啊都给所有容量都整体除以 2 然后每次流 1 的流量变成正常的最小费用可行流问题。

考虑怎么处理提前流 1 的情况。维护数组 e_i 表示 i 点的固定奇数流入流量减去 i 点的固定奇数流出流量的值。则因为中间的点 i 需要满足流量守恒即 e_i+2(网络流流入-网络流流出)=0，对奇偶性分析可得若有 2\nmid e_i 则必然无解。

但是 1,n 两个点不需要满足流量守恒，因此她们的差额可以自由调整。如果 e_1 是奇数则令 e_1 减少 1，e_n 增加 1。此时所有的 e_i 就都是偶数。

为了处理奇数添加的额外流量信息，考虑搞超级源汇点 S,T，对一个中部点 i 而言，如果 e_i>0 则需要额外流出 \frac{e_i}2 的流量，因此连一条 S\to i 流量为 \frac{e_i}2 费用为 -\infin 的边；否则需要额外流入 -\frac{e_i}2 的流量，连一条 i\to T 流量为 -\frac{e_i}2 费用为 -\infin 的边即可。

然后因为没有限制图的流量，因此还需要额外从 S 点连向 1 点流量为 +\infin 费用为 0 的边和一条从 n 点连向 T 点流量为 +\infin 费用为 0 的边以自由决定真正的 1\to n 的流量大小。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

namespace MCMF {
    int S, T, hhh[N], e[N], f[N], ne[N], idxx, q[N], pre[N], incf[N], st[N];
    int w[N], d[N];
    inline int ae(int a, int b, int c, int cost) {
        int id = idxx;
        e[idxx] = b, w[idxx] = cost, f[idxx] = c, ne[idxx] = hhh[a], hhh[a] = idxx++;
        e[idxx] = a, w[idxx] = -cost, f[idxx] = 0, ne[idxx] = hhh[b], hhh[b] = idxx++;
        return id;
    }
    inline int spfa() {
        int hh = 0, tt = 1;
        fill(d, d + N, inf);
        memset(incf, 0, sizeof incf);
        q[0] = S, d[S] = 0, incf[S] = inf, st[S] = 1;
        while (hh != tt) {
            int t = q[hh++];
            if (hh == N) hh = 0;
            st[t] = 0;
            for (int i = hhh[t]; ~i; i = ne[i]) {
                int v = e[i];
                if (f[i] && d[v] > d[t] + w[i]) {
                    d[v] = d[t] + w[i];
                    pre[v] = i, incf[v] = min(incf[t], f[i]);
                    if (!st[v]) {
                        q[tt++] = v;
                        if (tt == N) tt = 0;
                        st[v] = 1;
                    }
                }
            }
        }
        return incf[T] > 0;
    }
    inline void ek() {
        while (spfa()) {
            if (d[T] > 0) break;
            int flow = incf[T];
            for (int i = T; i != S; i = e[pre[i] ^ 1]) f[pre[i]] -= flow, f[pre[i] ^ 1] += flow;
        }
    }
    inline void init() { memset(hhh, -1, sizeof hhh), idxx = 0; }
}

int c[N], id[N], e[N];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, m; cin >> n >> m;
    MCMF::init();
    for (int i = 0; i < m; ++i) {
        int x, y, w;
        cin >> x >> y >> c[i] >> w;
        if (c[i] & 1) ++e[x], --e[y];
        id[i] = MCMF::ae(x, y, c[i] >> 1, 2 * w);
    }
    if (e[1] & 1) ++e[1], --e[n];
    MCMF::S = N - 1, MCMF::T = N - 2;
    vector<int> vec;
    for (int i = 1; i <= n; ++i) {
        if (e[i] & 1) { cout << "Impossible\n"; return; }
        int x = abs(e[i]) / 2;
        if (e[i] < 0) vec.emplace_back(MCMF::ae(MCMF::S, i, x, -1e9));
        else if (e[i] > 0) vec.emplace_back(MCMF::ae(i, MCMF::T, x, -1e9));
    }
    MCMF::ae(MCMF::S, 1, inf, 0), MCMF::ae(n, MCMF::T, inf, 0), MCMF::ek();
    for (int x : vec) if (MCMF::f[x]) { cout << "Impossible\n"; return; }
    cout << "Possible\n";
    for (int i = 0; i < m; ++i) cout << c[i] - 2 * MCMF::f[id[i]] << ' ';
    cout << '\n';
}

} // namespace lowspeed_song

:::

难度：紫+

鲜活指数：5

136. CF708D Incorrect Flow

:::info[Description] Link. :::

:::info[Solution]{open} 好玩的来了。

考虑对于一条 u\to v 的边，其初始给定的容量为 c，流量为 f，则需要分类讨论 c 和 f 之间的大小关系：

f\le c

此时当前的容量是合法的，有下面的几种操作方式：

• 减少流量：每减少 1 就需要让 f 减少 1，花费 1 的代价。本质可以看作是撤销原来一单位的 u\to v 流量，也就是让费用流沿着反方向 v\to u 走一单位。边的容量为 f，费用为 1。
• 增加流量，但是不超过 c：每增加 1 就需要让 f 增加 1，花费 1 的代价。u\to v 的边容量为 c-f 费用为 1。
• 增加流量且超过 c：容量和费用都需要增加 1，因此花费 2 的代价。u\to v 的边容量为 +\infin 费用为 2。

f>c

这条边初始就不合法，因此需要先花费 f-c 的代价平衡容量和流量，然后再进行操作。同样需要分类讨论：

• 首先需要把前 f-c 单位的流量退流，连一条 v\to u 容量为 f-c 费用为 0 的边，然后提前增加 f-c 的代价即可。
• 然后如果要继续退流，则每单位的代价为 1，连一条 v\to u 容量为 c 费用为 1 的边即可。
• 如果要增加流量，则每单位的代价为 2，连一条 u\to v 容量为 +\infin 费用为 2 的边即可。

然后还需要考虑流量不守恒的问题。记 d_i 表示 i 点当前的出流减去当前的入流是多少。则对于一条边 u\to v 而言，初始先更新 d_u\leftarrow d_u+f,d_v\leftarrow d_v-f。处理完后如果 d_i<0 则说明这个点流进来的流量太多了，因此从超级源点 S 向 i 点连一条容量为 -d_i 费用为 0 的边即可；如果 d_i>0 则说明这个点流出的流量太多了，因此从 i 点向超级汇点 T 连一条容量为 d_i 费用为 0 的边即可。

因为 1 号点和 n 号点不要求流量守恒，所以额外加一条从 n 号结点连向 1 号结点的流量为 +\infin 费用为 0 的边即可。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

namespace MCMF {

int S, T, hhh[N], e[N], f[N], ne[N], w[N], idxx, q[N], d[N], pre[N], incf[N], st[N];
inline void ae(int a, int b, int c, int d) {
    e[idxx] = b, w[idxx] = d, f[idxx] = c, ne[idxx] = hhh[a], hhh[a] = idxx++;
    e[idxx] = a, w[idxx] = -d, f[idxx] = 0, ne[idxx] = hhh[b], hhh[b] = idxx++;
}
inline int spfa() {
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = inf;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = 0;
        for (int i = hhh[t]; ~i; i = ne[i]) {
            int v = e[i];
            if (f[i] && d[v] > d[t] + w[i]) {
                d[v] = d[t] + w[i];
                pre[v] = i, incf[v] = min(incf[t], f[i]);
                if (!st[v]) {
                    q[tt++] = v;
                    if (tt == N) tt = 0;
                    st[v] = 1;
                }
            }
        }
    }
    return incf[T] > 0;
}
inline void ek(int &F, int &C) {
    F = C = 0;
    while (spfa()) {
        int tt = incf[T];
        F += tt, C += tt * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1]) f[pre[i]] -= tt, f[pre[i] ^ 1] += tt;
    }
}
}

int d[N];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, m; cin >> n >> m;
    memset(MCMF::hhh, -1, sizeof MCMF::hhh);
    int res = 0;
    while (m--) {
        int u, v, c, f; cin >> u >> v >> c >> f, d[u] += f, d[v] -= f;
        if (f <= c) MCMF::ae(v, u, f, 1), MCMF::ae(u, v, c - f, 1), MCMF::ae(u, v, inf, 2);
        else res += f - c, MCMF::ae(v, u, f - c, 0), MCMF::ae(v, u, c, 1), MCMF::ae(u, v, inf, 2);
    } MCMF::ae(n, 1, inf, 0), MCMF::S = n + 1, MCMF::T = n + 2;
    for (int i = 1; i <= n; ++i)
        if (d[i] > 0) MCMF::ae(i, MCMF::T, d[i], 0);
        else if (d[i] < 0) MCMF::ae(MCMF::S, i, -d[i], 0);
    int F, C; MCMF::ek(F, C);
    cout << res + C << '\n';
}

} // namespace lowspeed_song

:::

难度：黑-

鲜活指数：8

137. CF843E Maximum Flow

:::info[Description] Link :::

:::info[Solution]{open} 特别神秘的题目。考虑最大流的残量网络。设从源点 S 从残量网络中能到达的点集为 S 类点，其余点位 T 类点。因为当前流是最大流所以 T 点必然是 T 类点。

考虑最小割建模。对一条原边 u\to v，如果 g=0 则必有 f=0。因为容量为正，因此正向的残量为 c-f>0。因此如果有 u\in S 则必有 v\in S。此时必然不能出现 u\in S,v\in T。为了禁止这种割法在最小割图中建立一条 u\to v，容量为 +\infin 的边即可。

如果 g=1 则必有 f>0。残量网络中一定存在一个容量为 f 的反向便 v\to u 因此此时不能出现 v\in S,u\in T。为了禁止这种割法在最小割图中建立一条 u\to v 的容量为 +\infin 的边即可。而此时如果有 u\in S,v\in T 则残量网络中正向残量必须为 0，因此此时必然有 c=f 即这条边必然是满流边。因此还需要额外建立一条 u\to v 容量为 1 的边，这样最小割每割掉一条这样的边就对应了一条满流变，因此最小割的大小就是最少的满流边的数量。

对着这个最小割图跑一遍 dinic 得到该图的残量网络，然后还可以得到最小割两侧的点集 S,T。考虑怎么具体构造出每条边的流量。

对 g=0 的边直接设该边的流量为 0 即可。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

// 最小费用可行流
namespace MF {

int S, T, hhh[N], e[N], f[N], ne[N], idxx, q[N], dep[N], cur[N];
inline void init() { memset(hhh, -1, sizeof hhh), idxx = 0; }
inline int ae(int a, int b, int c) {
    int id = idxx;
    e[idxx] = b, f[idxx] = c, ne[idxx] = hhh[a], hhh[a] = idxx++;
    e[idxx] = a, f[idxx] = 0, ne[idxx] = hhh[b], hhh[b] = idxx++;
    return id;
}
inline int bfs() {
    int hh = 0, tt = 0;
    memset(dep, -1, sizeof dep);
    q[tt++] = S, dep[S] = 0;
    while (hh < tt) {
        int u = q[hh++];
        for (int i = hhh[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (f[i] && !~dep[v]) dep[v] = dep[u] + 1, q[tt++] = v;
        }
    }
    return dep[T] != -1;
}
inline int dfs(int u, int lim) {
    if (u == T) return lim;
    for (int &i = cur[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (f[i] && dep[v] == dep[u] + 1) {
            int x = dfs(v, min(lim, f[i]));
            if (x) {
                f[i] -= x, f[i ^ 1] += x;
                return x;
            }
        }
    } return 0;
}

inline int dinic(int s, int t) {
    S = s, T = t;
    int res = 0, x;
    while (bfs()) {
        memcpy(cur, hhh, sizeof hhh);
        while ((x = dfs(S, inf))) res += x;
    }
    return res;
}
inline void reach(int u, int *vis) {
    vis[u] = 1;
    for (int i = hhh[u]; ~i; i = ne[i])
        if (f[i] && !vis[e[i]]) reach(e[i], vis);
}
}

int d[N], u[N], v[N], g[N], id[N], vis[N];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, m, s, t; cin >> n >> m >> s >> t; MF::init();
    for (int i = 1; i <= m; ++i) {
        cin >> u[i] >> v[i] >> g[i];
        if (!g[i]) MF::ae(u[i], v[i], inf);
        else MF::ae(u[i], v[i], 1), MF::ae(v[i], u[i], inf);
    }
    int res = MF::dinic(s, t);
    memset(vis, 0, sizeof vis);
    MF::reach(s, vis), MF::init();
    memset(d, 0, sizeof d);
    int S = n + 1, T = n + 2;
    MF::ae(t, s, inf);
    for (int i = 1; i <= m; ++i) if (g[i])
        id[i] = MF::ae(u[i], v[i], inf), ++d[u[i]], --d[v[i]];
    int need = 0;
    for (int i = 1; i <= n; ++i)
        if (d[i] > 0) MF::ae(i, T, d[i]), need += d[i];
        else if (d[i] < 0) MF::ae(S, i, -d[i]);
    int F = MF::dinic(S, T);
    cout << res << '\n';
    for (int i = 1; i <= m; ++i)
        if (!g[i]) cout << 0 << ' ' << 1 << '\n';
        else cout << MF::f[id[i] ^ 1] + 1 << ' ' << (vis[u[i]] && !vis[v[i]] ? MF::f[id[i] ^ 1] + 1 : MF::f[id[i] ^ 1] + 2) << '\n';
}

} // namespace lowspeed_song

:::

难度：黑

鲜活指数：8

138. AT_agc038_f [AGC038F] Two Permutations

:::info[Description] Link. :::

:::info[Solution]{open} 套路的在置换环的角度下考虑。把 p 这个排列看作是若干个置换环，则对一个长度大于 1 的环如哦 A 想要保持为排列则要么整个环全都取 A_i=i 要么全都取 A_i=P_i。容易证明不存在第三种情况。q 排列也是同理的。

因此可以看作是给每个置换环设一个布尔变量。对 p 排列而言定义 x_C 布尔变量：若 C 环中所有元素都取的 A_i=i 则记 x_C=1，否则记 x_C=0。对 q 排列的定义和对 p 排列的相反，若 C 环中所有元素都取得 A_i=i 则 y_C=0，否则 y_C=1。

最大化 A_i\neq B_i 的数量等价于最小化 A_i=B_i 的数量。因此考虑枚举所有的位置 i 考虑其什么时候满足 A_i=B_i。设 x 是 i 所在的 p 环变量，y 是 j 所在的 q 环变量，则可以直接分类讨论：

• 若 P_i=Q_i=i 则不管怎样都只能有 A_i=B_i=i。
• 若 P_i=i,Q_i\neq i 则此时 A_i 的值永远只能是 i，B_i=i 当且仅当 Q 环不动也就是 y=0。因此此时 A_i=B_i 当且仅当 y=0。产生一个一元费用 c_{y,0}=1，连边 y\to T，边的容量为 1。
• 若 P_i\neq i,Q_i=i 则情况和前面的正好相反，此时产生一元费用 c_{x,1}=1，连边 S\to x，边的容量为 1。
• 然后考虑复杂的二元关系。如果 P_i\neq Q_i 而且有 P_i\neq i,Q_i\neq i 则如果想要让 A_i=B_i 必须满足两边都取到 i 也就是 x=1,y=0。因此费用表中只有 c_{1,0}=1。因为 c_{1,0} 可以用反向边来表示，因此连一条 y\to x，容量为 1 的边即可。
• 最后剩下 P_i=Q_i\neq i 的情况。此时 (x,y)=(1,0) 或者 (x,y)=(0,1) 都是可以产生贡献的 (x,y) 组。费用表中有 c_{0,1}=c_{1,0}=1，因此直接连边 x\to y 和 y\to x，两条边的容量都是 1 即可。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

namespace Flow {

int S, T, dep[N], cur[N];
struct edg {
    int e, f, o;
    edg(int a, int b) { e = a, f = b, o = 0; }
} ; vector<edg> adj[N];
inline void link(int s, int e, int f) {
    adj[s].push_back({edg(e, f)}), adj[e].push_back(edg(s, 0));
    int s1 = adj[s].size() - 1, s2 = adj[e].size() - 1;
    adj[s][s1].o = s2, adj[e][s2].o = s1;
}
inline bool bfs() {
    queue<int> q;
    memset(dep, 0, sizeof dep), memset(cur, 0, sizeof cur);
    dep[S] = 1, q.emplace(S);
    while (q.size()) {
        int p = q.front(); q.pop();
        for (auto &[r, f, _] : adj[p]) if (f && !dep[r]) {
            dep[r] = dep[p] + 1, q.emplace(r);
            if (r == T) return 1;
        }
    } return 0;
}
inline int dfs(int p, int f) {
    if (p == T) return f;
    int s = 0;
    for (int &i = cur[p]; i < adj[p].size(); ++i) {
        if (!f) break;
        int q = adj[p][i].e, fx = adj[p][i].f;
        if (fx && dep[p] + 1 == dep[q]) {
            int delta = dfs(q, min(f, fx));
            if (!delta) continue;
            adj[p][i].f -= delta, adj[q][adj[p][i].o].f += delta;
            f -= delta, s += delta;
        }
    }
    return s ? s : (dep[p] = 0);
}
inline int dinic() {
    int s = 0;
    while (bfs()) s += dfs(S, inf);
    return s;
}

} // namespace Flow

int a[N], b[N], p[N], q[N], pid[N], qid[N], idx;

inline void sol([[maybe_unused]]int __testcase_id) {
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], ++a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i], ++b[i];
    int res = n;
    for (int i = 1; i <= n; ++i) {
        if (!p[i]) {
            p[i] = i;
            for (int j = a[i]; j != i; j = a[j]) p[j] = i;
            if (a[i] != i) pid[i] = ++idx;
        } if (!q[i]) {
            q[i] = i;
            for (int j = b[i]; j != i; j = b[j]) q[j] = i;
            if (b[i] != i) qid[i] = ++idx;
        }
    } Flow::S = N - 1, Flow::T = N - 2;
    for (int i = 1; i <= n; ++i) {
        if (a[i] == b[i] && a[i] == i) --res;
        else if (a[i] == i && b[i] != i) Flow::link(Flow::S, qid[q[i]], 1);
        else if (a[i] != i && b[i] == i) Flow::link(pid[p[i]], Flow::T, 1);
        else if (a[i] == b[i]) Flow::link(pid[p[i]], qid[q[i]], 1), Flow::link(qid[q[i]], pid[p[i]], 1);
        else Flow::link(pid[p[i]], qid[q[i]], 1);
    } // cerr << "!!!\n";
    cout << res - Flow::dinic() << '\n';
}

} // namespace lowspeed_song

:::

难度：黑-

鲜活指数：8

139. P11613 [PA 2016] 覆盖 / Pokrycia

:::info[Description] Link. :::

:::info[Solution]{open} 是人类能做的题吗，，，感谢 gpt 姐姐帮我理解这个题。

题目就是统计有多少张 n 个点的，最小点覆盖恰好为 k 的有标号简单无向图，答案对 2 取模。

有经典结论：任意 n 个点的无向图中最小点覆盖大小和最大独立集大小的和为 n。因此问题等价于统计最大独立及大小恰好为 n-k 的图的数量 \bmod\ 2。

考虑从 \bmod\ 2 这个条件入手。如果能够把满足条件的图两两配对，而且每一对中两个图的最大独立集大小相同，那么这一对点的贡献在 \bmod\ 2 意义下就是 0，可以直接忽略。

先考虑原图中的 u,v 两个点，此时每个点都只是一个普通的顶点，暂时先给每个点都赋一个权值 1。点 u 的权值表示选择这个点进入独立集，相当于选择了多少个原始顶点。比较 u,v 两个点向其他点的连边，如果 u,v 两个点对外的邻接情况不同即 N(u)\backslash\lbrace v\rbrace\neq N(v)\backslash \lbrace u\rbrace 则交换 u,v 的所有对外的连边就可以i得到一张完全不同的图，此时如果再交换一次就会得到原图。而因为 u,v 两个点的权值相同，因此这样交换相当于是交换了两个等价的位置，因此最大独立集的大小不会改变。此时这两个图全部两两抵消。

因此此时只需要考虑 N(u)\backslash \lbrace v\rbrace=N(v)\backslash\lbrace u\rbrace 的点对 (u,v)（即 u,v 两个点对其他点的邻接情况完全相同）。这个时候剩下 u,v 之间有没有边需要考虑。直接分类讨论：

• 若 u,v 两个点之间有边则她们不能同时出现在一个独立集中，又因为她们对外完全相同所以选择 u,v 两个点完全没有区别，可以直接删除其中一个点。此时原来两个权值为 1 的点就变成了一个权值为 1 的点。
• 若 u,v 两个点之间没有边，则因为其对外邻接情况完全相同，所以如果一个最大独立集选择了 u 点但是没选择 v 点，则 v 点和 u 点的邻居必然完全一样，但是 v 点却和 u 点没有边，所以一定可以把 v 点加入到最大独立集中。因此这类情况的 u,v 在最大独立集 中要么都被选要么都不被选。因此此时 u,v 两个点可以被合并为一个大点，这个大点的权值被设为 2。

然后考虑继续仿照上述操作进行合并所有的大点并继续配对得到权值更大的大点，以此类推直到无法合并当前最高级的大点为止。显然处理完后所有的大点的权值一定都是 2 的幂次，而且每种权值最多存在一个点，因为如果还剩下两个相同权值的点则还可以继续进行上面的操作。

用一个二进制编码来表示最终状态，该编码可以看作是将图中最后剩下的所有点的权值相加得到的值。容易证明一个二进制编码对应唯一一组大点权值的集合。

考虑 dp。设 f_{i,j} 表示从 i 个原始点出发，经过上面的配对合并和删除后，最终得到状态 j 的图数量对 2 取模后的结果。考虑怎么从 i-1 个点的情况转移到 i 个点的情况。新加入的点初始权值一定为 1，假设最终想要得到的状态是 S，记 w 是 S 二进制表示中最低的 1 为止对应的权值，则这个新点有两种不同的阶举：一种是新的点一路合并最后被在状态 S 中，为了得到最后的状态 S 加入新点前的状态必须是 S-1 ，加入权值为 1 的新点之后低位连续发生合并，最后形成了 S 中最低的大点。另一种情况是新点一路合并到权值 w 然后被删除，这个情况需要满足原状态中所有低于 w 的权值都存在而且本来已经包含一个权值为 w 的大点，因此原状态为 S+w-1。

因此 dp 转移式形如：f_{i,S}=f_{i-1,S-1}\oplus f_{i-1,S+\operatorname{lowbit}(S)-1}。

初始状态显然就是 f_{0,0}=1。

然后考虑固定最终的大点组成的集合后，她们之间互相连边可以产生怎样的最大独立及大小。因为所有大点的权值都是互不相同的 2 的幂次时一个大点的权值一定严格大于所有权值比她小的大点的权值的和，因此求最大全独立集的时候可以按照权值从大到小贪心处理，如果当前大点和所有已经选择了的权值更大的大点互不冲突则一定应该选择她，因此最大独立集可以被唯一的由这个贪心算法刻画而来。

先考虑如果所有大点都被选中到最大独立集中的情况，此时所有大点之间都必须没有任何边，对答案的贡献就是 1。

然后再考虑只有最小权值的大点没有被选中到最大独立集中的情况。此时除了这个大点以外其余点都被选择，因此其余大点之间都不能有边相连。而最小值的大点想要不被选择就必须和至少一个其余被选中的点之间有边相连。如果共有 m 个大点，则权值最小的大点向其余 m-1 个大点的非空连边方式共有 2^{m-1}-1 种，是奇数，因此会对最大独立集大小贡献 1。

然后考虑如果还有其他大点没有被选中到最大独立集中的情况。则此时她在贪心的过程中必然和某个权值更大的大点有边相连。此时翻转她和和她相连的最小的超级点的边不会改变贪心得到的最大独立集，因此这些图可以再次两两配对，模 2 后不会对答案产生任何贡献。

因此对一个状态 S 而言其在 \bmod\ 2 意义下只会贡献两个独立集大小，分别是 S 和 S-\operatorname{lowbit}(S)，对答案的贡献都是 1。因此考虑再次 dp，设 g_{i,j} 表示当前考虑 i 个点对图，最大独立集大小恰好为 j 的图的数量对 2 取模后的结果。如果当前 f_{n,S}=1 则因为 S 这个状态恰好等价于其对应的最大独立集的大小，因此直接转移 g_{n,S}\leftarrow g_{n,S}\oplus 1 即可。

然后第二个贡献 S-\operatorname{lowbit}(S) 需要先保证 S 本身不是 2 的幂次即本身不止有一个大点才可以转移，如果可以转移的话直接转移 g_{n,S-\operatorname{lowbit}(S)}\leftarrow g_{n,S-\operatorname{lowbit}(S)}\oplus 1 即可。

:::success[Code]

namespace lowspeed_song {

bitset<(1 << 14)> f[1 << 14], g[1 << 14];

inline void init() {
    f[0][0] = 1;
    for (int i = 1; i < (1 << 14); ++i)
        for (int j = 1; j <= i; ++j) {
            f[i][j] = f[i - 1][j - 1] ^ f[i - 1][j + (j &- j) - 1];
            if (f[i][j]) {
                g[i][j].flip();
                if (j != (j &- j)) g[i][j - (j &- j)].flip();
            }
        }
}

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, k; cin >> n >> k;
    cout << g[n][n - k] << '\n';
}

} // namespace lowspeed_song

:::

难度：彩-

鲜活指数：10

140. AT_agc036_f [AGC036F] Square Constraints

:::info[Description] Link. :::

:::info[Solution]{open} 题目中给的东西其实就是要求排列对应的坐标点落在大圆和小圆之间求排列的数量。记 f_i 表示满足 x^2+i^2<n^2 的 x\in[0,2n)\cap\mathbb N 的数量，g_i 表示满足 x^2+i^2\le 4n^2 的 x\in[0,2n)\cap\mathbb N 的数量。则排列 p_i 的限制条件就可以看作是 \forall i,f_i\le p_i<g_i。

考虑对内圆 p_i\ge f_i 的限制做容斥，钦定排列前 n 个位置中，有 k 个位置是不满足 p_i\ge f_i，则记这样的排列的数量为 F_k 则直接容斥可得答案为 \sum\limits_{k=0}^n(-1)^kF_k。

考虑算 F_k 的值。先给一个暴力的做法，设 h_i 表示 i 位置的上限，则 h_i 要么为 f_i 要么为 g_i。考虑已知 h_i 时合法的排列 p 数量怎么算。有一个结论是，如果把 h 数组内所有值从小到大排序，则满足限制的排列数为 \prod\limits_{i=0}^{2n-1}(h_i-i)。证明考虑按照上界从小王大分配数字时，处理第 j 个位置可以使用 0\sim h_j-1 这 h_j 个数字，前面也已经使用了 j 个数字，而这 j 个数字一定在上界范围内，因此共有 h_j-j 种剩余的可用选择。因此直接枚举 h_i 的值，其中恰好有 k 个上界选的是 f_i 然后对排列数求和就得到了一个暴力的做法。

考虑进一步优化时间复杂度。容易想到 dp，套路的把所有的 f_i 和所有满足 g_i\in[n,2n) 的 g_i 按照值从小到大放到一起，然后按值从小到大做扫描线，设 dp_j 表示当前已经选择了 j 个 f_i 时的贡献，则如果当前的是一个 g_i 而在这之前已经出现了 c 个必须选择的 g_j（这里说 g_j 必须选择是指 j\ge n 的 j 此时 f_j 的限制不存在）那么当前 g_i 前面留下的数共有 c+j 个，因此 g_i 在最终排序的下标就是 c+j，其贡献就是 g_i-c-j，因此转移就是 dp_j\leftarrow dp_j(g_i-c-j)。

然后考虑如果当前遇到了一个 f_i，则需要进一步分类讨论：

如果选 f_i 则她前面已经有 y+j 个被选中的数，所以其的贡献就是 f_i-y-j，因此转移就形如 dp'_{j+1}\leftarrow dp'_{j+1}+dp_j(f_i-y-j)。

如果不选 f_i 则之后就必须选对应的 g_i，考虑贡献提前处理，对应 g_i 的位置已经是确定的了，因此固定最终选 k 个 f 加上 n 个必须选的 g，这些大 g_i 前面一定有 n+k 个数，而当前之前已经经过了 x 个 f，其中只有 j 个 f 被选，所以共有 x-j 个 f 被放弃了，她们对应的 g 都会排在当前这个 g_i 的前面，因此当前这个 g_i 的最终下标就是 n+k+x-j，其贡献就是 g_i-n-k-x+j，转移就形如 dp'_{j+1}\leftarrow dp'_{j+1}+dp_j(g_i-n-k-x+j)。最后更新 dp\leftarrow dp' 即可。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int F[N], nF[N];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, mod; cin >> n >> mod;
    vector<pair<int, int>> a;
    for (int i = 0; i < n; ++i) {
        int l = 0, r = 2 * n - 1;
        while ((l + 1) * (l + 1) + i * i < n * n) ++l;
        while (r * r + i * i > 4 * n * n) --r;
        a.emplace_back(l, r);
    }
    for (int i = n; i < 2 * n; ++i) {
        int r = 2 * n - 1;
        while (r * r + i * i > 4 * n * n) --r;
        a.emplace_back(r, 0);
    }
    sort(a.begin(), a.end());
    function<int(int)> calc = [&](int k) {
        fill(F, F + n + 1, 0), F[0] = 1;
        int c1 = 0, c2 = 0;
        for (auto &[l, r] : a) {
            fill(nF, nF + n + 1, 0);
            if (!r) {
                for (int j = 0; j <= c2; ++j) nF[j] = F[j] * (l - c1 - j + 1) % mod;
                ++c1;
            } else {
                for (int j = 0; j <= c2; ++j) nF[j + 1] = (nF[j + 1] + F[j] * (l - c1 - j + 1) % mod) % mod, nF[j] = (nF[j] + F[j] * (r - (n + c2 - j + k) + 1) % mod) % mod;
                ++c2;
            } copy(nF, nF + n + 1, F);
        } return F[k];
    };
    int res = 0;
    for (int k = 0; k <= n; ++k)
        if (k & 1) res = (res - calc(k) + mod) % mod;
        else res = (res + calc(k)) % mod;
    cout << res << '\n';
}

} // namespace lowspeed_song

:::

难度：黑+

鲜活指数：9

141. P9682 Electro Master

:::info[Description] Link. :::

:::info[Solution]{open} 先考虑如果序列中不存在 ?，怎么计数序列的权值。先观察一下题目中给的操作的性质：

• 任意时刻序列中向左 / 向右移动的粒子数量不变。
• 所有粒子的相对位置在任何时刻都是不变的。
• 最终向左移动的第 i 个粒子和 i-1 个粒子的碰撞次数为前 i-1 个粒子中负电荷粒子的数量。

考虑判断第 i 个粒子是否会在最后变成 B。容易发现这个条件等价于其经历的有效碰撞次数为奇数。设前 i-1 个粒子中有 k 个粒子是负电荷，则第 i 个粒子的有效碰撞次数的次数就是 k[s_i\neq s_{i-1}]+[s_i\neq s_{i+1}](k+[s_i=\red{-}])，奇偶性也是容易算的。因此这个问题可以线性解决。

然后考虑加入 ? 的情况。为了方便处理，这里认为 s_0 粒子是正电荷粒子，s_{n+1} 粒子是负电荷粒子。容易想到 dp，设 f_{i,j,a,b,c} 表示当前处理了前 i 个粒子，前 \red{i-1} 个粒子中共有 j 个正电荷粒子，s_{i-1}=a,s_i=b,s_{i+1}=c 有多少种不同的合法串的填写方法。转移是十分容易的，显然有 f_{i+1,j+b,b,c,d}\leftarrow f_{i+1,j+b,b,c,d}+f_{i,j,a,b,c}。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

char s[N];
int C[2010][2010], suf[N], suf2[N], f[2010][2][2][2], sc[2010][2010], g[2010][2][2][2];
inline int calc(int x, int y) {
    if (y <= 0) return sc[x][0];
    if (y > x) return 0;
    return sc[x][y];
}
inline void add(int &x, int v) { x = (x + v) % mod; }
inline int chk(char c, int x) { return c == '?' || c == '+' && x || c == '-' && !x; }

inline void sol([[maybe_unused]]int __testcase_id) {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    s[0] = '+', s[n + 1] = '-';
    C[0][0] = 1;
    for (int i = 1; i < 2010; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    } for (int i = 0; i < 2010; ++i)
        for (int j = i; ~j; --j) sc[i][j] = (sc[i][j + 1] + C[i][j]) % mod;
    for (int i = n; i; --i) suf[i] = suf[i + 1] + (int)(s[i] == '?'), suf2[i] = suf2[i + 1] + (int)(s[i] == '+');
    for (int y : {0, 1}) for (int z : {0, 1}) if (chk(s[1], y) && chk(s[2], z)) f[1][1][y][z] = 1;
    int res = 0;
    for (int i = 1; i <= n; i++) {
        // 统计第 i 个粒子的贡献
        for (int j = 1; j <= i; ++j)
            for (int x : {0, 1}) for (int y : {0, 1}) for (int z : {0, 1})
                if (((int)(i - j) * (x != y) + (int)(i - j + !y) * (y != z)) & 1) add(res, f[j][x][y][z] * calc(suf[i + 2], i + 1 - j - y - z - suf2[i + 2]));
        if (i == n) break;
        memset(g, 0, sizeof g);
        for (int j = 1; j <= i; ++j) for (int x : {0, 1}) for (int y : {0, 1}) for (int z : {0, 1}) for (int w : {0, 1})
            if (chk(s[i + 2], w)) add(g[j + y][y][z][w], f[j][x][y][z]);
        memcpy(f, g, sizeof f);
    }
    cout << res << '\n';
}

} // namespace lowspeed_song

:::

难度：紫

鲜活指数：7

142. CF1842G Tenzing and Random Operations

:::info[Description] Link. :::

:::info[Solution]{open} 直接推是可以做的但是比较无聊，因此考虑编一个组合意义。可以看作是一个人从 1 号点出发，每次从 i 号点移动到 i+1 号点，问移动到 n+1 点的方案数是多少。从 i 到 i+1 初始有 a_i 种移动方法。然后随机一个位置 p 就相当于是额外加若干条从 q 走到 q+1 的路（q\ge p），有 v 种移动方法。

考虑直接 dp。设 f_{i,j} 表示当前考虑了前 i 个位置，使用 j 次随机，有多少种不同的走法。转移是简单的：

• 不使用工具，f_{i+1,j}\leftarrow f_{i,j}a_{i+1}
• 使用工具，需要进一步分类讨论：
  • 用一个以前用过的工具，f_{i+1,j}\leftarrow f_{i,j}jv。
  • 新开一个工具，f_{i+1,j+1}\leftarrow f_{i,j}(i+1)(m-j)v，其中 i+1 是该工具出现的位置，m-j 是可以选择的方案数。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int a[N], f[5010][5010];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, m, v; cin >> n >> m >> v;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    f[0][0] = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j <= min(m, i); ++j) {
            f[i + 1][j + 1] = (f[i + 1][j + 1] + f[i][j] * (i + 1) % mod * v % mod * (m - j) % mod) % mod;
            f[i + 1][j] = (f[i + 1][j] + f[i][j] * a[i + 1] % mod + f[i][j] * v % mod * j % mod) % mod;
        }
    int res = 0;
    const int inv = inversion(n);
    for (int i = 0; i <= min(n, m); ++i) res = (res + f[n][i] * power(inv, i, mod) % mod) % mod;
    cout << res << '\n';
}

} // namespace lowspeed_song

:::

难度：紫

鲜活指数：9

143. CF1264E Beautiful League

:::info[Description] Link. :::

:::info[Solution]{open} 为啥有黑来着。

有经典结论：竞赛图三元环数量为 \binom n3-\sum\limits_{i=1}^n\binom{\deg_i}{2}，其中 \deg_i 表示 i 点的出度。最大化三元环的数量即最小化 \sum\limits_{i=1}^n\binom{\deg_i}2 也就是最小化 \sum \deg_i^2 的值。

后面部分十分套路，考虑费用流建模。如果 u,v 之间的比赛结果未确定，则建一个比赛结点 e_{u,v}，然后连下面的边：

则此时若 e_{u,v}\to u 这条边走了流，表示 u 再比赛中赢了 v，否则表示 v 在比赛中赢了 u。

:::success[Code]

namespace lowspeed_song {

vector<int> adj[N];
int deg[N], win[N], mt[55][55];
char res[55][55];

namespace MCMF {

int S, T, hhh[N], e[N], f[N], ne[N], w[N], idxx, q[N], d[N], pre[N], incf[N], st[N];
inline void ae(int a, int b, int c, int d) {
    e[idxx] = b, w[idxx] = d, f[idxx] = c, ne[idxx] = hhh[a], hhh[a] = idxx++;
    e[idxx] = a, w[idxx] = -d, f[idxx] = 0, ne[idxx] = hhh[b], hhh[b] = idxx++;
}
inline int spfa() {
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = inf;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = 0;
        for (int i = hhh[t]; ~i; i = ne[i]) {
            int v = e[i];
            if (f[i] && d[v] > d[t] + w[i]) {
                d[v] = d[t] + w[i];
                pre[v] = i, incf[v] = min(incf[t], f[i]);
                if (!st[v]) {
                    q[tt++] = v;
                    if (tt == N) tt = 0;
                    st[v] = 1;
                }
            }
        }
    }
    return incf[T] > 0;
}
inline void ek(int &F, int &C) {
    F = C = 0;
    while (spfa()) {
        int tt = incf[T];
        F += tt, C += tt * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1]) f[pre[i]] -= tt, f[pre[i] ^ 1] += tt;
    }
}
}

inline void init() {
}

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, m; cin >> n >> m;
    vector<pair<int, int>> unk;
    memset(MCMF::hhh, -1, sizeof MCMF::hhh);
    for (int i = 0; i < n; ++i) res[i][i] = '0';
    while (m--) {
        int u, v; cin >> u >> v; --u, --v;
        adj[u].emplace_back(v), adj[v].emplace_back(u);
        res[u][v] = '1', res[v][u] = '0', mt[u][v] = mt[v][u] = 1, ++win[u];
    } for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) if (!mt[i][j])
        ++deg[i], ++deg[j], unk.emplace_back(i, j);
    MCMF::S = N - 1, MCMF::T = N - 2;
    vector<tuple<int, int, int>> match;
    for (int i = 0; i < unk.size(); ++i) {
        auto [u, v] = unk[i];
        MCMF::ae(MCMF::S, n + i + 1, 1, 0);
        MCMF::ae(n + i + 1, u, 1, 0);
        MCMF::ae(n + i + 1, v, 1, 0);
        match.emplace_back(u, v, MCMF::idxx - 4);
    }
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < deg[i]; ++j) MCMF::ae(i, MCMF::T, 1, win[i] + j);
    int F, C; MCMF::ek(F, C);
    for (auto &[u, v, eu] : match) {
        if (!MCMF::f[eu]) res[u][v] = '1', res[v][u] = '0';
        else res[v][u] = '1', res[u][v] = '0';
    } for (int i = 0; i < n; ++i, cout << '\n')
        for (int j = 0; j < n; ++j) cout << res[i][j];
}

} // namespace lowspeed_song

:::

难度：紫

鲜活指数：8

144. AT_agc056_c [AGC056C] 01 Balanced

:::info[Description] Link. :::

:::info[Solution]{open} 记 d_i 表示前 i 位中 0 的数量减去 1 的数量是多少，然后特殊处理一下 d_0=0。题目的条件可以被刻画为：

• 对一组限制条件 (l,r) 而言必须满足 d_r=d_{l-1}。

因此考虑差分约束建模。对一组限制条件 (l,r) 而言，其必须满足 d_r=d_{l-1}，可以建一组连接 l-1,r 两个点，边权为 0 的双向边。

然后对 |d_i-d_{i-1}|=1 的限制可以考虑先把限制放宽得到 |d_i-d_{i-1}|\le 1，这个是容易建模的，直接拆绝对值然后建 i\to i-1 和 i-1\to i 的权值为 1 的边即可。

然后从 0 号点跑一遍最短路得到 dis_i 数组就是一组满足条件且字典序最小的 d_i。考虑这个为什么是对的。因为每个位置都尽量让 v_i 的值大，也就是尽量选择 v_i=v_{i+1}+1 这个松弛操作，对应的就是贪心的能在当前位填 0 就填 0 因此确实可以满足字典序最小的条件。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int dis[N];
vector<pair<int, int>> adj[N];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int l, r; cin >> l >> r;
        adj[l - 1].emplace_back(r, 0);
        adj[r].emplace_back(l - 1, 0);
    } for (int i = 1; i <= n; ++i) adj[i].emplace_back(i - 1, 1), adj[i - 1].emplace_back(i, 1);
    deque<int> q;
    memset(dis, -0x3f, sizeof dis);
    dis[0] = 0, q.emplace_back(0);
    while (q.size()) {
        int t = q.front(); q.pop_front();
        for (auto &[g, w] : adj[t]) if (dis[g] < -inf / 2) {
            dis[g] = dis[t] + w;
            if (!w) q.emplace_front(g);
            else q.emplace_back(g);
        }
    }
    for (int i = 1; i <= n; ++i)
        if (dis[i - 1] > dis[i]) cout << 1;
        else cout << 0;
    cout << '\n';
}

} // namespace lowspeed_song

:::

难度：紫

鲜活指数：8

145. P14019 [ICPC 2024 Nanjing R] 地铁

:::info[Description] Link :::

:::info[Solution]{open} 考虑用一个二元组 (u,i) 来维护状态，表示当前在车站 u 的 i 号线上。一个暴力的做法是直接建出整张图然后跑 dijk，但是时间复杂度明显爆炸了。

注意到导致边的数量爆炸的原因主要是换乘，因此考虑优化这个部分。在某个车站从线路 x 换到线路 y 的代价固定为 a_yb_x。如果 (u,x) 状态的最短距离已经被去确定为 (u,x) 则她换到 y 线的总距离就是 dis_x+b_xa_y 是一个一次函数的形式（把 a_y 看作变量 t 后可以被表示为 f_x(t)=b_xt+d_x）。因此考虑对每个车站把所有已经确定的线路对应的直接放到一个 LiChao SegTree 上，此时对每个车站直接把所有已经确定的线路对应的直线扔到李超树里，要切换到线路 y 的时候只需要查询 f_x(t) 函数在 t=a_y 位置的最小值即可。

然后注意到 b_x>0 一定成立，因此所有的 f_x(t) 都是单调递增的直线，因此考虑在当前站台所有没有确定的线路都按照 a_y 的值从小到大排序，则换乘得到的下一个最小后按一定是 a_y 最小的那一个。对每个车站维护指针每次只把当前最小的 a 的未确定状态加入 dijkstra 即可。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

vector<int> rail[N];
int n, k, a[N], b[N], frt[N], bel[N], e[N], pos[N], idx_, w[N], dis[N], res[N], vis[N];

namespace LiChaoSgt {
    vector<int> tree[N];
    pair<int, int> seg[N];
    inline int calc(int id, int u, int x) {
        if (!id) return inf;
        return seg[id].first * a[bel[rail[u][x]]] + seg[id].second;
    }
    inline void ins(int u, int l, int r, int rt, int id) {
        if (l == r) {
            if (!tree[u][rt] || calc(id, u, l) < calc(tree[u][rt], u, l)) tree[u][rt] = id;
            return;
        } int mid = l + r >> 1;
        if (calc(id, u, mid) < calc(tree[u][rt], u, mid)) swap(tree[u][rt], id);
        if (calc(id, u, l) < calc(tree[u][rt], u, l)) ins(u, l, mid, rt << 1, id);
        if (calc(id, u, r) < calc(tree[u][rt], u, r)) ins(u, mid + 1, r, rt << 1 | 1, id);
    }
    inline void ins(int u, int k, int b, int id) { seg[id] = {k, b}, ins(u, 0, (int)rail[u].size() - 1, 1, id); }
    inline int qry(int u, int l, int r, int rt, int val) {
        if (l == r) return calc(tree[u][rt], u, val);
        int mid = l + r >> 1, now = calc(tree[u][rt], u, val);
        if (val <= mid) return min(now, qry(u, l, mid, rt << 1, val));
        return min(now, qry(u, mid + 1, r, rt << 1 | 1, val));
    }
    inline int qry(int u, int pos) { return qry(u, 0, (int)rail[u].size() - 1, 1, pos); }
}

inline void sol([[maybe_unused]]int __testcase_id) {
    cin >> n >> k;
    for (int i = 1; i <= k; ++i) cin >> a[i];
    for (int i = 1; i <= k; ++i) cin >> b[i];
    for (int i = 1; i <= k; ++i) {
        int p, x, las = ++idx_;
        cin >> p >> x;
        frt[las] = x, bel[las] = i, rail[x].emplace_back(las);
        for (int j = 1; j < p; ++j) {
            int c, now = ++idx_; cin >> c >> x;
            frt[now] = x, bel[now] = i, rail[x].emplace_back(now);
            e[las] = now, w[las] = c, las = now;
        }
    }
    for (int i = 1; i <= n; ++i) sort(rail[i].begin(), rail[i].end(), [&](auto &x, auto &y) { return a[bel[x]] < a[bel[y]]; });
    for (int i = 1; i <= n; ++i) LiChaoSgt::tree[i].resize(rail[i].size() * 4 + 5);
    memset(dis, 0x3f, sizeof dis), memset(res, 0x3f, sizeof res);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    for (int &i : rail[1]) dis[i] = 0, q.emplace(0, i);
    // cerr << "!!!\n";
    while (q.size()) {
        auto [D, id] = q.top();
        q.pop();
        if (vis[id] || D != dis[id]) continue;
        vis[id] = 1;
        int u = frt[id], c = bel[id];
        res[u] = min(res[u], D), LiChaoSgt::ins(u, b[c], D, id);
        if (e[id] && dis[e[id]] > D + w[id]) dis[e[id]] = D + w[id], q.emplace(dis[e[id]], e[id]);
        while (pos[u] < rail[u].size() && vis[rail[u][pos[u]]]) ++pos[u];
        if (pos[u] < rail[u].size()) {
            int nd = LiChaoSgt::qry(u, pos[u]);
            if (dis[rail[u][pos[u]]] > nd) dis[rail[u][pos[u]]] = nd, q.emplace(nd, rail[u][pos[u]]);
        }
    }
    for (int i = 2; i <= n; ++i) cout << res[i] << ' ';
    cout << '\n';
}

} // namespace lowspeed_song

:::

难度：紫+

鲜活指数：7

146. P10573 [JRKSJ R8] C0mp0nents

:::info[Description] Link. :::

:::info[Solution]{open} 很显然 k 是没有用的，因此后面分析将只考虑 k=1 的情况。

容易证明固定一个 s 的时候答案一定是连续的一段区间。一个区间 [l,r] 如果想要合法，则必须同时满足下面三个条件：

• 每个 x\in (l,s) 都有边连向更小的位置。
• 每个 x\in(s,r) 都有边连向更大的位置。

因此考虑处理出 L_i 表示只考虑向左的条件时最远能扩展到哪里，R_i 表示只考虑向右的条件时最远能扩展到哪里。显然 L_i 和 R_i 都是满足单调性的，因此直接扫描一下就可以线性处理出结果。

此时可以知道对一个起始位置 s 而言，[L_s,s) 和 (s,R_s] 之间都是连通的可以互相转移，问题在于 \lbrace s\rbrace 是否能和上面两个区间连通起来互相转移。直接对 s 枚举每一条边 <u,v> 时间复杂度爆炸了，考虑优化。反过来先枚举每一条边 <u,v> 然后考虑判断是否存在一条边 <u,v> 满足 L_s\le u<s<v\le R_s。容易注意到这样的边能帮助的 s 要么为空要么为一段连续的区间，因此直接快速求出合法的区间然后差分 + 前缀和处理 s 这个位置是否存在一条边可以让她们连通即可。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

vector<int> adj[N];
int n, m, k, res[N], a[N], diff[N], e[N], L[N], R[N], LL[N], RR[N], pre[N], suf[N];

inline void gao(int st) {
    int idx = 0;
    for (int i = st; i <= n; i += k) a[++idx] = i, e[i] = idx;
    for (int i = 0; i <= idx + 1; ++i) diff[i] = 0;
    for (int i = 1; i <= idx; ++i) {
        L[i] = 0, R[i] = idx + 1;
        for (int &v : adj[a[i]])
            if (e[v] < i) L[i] = max(L[i], e[v]);
            else R[i] = min(R[i], e[v]);
    }
    LL[1] = 1;
    for (int i = 2; i <= idx; ++i) {
        LL[i] = LL[i - 1];
        if (L[i - 1] < LL[i]) LL[i] = i - 1;
    }
    RR[idx] = idx;
    for (int i = idx - 1; i; --i) {
        RR[i] = RR[i + 1];
        if (R[i + 1] > RR[i]) RR[i] = i + 1;
    }
    pre[idx + 1] = idx + 1;
    for (int i = idx; i; --i) {
        pre[i] = pre[i + 1];
        while (pre[i] > 1 && RR[pre[i] - 1] >= i) --pre[i];
    }
    suf[0] = 0;
    for (int i = 1; i <= idx; ++i) {
        suf[i] = suf[i - 1];
        while (suf[i] < idx && LL[suf[i] + 1] <= i) ++suf[i];
    }
    for (int i = 1; i <= idx; ++i)
        for (int &v : adj[a[i]]) if (i < e[v]) {
            int l = max(i + 1, pre[e[v]]), r = min(e[v] - 1, suf[i]);
            if (l <= r) ++diff[l], --diff[r + 1];
        }
    for (int i = 1; i <= idx; ++i) {
        diff[i] += diff[i - 1];
        if (L[i] < LL[i] && R[i] > RR[i])
            LL[i] = RR[i] = i;
        else if (!diff[i]) {
            if (L[i] < LL[i]) LL[i] = i;
            else if (R[i] > RR[i]) RR[i] = i;
        }
        res[a[i]] = RR[i] - LL[i] + 1;
    }
}

inline void sol([[maybe_unused]]int __testcase_id) {
    cin >> n >> m >> k;
    while (m--) {
        int a, b; cin >> a >> b;
        if (a % k == b % k) adj[a].emplace_back(b), adj[b].emplace_back(a);
    } for (int i = 1; i <= k; ++i) gao(i);
    for (int i = 1; i <= n; ++i) cout << res[i] << ' '; cout << '\n';
}

} // namespace lowspeed_song

:::

难度：紫+

鲜活指数：7

147. P14383 [JOISC 2017] 港口设施 / Port Facility

:::info[Description] Link. :::

:::info[Solution]{open} 观察样例可得答案要么为 0 要么是 2 的若干次幂的形式。

考虑若存在两个箱子 i,j 满足 a_i<a_j<b_i<b_j 则 i,j 两个箱子不能被放在同一个栈内。一个暴力的方法是直接枚举所有这样的二元组 (i,j)，这两个元素不能同属一个栈，因此直接扩展域并查集把 i,j+n 和 i+n,j 合并到一个集合 S 里，最终答案就是 2^{|S|}。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

pair<int, int> a[N];

struct DSU {
    int fa[N];
    inline DSU() { iota(fa, fa + N, 0); }
    inline void init(int maxn) { iota(fa, fa + maxn, 0); }
    inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
    inline int merge(int x, int y) {
        x = find(x), y = find(y);
        if (x != y) return fa[x] = y, 1;
        return 0;
    }
} dsu;

int ne[N], n;

inline int chk(int i, int j) {
    if (dsu.find(i) == dsu.find(j)) return 0;
    return dsu.merge(i, j + n), dsu.merge(j, i + n), 1;
}

inline void sol([[maybe_unused]]int __testcase_id) {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].first >> a[i].second;
    sort(a + 1, a + n + 1);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    for (int i = 1; i <= n; ++i) {
        auto [l, r] = a[i];
        while (q.size() && q.top().first < l) {
            int x = q.top().second; q.pop();
            if (ne[x]) q.emplace(a[ne[x]].second, ne[x]);
        } vector<int> v;
        while (q.size() && q.top().first < r) v.emplace_back(q.top().second), q.pop();
        for (int &j : v) if (!chk(i, j)) { cout << 0 << '\n'; return; }
        for (int j = 0; j + 1 < v.size(); ++j) ne[v[j]] = v[j + 1];
        if (v.size()) q.emplace(a[v[0]].second, v[0]);
        q.emplace(r, i);
    } int cnt = 0;
    for (int i = 1; i <= n + n; ++i) cnt += (int)(dsu.find(i) == i);
    cout << power(2, cnt >> 1, mod) << '\n';
}

} // namespace lowspeed_song

:::

难度：紫-

鲜活指数：6

148. CF1299D Around the World

:::info[Description] Link. :::

:::info[Solution]{open} 這也能做嗎.jpg

套路的考慮先求出圖的任意一個 DFS 生成樹，然後結合綫性基來維護答案。具體的，任意求出圖的一個 DFS 樹后記 dis_u 表示從根結點到 u 結點上經過的所有邊的邊權的 XOR 值，則考慮一條非樹邊 <u,v,w> 其和樹上的路徑 u\leftrightarrow v 組成一個環，這個環的 XOR 值就是 dis_u\oplus dis_v\oplus w。把所有這些環的邊權 XOR 值都插入到異或綫性基裏，因爲任意一條閉合路綫中走偶數次的邊都對 XOR 值沒有影響，因此只需要考慮走了奇數次的邊。而由經典結論可知這些邊必然都可以被上述若干個基本環拼凑得到。因此若某幾個基本環的 XOR 值為 0 則把這些環拼接起來就得到了一個 XOR 值為 0 的閉合路綫。而這個閉合路綫必然是非平凡的，因爲每個基本換都對應一條自己的非樹邊，非樹邊不會被訪問超過 1 次，因此也就不會被抵消掉。

因此題目中的限制條件等價於：所有當前和點 1 連通的基本環的 XOR 之都必須能成功的插入到同一個異或綫性基中。如果某個值沒法插入則説明她能夠被前面的若干個環 XOR 出來，因此存在一個非空組合的 XOR 值為 0 方案非法。

然後把點 1 和所有和點 1 相鄰的邊暫時刪除剩下若干個連通塊即可。因爲題目限制保證不存在經過 1 點且長度 >3 的簡單環，這個條件限制了每個連通塊和 1 結點的連接方式。假設一個連通塊裏有兩個點 u,v 都和 1 號結點相鄰，因爲 u,v 兩個點位於同一個連通塊内所以塊内必然存在至少一條 u\to v 的簡單路徑。再加上 1\to u 和 v\to 1 的路徑就得到了一個經過 1 的簡單環。因爲這個環的長度不能 >3 因此 u,v 兩個點必須直接有邊相鄰。記憶不的，如果一個塊内有三個點 u,v,w 都和 1 號結點相鄰，那麽她們之間兩兩都有路徑項鏈，因此 1\to u\to v\to w\to 1 就形成了一個長度至少為 4 的簡單還，引發矛盾。

因此：刪除點 1 后每個連通塊最多只有兩條邊原來就連向 1 號結點。先分開處理每個連通塊，在塊内 DFS 求出所有基本環的 XOR 并將其插入到一個綫性基 B 中。如果塊的内部發生插入失敗，則這個塊只要和 1 號結點聯通就一定會出現非法路綫。因爲可以從 1 走進這個塊，然後走完這個 XOR 為 0 的閉合路綫再園路返回 1，往返路徑出現兩次會全部抵消因此得到不合法的路徑。所以這種塊只能把所有和 1 相鄰的便都刪除掉。

如果塊内部本身合法就考慮她和 1 結點之間的邊。如果只有一條邊那麽考慮分類討論這條邊的情況：

• 如果刪除了這條邊那麽這個塊和 1 號節點斷開，什麽都不用加入全局綫性基。
• 如果保留這條邊，那麽點 1 可以進入這個塊，因此把塊内綫性基 B 合并到全局綫性基中即可。

如果有兩條邊設她們分別是 (1,u,a) 和 (1,v,b)，則根據前面的分析可知 u,v 之間必然還有一條邊，邊權為 c。則此時還會多出一個三元環 (1,u,v) 其 XOR 值就是 a\oplus b\oplus c。此時有三種情況：

• 兩條邊都刪除：什麽也不用加入。
• 只保留一條邊：點 1 可以進入這個塊，只需要加入綫性基 B 即可。注意有兩種保留一條邊的方法。
• 保留兩條邊：除了 B 以外還需要加入三元環的貢獻即 XOR a\oplus b\oplus c 這個環。此時如果 a\oplus b\oplus c 插入不了 B 這個綫性記則兩條邊都保留這個操作本身就是非法的。

現在每個連通塊都被壓縮成了兩三個網全局綫性基中加入哪些數的選擇。問題只剩下如何把不同的連通塊合起來處理了。此時顯然不能只保證每個塊内部合法，因爲不同的塊之間也可以凑出 XOR 為 0 的環。所以還需要維護一個全局的異或綫性基。注意到 w<32，因此所有的環 XOR 的二進制表示最多只有 5 位 也就是異或綫性基最多只有 5 個元素。DFS 一下可以發現本質不同的不同狀態數量只有 374 種。把這 374 個狀態先全部提前編號，然後設 f_S 表示當前處理完了前若干個連通塊的信息后當前全局綫性基的狀態為 S 的方案數。初始時綫性基為空，處理一個連通塊的過程中根據前面分析出來的選擇進行轉移，如果需要把某個塊的綫性基 B 加入當前狀態則把 B 中的所有數逐個插入當前綫性基。如果有一個數沒法插入就説明轉移非法。如果全部成功插入則可以得到一個新的綫性基狀態。這些合并結果都可以提前預處理出。

記 merge(A,B) 表示合并 A,B 兩個綫性基后得到的新綫性基，則轉移考慮分類討論：

• 對只有一個便連向 1 的塊，轉移要麽仍然為 S 要麽從 S 變爲 merge(S,B)。
• 對於有兩條邊的塊，轉移方式有下面的三種：

需要處理一下綫性基無法插入也就是轉移非法的情況。

處理完所有連通塊后，答案可以被表示爲 \sum f_S 的形式。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

struct Basis {
    int b[5];
    inline Basis() { memset(b, 0, sizeof b); }
    inline int ins(int x) {
        for (int i = 4; ~i; --i) if (x >> i & 1) {
            if (b[i]) x ^= b[i];
            else return b[i] = x, 1;
        } return 0;
    }
    inline int getmask() const {
        int s = 1;
        for (int i = 0; i < 5; ++i) if (b[i]) {
            int t = s;
            for (int j = 0; j < 32; ++j)
                if (s >> j & 1) t |= 1 << (j ^ b[i]);
            s = t;
        } return s;
    }
};

vector<pair<int, int>> adj[N];
int w_[N], vis[N], dep[N], xr[N], f[N], g[N];
int trans[710][710], idx;
Basis state[N];

inline void sol([[maybe_unused]]int __testcase_id) {
    idx = 1;
    map<int, int> mp; mp[1] = 0;
    for (int i = 0; i < idx; ++i)
        for (int j = 1; j < 32; ++j) {
            Basis t = state[i];
            if (!t.ins(j)) continue;
            int s = t.getmask();
            if (!mp.count(s)) mp[s] = idx, state[idx++] = t;
        }
    memset(trans, -1, sizeof trans);
    for (int i = 0; i < idx; ++i)
        for (int j = 0; j < idx; ++j) {
            Basis t = state[i];
            int ok = 1;
            for (int k = 0; k < 5; ++k)
                if (state[j].b[k] && !t.ins(state[j].b[k])) ok = 0;
            if (ok) trans[i][j] = mp[t.getmask()];
        }
    int n, m; cin >> n >> m;
    memset(w_, -1, sizeof w_);
    while (m--) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].emplace_back(v, w), adj[v].emplace_back(u, w);
        if (u == 1) w_[v] = w;
        if (v == 1) w_[u] = w;
    } f[0] = 1;
    for (int i = 2; i <= n; ++i) if (!vis[i]) {
        Basis basis;
        int ok = 0;
        vector<pair<int, int>> vec;
        function<void(int, int)> dfs = [&](int u, int fa) {
            vis[u] = 1, dep[u] = dep[fa] + 1;
            if (~w_[u]) vec.emplace_back(u, w_[u]);
            for (auto &[v, w] : adj[u]) if (v != fa && v != 1) {
                if (!vis[v]) xr[v] = xr[u] ^ w, dfs(v, u);
                else if (dep[v] < dep[u] && !basis.ins(xr[u] ^ xr[v] ^ w)) ok = 1;
            }
        };
        dfs(i, 0);
        vector<pair<int, int>> vec_ = {{0, 1}};
        if (!ok) {
            int b = mp[basis.getmask()];
            if (vec.size() == 1) vec_.emplace_back(b, 1);
            else if (vec.size() == 2) {
                vec_.emplace_back(b, 2);
                int u = vec[0].first, v = vec[1].first, w = 0;
                for (auto &[vv, c] : adj[u]) if (vv == v) { w = c; break; }
                Basis T = basis;
                if (T.ins(vec[0].second ^ vec[1].second ^ w)) vec_.emplace_back(mp[T.getmask()], 1);
            }
        }
        for (int i = 0; i < idx; ++i) g[i] = 0;
        for (int i = 0; i < idx; ++i) for (auto &[j, k] : vec_)
            if (~trans[i][j]) g[trans[i][j]] = (g[trans[i][j]] + f[i] * k) % mod;
        for (int i = 0; i < idx; ++i) f[i] = g[i];
    }
    int res = 0;
    for (int &i : f) res = (res + i) % mod;
    cout << res << '\n';
}

} // namespace lowspeed_song

:::

难度；黑

鲜活指数：8

149. AT_agc029_f [AGC029F] Construction of a tree

:::info[Description] Link. :::

:::info[Solution]{open} 考虑二分图建模。固定 1 号结点为树的根结点，则对每个非根结点 2\sim n 其都有一个父亲结点 f_i。构建二分图，左部点为编号 2,3,4,\ldots,n 的点，右部点为集合 S_1,S_2,\ldots,S_{n-1}。如果 x\in S_i 就在左部点 x 和右部点 E_i 之间连一条边。

先在二分图上求一个完美匹配，由 Hall 定理可知若不存在完美匹配则必然无解，否则设集合 S_i 匹配到的结点为 f_i，考虑让 S_i 这个集合负责把 f_i 结点接入树中。具体的：

从 1 号结点开始 BFS，假设当前已经访问到了结点 x 则考虑枚举所有满足 x\in S_i 且还没有使用过的集合 S_i。因为 x\in S_i\land f_i\in S_i 因此可以直接连边 <x,f_i> 作为集合 S_i 的答案。然后记 f_i 的父亲结点为 x，把 f_i 加入到队列中并继续 BFS 扩展即可。

如果 BFS 结束后仍然有结点没有被访问到，则说明已经无法通过任何集合向外继续扩展，因此此时不存在合法方案，直接输出 -1 即可。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

namespace Flow {

int S, T, dep[N], cur[N];
struct edg {
    int e, f, o;
    edg(int a, int b) { e = a, f = b, o = 0; }
} ; vector<edg> adj[N];
inline void link(int s, int e, int f) {
    adj[s].push_back({edg(e, f)}), adj[e].push_back(edg(s, 0));
    int s1 = adj[s].size() - 1, s2 = adj[e].size() - 1;
    adj[s][s1].o = s2, adj[e][s2].o = s1;
}
inline bool bfs() {
    queue<int> q;
    memset(dep, 0, sizeof dep), memset(cur, 0, sizeof cur);
    dep[S] = 1, q.emplace(S);
    while (q.size()) {
        int p = q.front(); q.pop();
        for (auto &[r, f, _] : adj[p]) if (f && !dep[r]) {
            dep[r] = dep[p] + 1, q.emplace(r);
            if (r == T) return 1;
        }
    } return 0;
}
inline int dfs(int p, int f) {
    if (p == T) return f;
    int s = 0;
    for (int &i = cur[p]; i < adj[p].size(); ++i) {
        if (!f) break;
        int q = adj[p][i].e, fx = adj[p][i].f;
        if (fx && dep[p] + 1 == dep[q]) {
            int delta = dfs(q, min(f, fx));
            if (!delta) continue;
            adj[p][i].f -= delta, adj[q][adj[p][i].o].f += delta;
            f -= delta, s += delta;
        }
    }
    return s ? s : (dep[p] = 0);
}
inline int dinic() {
    int s = 0;
    while (bfs()) s += dfs(S, inf);
    return s;
}

} // namespace Flow

vector<int> S[N];
pair<int, int> res[N];
int F[N], vis[N], fa[N], id[N];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n; cin >> n;
    Flow::S = 1, Flow::T = n + n;
    for (int i = 2; i <= n; ++i) Flow::link(Flow::S, i, 1);
    for (int i = 1; i < n; ++i) {
        int c; cin >> c;
        while (c--) {
            int w; cin >> w;
            S[w].emplace_back(i);
            if (w != 1) Flow::link(w, n + i, 1);
        } Flow::link(n + i, Flow::T, 1);
    } if (Flow::dinic() != n - 1) { cout << -1 << '\n'; return; }
    for (int i = 1; i <= n; ++i)
        for (auto &[e, f, o] : Flow::adj[n + i])
            if (2 <= e && e <= n && f) { F[i] = e; break; }
    queue<int> q; q.emplace(1);
    while (q.size()) {
        int t = q.front(); q.pop();
        for (int &i : S[t]) if (!vis[i])
            vis[i] = 1, fa[F[i]] = t, id[F[i]] = i, q.emplace(F[i]);
    } for (int i = 1; i < n; ++i) if (!vis[i]) { cout << -1 << '\n'; return; }
    for (int i = 2; i <= n; ++i) res[id[i]] = {fa[i], i};
    for (int i = 1; i < n; ++i) cout << res[i].first << ' ' << res[i].second << '\n';
}

} // namespace lowspeed_song

:::

难度：黑

鲜活指数：9

150. P13583 [NWRRC 2023] Colorful Village

:::info[Description] Link :::

:::info[Solution]{open} 考虑到颜色为 1 的两个点中必选其中一个，设这个点为 u，则考虑以 u 点为根做图论建模跑 2-Sat。具体的，记 fa_i 表示以 u 点为根时 i 点的父亲结点是什么，则因为根结点必选所以如果父亲结点没有选则儿子结点必须不选，如果儿子结点选了那么父亲结点必须不选。然后再考虑同色的关系，设两个同色的位置是 i,j，则此时若 i 选了则 j 必须不选，j 选了则 i 必须不选，反之同理。

一个特殊的地方是根结点必须选，所以需要从 u' 向 u 连一条边。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

stack<int> stk;
vector<int> adj[N], col[N], adj_[N];
int n, a[N], dfn[N], low[N], bel[N], idx, tot, ins[N];

inline void dfs(int u) {
    dfn[u] = low[u] = ++idx;
    ins[u] = 1, stk.emplace(u);
    for (int &v : adj_[u]) {
        if (!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    } if (dfn[u] == low[u]) { ++tot;
        while (stk.top() != u) {
            int t = stk.top(); stk.pop();
            ins[t] = 0, bel[t] = tot;
        } int t = stk.top(); stk.pop();
        ins[t] = 0, bel[t] = tot;
    }
}

inline void dfs(int u, int fa) {
    if (fa) adj_[u].emplace_back(fa), adj_[fa + (n << 1)].emplace_back(u + (n << 1));
    for (int &v : adj[u]) if (v != fa) dfs(v, u);
}

inline void sol([[maybe_unused]]int __testcase_id) {
    cin >> n;
    for (int i = 1; i <= n + n; ++i) adj[i].clear(), adj_[i].clear(), col[i].clear();
    for (int i = 1; i <= n + n; ++i) cin >> a[i], col[a[i]].emplace_back(i);
    for (int i = 1; i < n + n; ++i) {
        int a, b; cin >> a >> b;
        adj[a].emplace_back(b), adj[b].emplace_back(a);
    }
    function<bool(int)> gao = [&](int rt) {
        idx = tot = 0;
        for (int i = 1; i <= n + n + n + n; ++i) dfn[i] = low[i] = 0, adj_[i].clear();
        adj_[rt + (n << 1)].emplace_back(rt);
        for (int i = 1; i <= n; ++i) {
            adj_[col[i][0]].emplace_back(col[i][1] + (n << 1));
            adj_[col[i][1]].emplace_back(col[i][0] + (n << 1));
            adj_[col[i][0] + (n << 1)].emplace_back(col[i][1]);
            adj_[col[i][1] + (n << 1)].emplace_back(col[i][0]);
        } dfs(rt, 0);
        for (int i = 1; i <= n + n; ++i)
            if (!dfn[i]) dfs(i);
        for (int i = 1; i <= n + n; ++i)
            if (bel[i] == bel[i + n + n]) return 0;
        return 1;
    };
    if (gao(col[1][0])) {
        for (int i = 1; i <= n + n; ++i)
            if (bel[i] < bel[i + n + n]) cout << i << ' ';
        cout << '\n';
    } else if (gao(col[1][1])) {
        for (int i = 1; i <= n + n; ++i)
            if (bel[i] < bel[i + n + n]) cout << i << ' ';
        cout << '\n';
    } else cout << -1 << '\n';
}

} // namespace lowspeed_song

:::

难度：紫-

鲜活指数：6

151. P9374 「DROI」Round 2 单图

:::info[Description] Link. :::

:::info[Solution]{open} 容易观察到合法的图结构必然是要么每个点没有入度要么没有出度要么是一个两个点的 SCC。

先不考虑两个点 SCC 这个结构，记有 x 个点有没有入度，y 个点没有出度。则对每个没有入度的点，其都只能连向没有出度的点。简单计数一下可以知道不同的连边方案数为 (2^y-1)^x。因为 x+y=n 所以计数可以直接枚举 x 的取值，总方案数就是 \sum\limits_{i=0}^{n-1}\binom ni(2^{n-i}-1)^i。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int C[N][N], f[N], g[N];

inline void sol([[maybe_unused]]int __testcase_id) {
    int T, mod; cin >> T >> mod;
    C[0][0] = 1;
    for (int i = 1; i < N; ++i) {
        C[i][0] = 1;
        for (int j = 1; j <= i; ++j) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
    }
    f[0] = 1;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < i; ++j)
            f[i] = (f[i] + C[i][j] * power(power(2, i - j, mod) - 1, j, mod) % mod) % mod;
    g[0] = 1;
    for (int i = 1; i < N; ++i) {
        g[i] = 1;
        for (int j = 1; j <= i; ++j) g[i] = g[i] * (j + j - 1) % mod;
    }
    while (T--) {
        int n; cin >> n;
        int res = 0;
        for (int i = 0; i <= n / 2; ++i)
            res = (res + C[n][i + i] * g[i] % mod * f[n - i - i] % mod) % mod;
        cout << res << '\n';
    }
}

} // namespace lowspeed_song

:::

难度：蓝

鲜活指数：7

152. CF1268E Happy Cactus

:::info[Description] Link. :::

:::info[Solution]{open} 先考虑图是一个树的情况。此时定义 f_u 表示当前已经处理的边中所有从 u 结点出发的沿边权递增的路径能够到达的点的数量。这个是容易处理的，直接把边权从大到小排序然后按顺序转移即可。

然后考虑把上述做法扩展到仙人掌上。考虑如果当前一条边 <u,v> 在仙人掌的某个环上，则处理该边的时候 u,v 两个点有可能已经通过环的另一侧连接起来了，此时直接转移的话答案会算重。容易发现此时 <u,v> 边必然是整个环上权值最小的边。进一步分析可以发现算重的部分就是处理该环的最大边是她两个端点当前能够到达的那些点。因此在处理最大边的时候把这个值记为 g_i，则之后处理最小边的时候把答案额外减去 g_i 即可。

找仙人掌中所有的环是容易的，这里就不展开说了。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int n, m;
pair<int, int> e[N];
vector<pair<int, int>> adj[N];
int f[N], g[N], Min[N], fa[N], fa_[N], dep[N];

inline void gao(int u, int v, int id) {
    vector<int> v1 = {id}, v2;
    for (int i = u; i != v; i = fa[i]) v2.emplace_back(fa_[i]);
    reverse(v2.begin(), v2.end());
    for (int &i : v2) v1.emplace_back(i);
    int mi = min_element(v1.begin(), v1.end()) - v1.begin();
    int mx = max_element(v1.begin(), v1.end()) - v1.begin();
    int ok = 1;
    for (int i = mi; i != mx; ) {
        if (v1[i] > v1[(i + 1) % v1.size()]) ok = 0;
        i = (i + 1) % v1.size();
    } for (int i = mi; i != mx; ) {
        if (v1[i] > v1[(i + v1.size() - 1) % v1.size()]) ok = 0;
        i = (i + v1.size() - 1) % v1.size();
    } if (ok) Min[v1[mi]] = v1[mx];
}

inline void dfs(int u, int pid) {
    for (auto &[v, id] : adj[u]) if (id != pid) {
        if (!dep[v]) dep[v] = dep[u] + 1, fa[v] = u, fa_[v] = id, dfs(v, id);
        else if (dep[u] > dep[v]) gao(u, v, id);
    }
}

inline void sol([[maybe_unused]]int __testcase_id) {
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v; cin >> u >> v;
        e[i] = {u, v}, adj[u].emplace_back(v, i), adj[v].emplace_back(u, i);
    } dep[1] = 1, dfs(1, 0);
    for (int i = 1; i <= n; ++i) f[i] = 1;
    for (int i = m; i; --i) {
        auto &[u, v] = e[i];
        int val = f[u] + f[v];
        if (Min[i]) val -= g[Min[i]];
        f[u] = f[v] = g[i] = val;
    } for (int i = 1; i <= n; ++i) cout << f[i] - 1 << ' '; cout << '\n';
}

} // namespace lowspeed_song

:::

难度：紫

鲜活指数：7

153. CF1572D Bridge Club

:::info[Description] [Link(https://www.luogu.com.cn/problem/CF1572D)] :::

:::info[Solution]{open} 一个暴力的做法是直接二分图建模，注意到直接把可以组队的点连起来，相邻两个点的 popcount 值差一定为 1，因此一定能得到一张二分图。直接增广 k 次跑 dinic 即可。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

namespace MCMF {

int S, T, hhh[N], e[N], f[N], ne[N], w[N], idxx, q[N], d[N], pre[N], incf[N], st[N];
inline void ae(int a, int b, int c, int d) {
    e[idxx] = b, w[idxx] = d, f[idxx] = c, ne[idxx] = hhh[a], hhh[a] = idxx++;
    e[idxx] = a, w[idxx] = -d, f[idxx] = 0, ne[idxx] = hhh[b], hhh[b] = idxx++;
}
inline int spfa() {
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = inf;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = 0;
        for (int i = hhh[t]; ~i; i = ne[i]) {
            int v = e[i];
            if (f[i] && d[v] > d[t] + w[i]) {
                d[v] = d[t] + w[i];
                pre[v] = i, incf[v] = min(incf[t], f[i]);
                if (!st[v]) {
                    q[tt++] = v;
                    if (tt == N) tt = 0;
                    st[v] = 1;
                }
            }
        }
    }
    return incf[T] > 0;
}
inline void ek(int &F, int &C) {
    F = C = 0;
    while (spfa()) {
        int tt = incf[T];
        F += tt, C += tt * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1]) f[pre[i]] -= tt, f[pre[i] ^ 1] += tt;
    }
}
inline void ek(int &F, int &C, int k) {
    F = C = 0;
    while (k-- && spfa()) {
        int tt = incf[T];
        F += tt, C += tt * d[T];
        for (int i = T; i != S; i = e[pre[i] ^ 1]) f[pre[i]] -= tt, f[pre[i] ^ 1] += tt;
    }
}
}

int a[N], id[N], vis[N];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, k, idx = 0; cin >> n >> k;
    for (int i = 0; i < (1 << n); ++i) cin >> a[i];
    k = min(k, (1ll << n) / 2);
    memset(MCMF::hhh, -1, sizeof MCMF::hhh);
    vector<tuple<signed, signed, int>> e;
    for (int i = 0; i < (1 << n); ++i) if (!__builtin_parity(i))
        for (int j = 0; j < n; ++j) e.emplace_back(a[i] + a[i ^ (1 << j)], i, i ^ (1 << j));
    int m = min<int>(e.size(), k * (2 * n - 1) + 1);
    sort(e.begin(), e.end(), greater<>()), e.resize(m);
    memset(id, -1, sizeof id);
    for (auto &[w, u, v] : e) {
        if (!~id[u]) id[u] = idx++;
        if (!~id[v]) id[v] = idx++;
    }
    MCMF::S = N - 1, MCMF::T = N - 2;
    for (auto &[w, x, y] : e) {
        int u = id[x], v = id[y];
        MCMF::ae(u, v, 1, -w);
        if (!vis[u]) MCMF::ae(MCMF::S, u, 1, 0), vis[u] = 1;
        if (!vis[v]) MCMF::ae(v, MCMF::T, 1, 0), vis[v] = 1;
    }
    int F, C; MCMF::ek(F, C, k);
    cout << -C << '\n';
}

} // namespace lowspeed_song

:::

难度：紫

鲜活指数：8

154. P14170 二分图最大匹配期望

:::info[Description] Link. :::

:::info[Solution]{open} 先回顾一下 Hall 定理：

对一张二分图 G 而言，设其左部点集合为 V_1，右部点集合为 V_2，则其存在大小为 |V_1| 的最大匹配当且仅当 \forall S\subseteq V_1\Longrightarrow |S|\le |N(S)|。

这里给出 Hall 定理的一个推论；

对一张二分图 G，设其左部点集合为 V_1，右部点集合为 V_2，则其最大匹配大小为 |V_1|-\max\limits_{S\subseteq V_1}(|S|-|N(S)|)。

对一个左部点集合 S，考虑记 v(S)=|S|-|N(S)|，则上面的最大匹配大小可以被表示为 |V_1|-\max\limits_{S\subseteq V_1}v(S)，因此问题可以被转化为求 \max\limits_{S\subseteq V_1}v(S) 的期望值是多少。

考虑对一个二分图，记这个二分图的好集合为其左部点集合的所有子集中，满足 \max\limits_{S\subseteq V_1}v(S)=v(S) 的集合 S。然后再定义极好集合为该二分图的所有好集合中，大小最小的集合。可以证明对任意二分图，都恰好存在一个极好集合。具体的：若两个不同的集合 A,B 都是极好集合，则其交集 A\cap B 也必然是极好集合，而显然有 |A\cap B|\le\min(|A|,|B|)。

然后考虑 dp。设 f_{S,T} 表示只考虑 S,T 两个点集内的点，以及一端在 S 集合内一端在 T 集合内的边时，把这张图看作是一个以 S 集合为左部点，T 集合为右部点的二分图中，若 S 集合的邻域恰好为 T 集合，而且存在一个匹配使得 S 集合中所有点都能匹配到 T 集合中的不同点的概率是多少；g_{S,T} 表示在上面的条件下，S 集合是该生成二分图的极好集合的概率是多少。

初始条件显然是 f_{0,0}=g_{0,0}=1。

为了方便转移，这里记 all_{S,T} 表示在上面的条件下，T 集合中的每个点都至少被 S 集合中某个点连到的概率是多少；noth_{S,T} 表示在上面的条件下，T 集合中的每个点都无法被 S 集合中的任意一个点连到的概率是多少。这两个东西是好处理的。具体来说：

然后考虑转移 f,g 两个 dp 数组。

先考虑第一个条件：S 点集的邻域恰好为 T，概率显然是 all_{S,T}。然后考虑容斥算不合法概率，如果某张图不能把 S 完全匹配，则其必然满足 \max\limits_{S'\subseteq S}v(S')\neq 0。取该左部点集唯一的极好集合 A\subseteq S 然后再设 B\subseteq T 是 A 集合的邻域，则此时一定有 |A|>|B|。A 是左部点集唯一的极好集合的概率就是 g_{A,B}，然后还需要保证 B 集合是 A 集合的完整邻域，所以 A 集合不能有边连向 T\backslash B，概率就是 noth_{A,T\backslash B}。删掉 A,B 两个点集后，剩下的部分 S\backslash A 必须能完全匹配到 T\backslash B，所以还需要额外乘 f_{S\backslash A,T\backslash B}。

总结一下，f 数组的转移就是 f_{S,T}=all_{S,T}-\sum\limits_{A,B}g_{A,B}\times f_{S\backslash A,T\backslash B}\times noth_{A,T\backslash B}，限制条件是 A\subseteq S,B\subseteq T,|A|>|B|。

然后考虑转移 g 数组。同样先从邻域恰好为 T 的图开始，也就是 all_{S,T}。同样考虑容斥，如果 S 集合不是极好集合，则说明其一定存在一个真子集 A\subset S 为极好集合。设 A 集合的邻域为 B，则为了让 S 不是极好集合，必须有 |A|-|B|\ge d。确定 A,B 两个集合后，同样还是分开算贡献，A 集合成为极好集合的概率为 g_{A,B}，然后 A 集合不能有边连向 T\backslash B，概率为 noth_{A,T\backslash B}，剩下的 S\backslash A 必须能够完全匹配到 T\backslash B 所以还需要额外乘 f_{S\backslash A,T\backslash B}。

总结一下，g 数组的转移就是 g_{S,T}=all_{S,T}-\sum\limits_{A,B}g_{A,B}\times f_{S\backslash A,T\backslash B}\times noth_{A,T\backslash B}，不一样的地方是限制条件为 A\subset S,B\subseteq T,|A-|B|\ge |S|-|T|。

转移这两个数组的时候直接一起转移即可。

最后考虑怎么统计答案。设整张图的极好集合为 S，S 集合在整张图中的邻域集合为 T，则此时 \max\limits_{S'\subseteq S}v(S)=|S|-|T| 因此该图的最大匹配大小就是 n-|S|+|T|。为了保证 S 在整张图上的邻域恰好还是 T 集合，需要保证 S 集合不连向 U_R\backslash T 集合，因此概率需要乘 noth_{S,U_R\backslash T}。然后考虑剩下的左部点部分 U_L\backslash S，她们必须能够值用二分图右部点中的剩余点 U_R\backslash T 来完全匹配。一位内不知道具体连到了哪些剩余的右部点，因此考虑再次枚举这个邻域 T'\subseteq U_R\backslash T。这个部分邻域恰好为 T' 且能够完全匹配的概率是 f_{U_L\backslash S,T'}，同时还需要保证这些点都不连向集合 U_R\backslash T\backslash T' 因此还需要额外乘以 noth_{U_L\backslash S,U_R\backslash T\backslash T'}。

总结一下，这一类二分图度对答案的贡献可以表示为 g_{S,T}\times noth_{S,U_R\backslash T}\times f_{U_L\backslash S,T'}\times noth_{U_L\backslash S,U_R\backslash T\backslash T'}\times (n-|S|+|T|)。枚举所有的集合 S,T,T' 然后把所有贡献相加即可得到最终的答案。

:::success[Code]

namespace lowspeed_song {

inline void init() {
}

int p[610][610], tmp[610][610], all[610][610], noth[610][610], cnt[610], f[610][610], g[610][610];

inline void sol([[maybe_unused]]int __testcase_id) {
    int n, m; cin >> n >> m;
    const int inv100 = inversion(100);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) cin >> p[i][j], p[i][j] = p[i][j] * inv100 % mod;
    for (int i = 0; i < n; i++) {
        tmp[i][0] = 1;
        for (int t = 1; t < (1 << m); ++t) {
            int j = __builtin_ctz(t);
            tmp[i][t] = tmp[i][t ^ (1 << j)] * (1 - p[i][j] + mod) % mod;
        }
    }
    for (int t = 0; t < (1 << m); ++t) noth[0][t] = 1;
    for (int s = 1; s < (1 << n); ++s) {
        int i = __builtin_ctz(s), pre = s ^ (1 << i);
        for (int t = 0; t < (1 << m); ++t) noth[s][t] = noth[pre][t] * tmp[i][t] % mod;
    }
    for (int s = 0; s < (1 << n); ++s) {
        all[s][0] = 1;
        for (int t = 1; t < (1 << m); ++t) {
            all[s][t] = 1;
            for (int S = t; S; S = (S - 1) & t) all[s][t] = (all[s][t] + mod - all[s][t ^ S] * noth[s][S] % mod) % mod;
        }
    }
    for (int s = 0; s < (1 << n); ++s)
        for (int t = 0; t < (1 << m); ++t) f[s][t] = g[s][t] = 0;
    f[0][0] = g[0][0] = 1;
    for (int s = 1; s < (1 << n); ++s) {
        for (int t = 0; t < (1 << m); ++t) {
            if (__builtin_popcount(s) > __builtin_popcount(t)) {
                g[s][t] = all[s][t];
                for (int a = (s - 1) & s; ; a = (a - 1) & s) {
                    for (int b = t; ; b = (b - 1) & t) {
                        if (__builtin_popcount(a) - __builtin_popcount(b) >= __builtin_popcount(s) - __builtin_popcount(t)) g[s][t] = (g[s][t] + mod - g[a][b] * f[s ^ a][t ^ b] % mod * noth[a][t ^ b] % mod) % mod;
                        if (!b) break;
                    } if (!a) break;
                }
            } else {
                f[s][t] = all[s][t];
                for (int a = s; a; a = (a - 1) & s)
                    for (int b = t; ; b = (b - 1) & t) {
                        if (__builtin_popcount(a) > __builtin_popcount(b)) f[s][t] = (f[s][t] + mod - g[a][b] * f[s ^ a][t ^ b] % mod * noth[a][t ^ b] % mod) % mod;
                        if (!b) break;
                    }
            }
        }
    }
    int res = 0;
    for (int s = 0; s < (1 << n); ++s)
        for (int t = 0; t < (1 << m); ++t)
            for (int t0 = (((1 << m) - 1) ^ t);; t0 = (t0 - 1) & (((1 << m) - 1) ^ t)) {
                res = (res + g[s][t] * noth[s][(((1 << m) - 1) ^ t)] % mod * f[((1 << n) - 1) ^ s][t0] % mod * noth[((1 << n) - 1) ^ s][(((1 << m) - 1) ^ t) ^ t0] % mod * (n - __builtin_popcount(s) + __builtin_popcount(t)) % mod) % mod;
                if (!t0) break;
            }
    cout << res << '\n';
}

} // namespace lowspeed_song

:::