自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:45:58，当前版本为作者最后更新于2023-04-12 20:37:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9167 [省选联考 2023] 城市建造

因为选择的城市数等于连通块数，所以每个连通块恰选择一个城市，否则无法连通。

先在不考虑连通块大小的限制下，探究合法的充要条件。

性质和结论

对于选择的两个城市，如果存在一条不经过重复点的简单路径连接它们，则路径上的每个点都要选择。否则，必然存在某两个选择的城市连通。

相反，如果满足条件，将选择的城市之间的边删去后，这些城市两两不连通。可以反证。

因此，根据点双的性质，如果一个点双里面选了两个点，则整个点双都要被选择。

建出圆方树，称选择一个方点表示选择其周围的所有圆点，要求：

• 为保证选择的城市不连通，选择的方点是一个连通块。即若两个方点被选择，则它们简单路径上的所有方点均被选择。
• 删去选择的方点（相当于删去选择城市之间的边）后，每个连通块大小（圆点数量）相差不超过 $k$。

$\boldsymbol{k = 0}$

考虑 $k = 0$，则连通块大小 $d$ 为 $n$ 的因数。

考虑以重心 $R$ 为根，则若一个方点被选择，其祖先方点一定被选择，且若 $R$ 为方点，则 $R$ 一定被选择。可以反证。

树形 DP，能剥子树就剥子树。设 $f_i$ 表示：若 $i$ 是圆点，能否删去其父亲方点（若 $i$ 为根，则答案可以视为添加并强制删去 $i$ 的父亲方点时整棵子树的答案）；若 $i$ 是方点，能否删去其本身。$f_R$ 即为所求。

• 对于圆点 $i$，枚举所有子结点 $j$（方点）。当 $sz_j \geq d$ 时，要求 $f_j = 1$。否则 $j$ 不能被删去，因此要求 $sz_j < d$ 的 $sz_j$ 之和恰等于 $d$。
• 对于方点 $i$，$f_i = 1$ 当且仅当其所有子结点 $j$ 的 $f_j = 1$。

$\boldsymbol{k = 1}$

考虑 $k = 1$，枚举连通块大小 $d = 1\sim \lfloor \frac n 2\rfloor$，则 $k = 0$ 的 $2\sim \lfloor \frac n 2\rfloor$ 多算了，要减掉（因为 $n\geq 3$，所以 $k = 0$ 的 $\lfloor \frac n 2\rfloor + 1$ 一定不合法）。

类似地，设 $f_i$ 表示对应方案数，$f_R$ 即为所求。

• 对于圆点 $i$：

  • 若 $sz_j < d$，则 $j$ 不能被删去。
  • 若 $sz_j > d$，则 $j$ 必须被删去。
  • 否则 $sz_j = d$。当 $f_j = 0$ 时，$j$ 不能被删去。否则 $j$ 可以被删去，也可以不删去，但后者要求不存在不能被删去的 $j$ 且其它 $j$ 均被删去。

  设 $ss$ 为不能被删去的 $\sum sz_j$ 加上 $i$ 本身贡献的 $1$ 表示 $i$ 的连通块大小最小值，设 $pd$ 为可以被删去的 $\prod f_j$：

  • 若 $ss > d + 1$，$f_i = 0$。
  • 若 $d\leq ss\leq d + 1$，则 $f_i$ 加上 $pd$。
  • 若 $ss = 1$，则 $f_i$ 加上对每个可以被删去的 $sz_j = d$，$\frac {pd} {f_j}$ 之和。因为 $sz_j = d$ 且 $f_j > 0$ 时 $f_j = 1$，故 $\sum \frac {pd} {f_j}$ 等于 $pd$ 乘以 $sz_j = d$ 且 $f_j > 0$ 的 $j$ 的数量 $cnt$。

  注意第二、三个条件可以同时满足。

• 对于方点 $i$，$f_i$ 等于 $\prod f_j$。

$k = 0$ 的复杂度为 $\mathcal{O}(nd(n))$，$k = 1$ 的复杂度为 $\mathcal{O}(n ^ 2)$。

枚举选择的城市数量，发现只有整除值或整除值 $-1$ 可能成为答案（等价于 $n\bmod l \leq \frac n l$ 的 $l$ 的数量），复杂度降为 $\mathcal{O}(n ^ {1.5})$。加入部分剪枝后以非常快的速度通过（若 $sz_j > d$ 且 $f_j = 0$ 则无解，若 $sz_j < d$ 则不用递归）。

#include <bits/stdc++.h>
using namespace std;

constexpr int N = 2e5 + 5;
constexpr int mod = 998244353;
void add(int &x, int y) {
  x += y, x >= mod && (x -= mod);
}

