2024-02-14 模拟赛补题

考场上写出：

if (sub1 :: check()) sub2 :: solve();

这个sb操作直接少 60pts。

T1. 脐

题意

给定一个长度为 $n$ 的排列 $p$，求有多少棵树满足：

$\forall 1 \le i < j \le n$，如果树中存在边 $(i, j)$，那么一定存在边 $(p_i, p_j)$。

答案对 $998244353$ 取模。

$1 \le n \le 2 \times 10^6$。

题解

不会。

T2. 最初日

题意

给定一个 $n \times n$ 的矩阵 $a$，每行每列都是 $1 \sim n$ 的排列。

你要选出 $n$ 个格子，满足每行每列都只有一个格子被选中。设 $r_i$ 是第 $i$ 行被选中的格子的元素，$c_i$ 是 $i$ 列被选中的格子的元素。要求你选的格子满足，$\forall 1 \le i, j \le n$，有 $(a_{i, j} - r_i) \cdot (a_{i, j} - c_j) \ge 0$ 成立。

每个格子有一个权值 $c_{i, j}$ ( $c_{i, j} \in \{0, 1\}$ )，求出合法方案中选出格子的权值和的最大值。

$2 \le n \le 128$，保证存在合法方案。

题解

这种题目看起来很网络流，考虑网络流。

考虑转化一下这个限制，原题的限制是：

$$\begin{cases} a_{i, j} \ge r_i & a_{i, j} \ge c_j \\ a_{i, j} \le r_i & a_{i, j} \le c_j \end{cases}$$

合法的方案满足：要么第一行全部成立，要么第二行全部成立。现在我们转化一下，变成：

$$\begin{cases} a_{i, j} \ge r_i & a_{i, j} \le c_j \\ a_{i, j} \le r_i & a_{i, j} \ge c_j \end{cases}$$

这样的话，限制就是：第一行至少成立一个，并且第二行至少成立一个。（注意这里是至少）

这种限制的特征让我们想到最小割，这里的最小割假设是在割点（不是割边），那么一个点如果被割了就说明这个点被合法方案选中了。

这样就可以引出我们的建图方式了：

• 建立虚拟源汇点 $S, T$。
• $S$ 连接所有 $a_{i, j} = 1$ 的点，$T$ 连接所有 $a_{i, j} = n$ 的点，流量均为 $+ \infty_{\max}$。
• 对于一个点 $(i, j)$ ( $1 < a_{i, j} < n$ )，连接第 $i$ 行 $a_{i, k} = a_{i, j} + 1$ 的点 $(i, k)$，并连接第 $j$ 列 $a_{p, j} = a_{i, j} + 1$ 的点。流量均为 $+ \infty_{\max}$。
• 把点 $(i, j)$ 的权值设为 $\infty_{\min} - c_{i, j}$（这里还是在割点）。

这里的 $\infty_{\max}$ 与 $\infty_{\min}$ 代表的都是正无穷，但是 $\infty_{\min}$ 要小得多，原因是你在割点，是没有办法割边的。

最后用 $n \times \infty_{\min}$ 减去最小割就是答案。

对于这种建图的解释：

考虑最小割会割掉哪些点，不妨这样考虑，对于一个点 $(i, j)$，$S \to T$ 的路径中有两种方式会经过它，要么是：

1. 先经过第 $i$ 行上权值 $\le a_{i, j}$ 的点，再经过第 $j$ 列上权值 $\ge a_{i, j}$ 的点。
2. 先经过第 $j$ 列上权值 $\le a_{i, j}$ 的点，再经过第 $i$ 行上权值 $\ge a_{i, j}$ 的点。

这样割掉了这两种路径后，就与上面的限制等价了。

而又由于是最小割，我们割的点的点权限制非常巧妙。题目要求只选 $n$ 个点，又可以发现网络图中最少割 $n$ 个点。将流量设为 $\infty_{\min}$ 使得会优先满足割的点最少，然后再满足点权最小。

