题解 P11220 / MX241020D【【MX-S4-T4】「yyOI R2」youyou 的三进制数】

好长的标题

题目描述

现在有 \(0 \sim n\) 共 \(n + 1\) 个数。
定义 \((x)_{3}\) 表示十进制数 \(x\) 的三进制形式。如果没有特别强调，那么这些数均为十进制形式。

youyou 想构造一个序列长度为 \(p\)（\(p \ge 1\)）的非负整数序列 \(a\)。使之满足：

• \(a_i \in [0,n]\)。
• 不存在 \(i,j\)（\(1 \le i <j \le p\)），使得 \(a_i = a_j\)。
• 对于任意 \(1 \le i < n\)，\(a_i\) 与 \(a_{i+1}\) 至少满足以下四个条件中的一个：
  1. \((a_i)_3\) 去掉最后一位，恰好等于 \((a_{i+1})_3\)（若只有一位，则去掉后的数字为 \(0\)）。
  2. 在 \((a_i)_3\) 末尾添上某一位 \(t(0 \le t \le 2)\)，恰好等于 \((a_{i+1})_3\)（若 \(a_i = 0\)，则添加后舍去前置 \(0\)）。
  3. \(a_i \le w\)， \((a_i)_3\) 的末尾不是 \(0\)，且将末尾的一位数字移到开头与 \((a_{i + 1})_3\) 相等。
  4. 当 \((a_i)_3\) 长度 \(\ge 2\)，且 \((a_i)_3\) 次高位非零时，将 \((a_i)_3\) 开头的一位数字移到末尾，形成的数的十进制值 \(\le w\)，且恰好等于 \((a_{i+1})_3\)。

这样的序列 \(a\) 被称为“完美的”。

youyou 认为，如果十进制三元组 \((x,y,z)\) 是好的，必须满足以下条件：

• \(0 \le x,y,z \le n\)，\(x \neq y\)。
• 存在至少一个”完美的“序列 \(b\)，使得十进制下有 \(b_1=x\)，\(b_s = y\)。其中 \(s\) 为序列长度。
• 存在至少一个”完美的”序列 \(c\)，使得十进制下有 \(c_1=z\)。同时，对于上述任意的 \(b\)，均有恰好一对 \((i, j)\)，满足 \(1 \le i \le |b|\)，\(1 \le j \le |c|\)，使得 \(b_i = c_j\)。

对于每一个 \(0 \le z \le n\)，求能构成“好的”三元组 \((x,y,z)\) 的有序对 \((x,y)\) 的个数。

\(w\leq n\leq 3\times 10^5\)。

solution

发现题目中的四个条件，第一条和第二条是对称的，第三条和第四条仔细看也是对称的。结合下文需要固定序列的首项和末项，我们不难想到：构造一个 \(n+1\) 个点的无向图，标号 \(0\sim n\)，其中点 \(i\) 与 \(3i, 3i+1, 3i+2\) 有边，\(i\leq w\) 时还和“将 \(i\) 末尾的一位数字移到开头”形成的数之间有边，注意以上点的标号如果超过 \(n\) 则不用连。

则需要计数的对象可以转写为：对于 \((x, y, z)\)，需要满足 \(x, y\) 之间有一条简单路径（可以发现图是连通的，这样的路径必然存在），且存在一条从 \(z\) 出发的路径，使得 \(x, y\) 之间的任意简单路径都与这条路径有交，也就是说：存在一条从 \(z\) 出发的路径，其上恰有一个点是任何 \(x\) 到 \(y\) 的简单路径的必经点，其余点都不能出现在任何 \(x\) 到 \(y\) 的简单路径上（容易发现这是充要的）。

不妨提取每个点双连通分量为一个方点带一堆圆点，建立圆方树。则又可以将计数对象转写为：\(x, y\) 在圆方树上的路径上离 \(z\) 最近的点必须是一个圆点。