int n, m, k, ans, node;
vector<int> e[N], g[N], h[N];
int dn, dfn[N], low[N], stc[N], top;
void tarjan(int id) {
  low[id] = dfn[id] = ++dn, stc[++top] = id;
  for(int it : e[id]) {
    if(!dfn[it]) {
      tarjan(it);
      low[id] = min(low[id], low[it]);
      if(low[it] >= dfn[id]) {
        g[++node].push_back(id);
        g[id].push_back(node);
        for(int x = 0; x != it; ) {
          x = stc[top--];
          g[node].push_back(x);
          g[x].push_back(node);
        }
      }
    }
    else low[id] = min(low[id], dfn[it]);
  }
}

int R, mx[N], sz[N];
void findroot(int id, int ff) {
  sz[id] = id <= n;
  for(int it : g[id]) {
    if(it == ff) continue;
    findroot(it, id);
    sz[id] += sz[it];
    mx[id] = max(mx[id], sz[it]);
  }
  mx[id] = max(mx[id], n - sz[id]);
  if(id <= n && mx[id] < mx[R]) R = id;
}

int pos, fa[N], mn[N], ind[N];
void dfs(int id, int ff) {
  ind[++pos] = id;
  mn[id] = N, fa[id] = ff, sz[id] = id <= n;
  for(int it : g[id]) {
    if(it == ff) continue;
    dfs(it, id), sz[id] += sz[it];
    mn[id] = min(mn[id], sz[it]);
    h[id].push_back(it);
  }
}

int f[N];
void dfs2(int id, int x) {
  for(int i = node; i; i--) {
    int id = ind[i], cnt = 0;
    if(sz[id] < x) continue;
    if(id <= n) {
      f[id] = 0;
      int tot = 1, prod = 1;
      for(int i = 1; i <= h[id].size(); i++) {
        int it = h[id][i - 1];
        if(sz[it] < x) tot += sz[it];
        if(sz[it] == x) f[it] ? cnt++ : tot += x;
        if(sz[it] > x) prod = 1ll * prod * f[it] % mod;
      }
      if(x <= tot && tot <= x + 1) f[id] = prod;
      if(tot == 1) f[id] = (f[id] + 1ll * prod * cnt) % mod;
    }
    else {
      f[id] = 1;
      for(int it : h[id]) {
        if(sz[it] < x) {
          f[id] = 0;
          break;
        }
        f[id] = 1ll * f[id] * f[it] % mod;
      }
    }
    if(sz[id] > x + 1 && f[id] == 0) {
      f[R] = 0;
      break;
    }
  }
}
void dfs3(int id, int x) {
  for(int i = node; i; i--) {
    int id = ind[i];
    if(sz[id] < x) continue;
    if(id <= n) {
      f[id] = 0;
      int tot = 1, ok = 1;
      for(int it : h[id]) {
        if(sz[it] < x) tot += sz[it];
        else if(!f[it]) ok = 0;
      }
      f[id] = tot == x && ok;
    }
    else {
      f[id] = 1;
      for(int it : h[id]) {
        if(sz[it] < x) f[id] = 0;
        else if(!f[it]) f[id] = 0;
      }
    }
    if(sz[id] > x + 1 && f[id] == 0) {
      f[R] = 0;
      break;
    }
  }
}
int check(int x, int k) {
  if(k == 0 && n % x) return 0;
  k == 1 ? dfs2(R, x) : dfs3(R, x);
  int res = f[R];
  if(k == 1) res = (res - check(x + 1, 0) + mod) % mod;
  return res;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> m >> k, node = n;
  for(int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }

  tarjan(1);

  mx[0] = N, findroot(1, 0), dfs(R, 0);
  static bool vis[N];
  for(int i = 2; i <= n; i++) {
    vis[n / i] = 1;
    if(n % i == 0) vis[n / i - 1] = 1;
  }
  for(int l = 1; l <= n / 2; l++) {
    if(!vis[l]) continue;
    ans = (ans + check(l, k)) % mod;
  }
  cout << ans << "\n";

  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}
/*
g++ cities.cpp -o cities -std=c++14 -O2
*/

线性做法

考虑同时 DP 所有 $d$，用哈希表维护有值的位置 $f_{i, d}$。

• 对于方点，合并子结点的复杂度不超过子结点哈希表大小之和。

• 对于圆点，按子树大小从小到大排序，则只有 $1$ 或子树大小前缀和或子树大小前缀和 $+1$ 可能合法。预处理子树大小前缀和。计算 $f_{i, d}$ 时，从后往前枚举。

  • 若 $sz_j < d$ 则不用继续枚举，直接给 $ss$ 加上子树大小前缀和。
  • 若 $sz_j > d$ 则将 $pd$ 乘以 $f_{j, d}$，若 $f_{j, d} = 0$ 则直接退出。
  • 若 $sz_j = d$ 且 $f_{j, d} = 1$，则给 $cnt$ 加 $1$。
  • 若 $sz_j = d$ 且 $f_{j, d} = 0$，则给 $ss$ 加 $d$，这样的 $j$ 最多只能有 $1$ 个。

  可知圆点的哈希表大小不超过其度数，且计算 $f_{i, d}$ 的总复杂度不超过子结点的哈希表大小之和。