代码

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
const int K = 260, N = K * K, M = N << 4;
const int inf = 1E9, INF = 1E15;
int n, m;
struct flow {
  int head[N], nex[M << 1], tot = 1, cur[N], dep[N];
  int SN, S, T;
  struct E {int to, nxt, flow;} edge[M << 1];
  void ad(int x, int y, int w) {
    edge[++tot] = (E) {x, y, w};
    nex[tot] = head[x]; head[x] = tot;
  }
  void add(int x, int y, int w) {
    ad(x, y, w);
    ad(y, x, 0);
  }
  bool bfs() {
    fill(dep + 1, dep + 1 + SN, 0);
    queue <int> q; q.emplace(S);
    dep[S] = 1; while (!q.empty()) {
      int u = q.front(); q.pop();
      for (int i = head[u]; i; i = nex[i]) {
        int v = edge[i].nxt, w = edge[i].flow;
        if (w > 0 && !dep[v]) {
          dep[v] = dep[u] + 1;
          q.emplace(v);
        }
      }
    } return dep[T];
  }
  int dfs(int u, int flow) {
    if (u == T || !flow) return flow;
    int res = 0;
    for (int i = cur[u]; i && res < flow; i = nex[i]) {
      cur[u] = i;
      int v = edge[i].nxt, w = edge[i].flow;
      if (w > 0 && dep[v] == dep[u] + 1) {
        int k = dfs(v, min(flow - res, w));
        if (!k) dep[v] = 0;
        else {
          edge[i].flow -= k;
          edge[i ^ 1].flow += k;
          res += k;
        }
      }
    } return res;
  }
  int dinic() {
    int ans = 0;
    while (bfs()) {
      copy(head + 1, head + 1 + SN, cur + 1);
      ans += dfs(S, INF);
    } return ans;
  }
} dc;
int a[K][K], c[K][K], b[K];
int id(int i, int j) {return (i - 1) * n + j;}
int in(int i, int j) {return id(i, j);}
int out(int i, int j) {return in(i, j) + m;}
signed main(void) {
  ios :: sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n; m = n * n;
  dc.S = m * 2 + 1, dc.T = dc.SN = dc.S + 1;
  for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)
    cin >> a[i][j];
  for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j)
    cin >> c[i][j];
  for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) 
    dc.add(in(i, j), out(i, j), inf - c[i][j]);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) b[a[i][j]] = j;
    dc.add(dc.S, in(i, b[1]), INF);
    for (int j = 1; j < n; ++j)
      dc.add(out(i, b[j]), in(i, b[j + 1]), INF);
    dc.add(out(i, b[n]), dc.T, INF);
  }
  for (int j = 1; j <= n; ++j) {
    for (int i = 1; i <= n; ++i) b[a[i][j]] = i;
    dc.add(dc.S, in(b[1], j), INF);
    for (int i = 1; i < n; ++i)
      dc.add(out(b[i], j), in(b[i + 1], j), INF);
    dc.add(out(b[n], j), dc.T, INF);
  }
  int ans = dc.dinic();
  cout << inf * n - ans << '\n';
  return 0;
}

T3. 黑鸟

题意

给定一棵 $n$ 个节点的树，根节点为 $1$，第 $i$ 个点有权值 $A_i$。现在你要对它维护 $4$ 种操作：

• 1 u v，将 $u$ 的父亲改成 $v$。
• 2 u v x，将 $u, v$ 简单路径上点的点权全部改成 $x$。
• 3 u，求 $\textrm{Fib}(A_u)$。
• 4 u v，设从 $u$ 到 $v$ 的简单路径上的点的点权依次是 $B_1, B_2, \cdots, B_k$，求：

$$\sum\limits_{l = 1}^k\sum\limits_{r = l}^k \textrm{Fib}\left(\sum\limits_{p = l}^r B_p\right)$$

其中，$\textrm{Fib}(n)$ 的递推式如下：

$$\textrm{Fib}(n) = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ \textrm{Fib}(n - 1) + \textrm{Fib}(n - 2) & n \ge 2 \end{cases}$$

以上所有运算都在 $\textrm{mod } 998244353$ 意义下进行。

$1 \le n, m \le 10^5$，$A_i, x \le 10^9$。

题解

可以发现这个 $A_i$ 非常大，要用矩阵快速幂求 $\textrm{Fib}(A_u)$，此时：

$$\textrm{Fib}(A_u) = \left(\begin{Bmatrix} 1 & 0 \end{Bmatrix} \times \begin{Bmatrix} 1 & 1 \\ 1 & 0 \end{Bmatrix}^{A_u} \right)_{1, 2}$$