由此可以尝试计算答案。记 \(x, y\) 在圆方树上的路径上离 \(z\) 最近的点为 \(u\)，在为圆点的 \(u\) 上统计答案。枚举每条出边，计算删去这条出边指出的子树后有多少条路径经过 \(u\)，这些路径都能贡献到这棵子树中的所有点。可以求出 dfn 序，在 dfn 序上进行区间加，使用差分维护。计算路径条数则可以先计算全局有多少路径经过 \(u\)，枚举出边后再删去对应多算的路径。

至此本题可以在 \(O(n\log n)\) 的时间复杂度内完成，瓶颈在建图（迫真）。

code

#include <bits/stdc++.h>
using namespace std;
#define link b426058e
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
int n, w, tot, siz[600010], sz[600010];
basic_string<int> g[300010], t[600010];
void link(int u, int v) {
  if (++u != ++v) g[u] += v, g[v] += u, debug("%d %d\n", u, v);
}
int dfn[600010], low[300010], stk[300010], top, cnt;
void tarjan(int u) {// {{{
  dfn[u] = low[u] = ++cnt, stk[++top] = u;
  for (int v : g[u]) {
    if (dfn[v]) low[u] = min(low[u], dfn[v]);
    else {
      tarjan(v);
      low[u] = min(low[u], low[v]);
      if (low[v] >= dfn[u]) {
        int p = ++tot;
        t[p] += u, t[u] += p, debug("%d %d\n", u, p);
        do t[p] += stk[top], t[stk[top]] += p, debug("%d %d\n", p, stk[top]); while (stk[top--] != v); 
      }
    }
  }
}// }}}
LL c[600010];
void dfs(int u, int fa) {
  siz[u] = u <= n, dfn[u] = ++cnt, sz[u] = 1;
  for (int v : t[u]) if (v != fa) dfs(v, u), siz[u] += siz[v], sz[u] += sz[v];
  if (u <= n) {
    LL num = n;
    for (int v : t[u]) if (v != fa) num += 1ll * siz[v] * (n - siz[v]);
    int fsiz = n - siz[u];
    num += 1ll * fsiz * (n - fsiz);
    c[dfn[u]] += num, c[dfn[u] + 1] -= num;
    debug("ans[%d] += %lld\n", u, num);
    for (int v : t[u]) if (v != fa) {
      LL val = num - 2ll * siz[v] * (n - siz[v]);
      c[dfn[v]] += val, c[dfn[v] + sz[v]] -= val;
      debug("ans[subtree(%d)] += %lld\n", v, val);
    }
    LL fval = num - 2ll * fsiz * (n - fsiz);
    c[1] += fval, c[dfn[u]] -= fval, c[dfn[u] + sz[u]] += fval;
    debug("ans[!subtree(%d)] += %lld\n", u, fval);
  }
}
int main() {
#ifndef LOCAL
#ifdef NF
  freopen("ternary.in", "r", stdin);
  freopen("ternary.out", "w", stdout);
#endif
  cin.tie(nullptr)->sync_with_stdio(false);
#endif
  cin >> n >> w;
  for (int i = 0; i <= n; i++) {
    link(i, i / 3);
    if (i % 3 && i <= w) {
      vector<int> dit;
      for (int x = i; x; x /= 3) dit.push_back(x % 3);
      int x = 0;
      x = x * 3 + dit[0];
      for (int i = (int)dit.size() - 1; i >= 1; i--) x = x * 3 + dit[i];
      if (x <= n) link(i, x);
    }
  }
  debug("===\n");
  tot = ++n, tarjan(1), cnt = 0, dfs(1, 0);
  for (int i = 1; i <= cnt; i++) c[i] += c[i - 1];
  for (int i = 1; i <= n; i++) cout << c[dfn[i]] - n << endl;
  return 0;
}

吐槽一下样例，怎么搞的，样例一是树，样例二直接飞升到 \(222\) 个点，怎么调啊？！