除去按子树大小排序外，复杂度为 $\mathcal{O}(n)$。甚至跑不过 $\mathcal{O}(n ^ {1.5})$。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

bool Mbe;
constexpr int N = 2e5 + 5;
constexpr int mod = 998244353;
void add(int &x, int y) {
  x += y, x >= mod && (x -= mod);
}

vector<int> e[N], g[N], son[N];
int node, dn, dfn[N], low[N], stc[N], top;
void tarjan(int id) {
  dfn[id] = low[id] = ++dn;
  stc[++top] = id;
  for(int it : e[id]) {
    if(!dfn[it]) {
      tarjan(it);
      low[id] = min(low[id], low[it]);
      if(low[it] >= dfn[id]) {
        g[++node].push_back(id);
        g[id].push_back(node);
        for(int x = 0; x != it; ) {
          g[node].push_back(x = stc[top--]);
          g[x].push_back(node);
        }
      }
    }
    else low[id] = min(low[id], dfn[it]);
  }
}

int n, m, k;
int R, sz[N], mx[N];
void dfs(int id, int ff) {
  sz[id] = id <= n;
  for(int it : g[id]) {
    if(it == ff) continue;
    dfs(it, id), sz[id] += sz[it];
    mx[id] = max(mx[id], sz[it]);
  }
  mx[id] = max(mx[id], n - sz[id]);
  if(mx[id] < mx[R]) R = id;
}

int ss[N];
unordered_map<int, int> f[N];
int calc() {
  int ans = 0;
  for(auto it : f[R]) {
    if(it.first * 2 <= n) add(ans, it.second);
  }
  return ans;
}
void merge(int x, int y) {
  unordered_map<int, int> nw;
  for(auto it : f[x]) {
    auto pt = f[y].find(it.first);
    if(pt != f[y].end()) nw[it.first] = 1ll * it.second * pt->second % mod;
  }
  f[x] = nw;
}

void dfs0(int id, int ff) {
  for(int it : g[id]) {
    if(it == ff) continue;
    dfs0(it, id), son[id].push_back(it);
  }
  sort(son[id].begin(), son[id].end(), [&](int x, int y) {
    return sz[x] < sz[y];
  });
  int E = son[id].size();
  if(id <= n) {
    for(int i = 1; i <= E; i++) ss[i] = ss[i - 1] + sz[son[id][i - 1]];
    auto update = [&](int x) {
      for(int i = E; i; i--) {
        int it = son[id][i - 1];
        if(sz[it] >= x) {
          auto pt = f[it].find(x);
          if(pt == f[it].end()) return;
          continue;
        }
        if(ss[i] + 1 != x) return;
        break;
      }
      f[id][x] = 1;
    };
    for(int i = 0; i <= E; i++) update(ss[i] + 1);
  }
  else {
    f[id] = f[son[id][0]];
    for(int i = 1; i < E; i++) merge(id, son[id][i]);
  }
}
void dfs1(int id, int ff) {
  for(int it : g[id]) {
    if(it == ff) continue;
    dfs1(it, id);
  }
  int E = son[id].size();
  if(id <= n) {
    for(int i = 1; i <= E; i++) ss[i] = ss[i - 1] + sz[son[id][i - 1]];
    auto update = [&](int x) {
      int prod = 1, size = 1, cnt = 0;
      for(int i = E; i && size <= x + 1; i--) {
        int it = son[id][i - 1];
        if(sz[it] >= x) {
          auto pt = f[it].find(x);
          if(sz[it] >= x + 1) {
            if(pt == f[it].end()) return;
            prod = 1ll * prod * pt->second % mod;
          }
          else {
            if(pt == f[it].end()) size += sz[it];
            else cnt++;
          }
        }
        else {
          size += ss[i];
          break;
        }
      }
      if(size > x + 1) return;
      f[id][x] = 1ll * prod * ((int) (size >= x) + (size == 1 ? cnt : 0)) % mod;
    };
    for(int i = 0; i <= E; i++) {
      if(i && ss[i - 1] + 1 != ss[i]) update(ss[i]);
      update(ss[i] + 1);
    }
  }
  else {
    f[id] = f[son[id][0]];
    for(int i = 1; i < E; i++) merge(id, son[id][i]);
  }
}

bool Med;
int main() {
  fprintf(stderr, "%.4lf\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("cities.in", "r", stdin);
    FILE* OUT = freopen("cities.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

  cin >> n >> m >> k, node = n;
  for(int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  tarjan(1);
  mx[0] = N, dfs(1, 0), dfs(R, 0);
  dfs0(R, 0);
  int ans = calc();
  if(k == 0) cout << calc() << "\n", exit(0);
  ans = mod - ans + 1, dfs1(R, 0);
  cout << (ans + calc()) % mod << "\n";
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}
/*
g++ cities.cpp -o cities -std=c++14 -O2 -DALEX_WEI
*/

ymx 有一个除并查集外线性的妙妙做法。