（下面用 $B$ 来代指 $\begin{Bmatrix}1 & 1 \\ 1 & 0\end{Bmatrix}$）

先考虑没有 $1$ 操作时怎么做。很明显可以想到树链剖分。

考虑线段树的节点上维护什么。我们看一下操作 $4$ 是在求什么，在将 $\textrm{Fib}$ 转化成矩阵快速幂后，可以发现现在求的东西变成了：

$$\sum\limits_{l = 1}^k \sum\limits_{r = l}^k \left(\begin{Bmatrix} 1 & 0 \end{Bmatrix} \times B^{\sum\limits_{p = l}^r A_p} \right)$$

由于矩阵乘法有分配律，所以把 $\begin{Bmatrix}1 & 0\end{Bmatrix}$ 提出来，变成：

$$\begin{Bmatrix} 1 & 0 \end{Bmatrix} \times \sum\limits_{l = 1}^k \sum\limits_{r = l}^k B^{\sum\limits_{p = l}^r A_p}$$

线段树上的节点维护的就是后面的东西，也就是所有 子区间的积 的和。

考虑一个 sum 标记表示这个玩意。考虑上传 sum，sum 肯定是左儿子的 sum 加右儿子的 sum 再加上跨过左右儿子的区间对 sum 的贡献。

而跨过左右区间的，可以通过维护前缀积之和和后缀积之和求出，具体地，lb，rb 分别为前后缀的积的和。

$$\begin{cases} lb = \sum\limits_{i = l}^r B^{\sum\limits_{j = l}^i A_j} \\ rb = \sum\limits_{i = l}^r B^{\sum\limits_{j = i}^r A_j} \end{cases}$$

（看不清楚下标可以 Ctrl + 滚轮 放大）

这个 lb，rb 应该很好转移，只需再转移一个区间的积 mul 就行了。然后 sum += ls.rb * rs.lb 就行了。

接着考虑修改，考虑我们维护的 $4$ 个 tag 会怎么变化（设区间全部赋值成 $c$）：

• mul，这个直接快速幂就行了。
• lb，rb，这两个玩意数值是相等的。都会变成：

  $$\sum\limits_{i = l}^r B^{\left(c \cdot (i - l + 1)\right)}$$

  这个式子是等比数列求和，其答案是：

  $$B^c \times \frac{I - B^{c \times (r - l + 1)}}{I - B^c}$$

  这里的 $I$ 是单位矩阵，这里可以直接矩阵求逆得到 $(I - B)^{-1}$。接着就求出来了。
• sum，变成了：

  $$\sum\limits_{k = 1}^{r - l + 1} [(r - l + 1) - k + 1] \times B^{c \cdot k}$$

  可以发现会变的东西只有 $k$，其它都是常数，也就是：

  $$(r - l + 1) \times (r - l + 2) \times \sum\limits_{k = 1}^{r - l + 1} B^{c \cdot k} - \sum\limits_{k = 1}^{r - l + 1} k \times B^{c \cdot k}$$

  只需要求出 $\sum\limits_{k = 1}^{r - l + 1} B^{c \cdot k}$ 和 $\sum\limits_{k = 1}^{r - l + 1} k \cdot B^{c \cdot k}$。前者就等于 lb 和 rb ，后者可以转化一下：

  $$\begin{cases} \begin{aligned} S &= \sum\limits_{k = 1}^{r - l + 1}B^{c \cdot k} \\ B^c \cdot S &= \sum\limits_{k = 1}^{r - l + 1}B^{c \cdot (k + 1)} \\ (I - B^c) \cdot S &= \sum\limits_{k = 1}^{r - l + 1} B^{c \cdot k} - (r - l + 1) \times B^{c \cdot (r - l + 2)} \end{aligned} \end{cases}$$

  这样 sum 就可以算了，所以 sum 也转移完了。

最后把树剖换成 LCT 就可以通过该题了。时间复杂度 $\mathcal{O}(n \log n \log V)$

顺便一提，数据非常水。所有数据中树的直径最大为 $50$，这导致暴力直接成为最优解（因为暴力复杂度少个 $\log V$）。