2025.5.23 【ZR NOI模拟赛 T3】高速公路 题解（容斥，高维前缀和，性质）

非常牛的题，记录一下思路。

传送门

题意

有一张 $n$ 个点的无向图，每个点有一个颜色 $c_i$，满足 $c_i\in [1,k]$。

图是由 $m$ 条链组成，满足任意一个点恰好只在一条链上。对于一条链上的第 $i$ 个点和第 $j$ 个点，从 $i$ 沿着链走到 $j$ 的花费为 $|i-j|$。

若两个点 $x,y$ 满足 $c_x=c_y$，那么可以花费 $1$ 代价从 $x$ 移动到 $y$。

定义 $dis(x,y)$ 为从 $x$ 移动到 $y$ 的最小花费。给定图的形态和每个点的颜色，求：

$$\sum _{1\le x<y\le n}dis(x,y)$$

$1\le n\le 10^6,1\le k\le 20$，保证所有点对都能相互到达。

分析：

由于相同颜色的点之间可以花费 $1$ 的代价相互到达，并且颜色数很小。我们将同色的点看作同类，每次计算两类点之间的花费。

枚举 $x,y$，计算 $x$ 颜色的点和 $y$ 颜色的点之间的花费和：

若 $x=y$，那么答案就是 $\frac{cn{t}_x\times (cn{t}_x-1)}{2}$。其中 $cn{t}_x$ 表示颜色为 $x$ 的点的数量。

若 $x\ne y$，先来考虑如何计算两个确定的点 $a,b$ 之间的花费(满足 $c_a=x,c_b=y$)：
称花费 $1$ 代价从一个点到另一个同色点为 传送。
我们发现如果最优路径下 $a\to b$ 至少进行了一次传送，那么就有：

$$dis(a,b)=\underset{p=1}{\overset{k}{\min }}(d_{a,p}+d_{b,p}+1)$$

其中 $d_{a,c}$ 表示 $a$ 号点到任意一个颜色为 $c$ 的点的最小花费。
证明是简单的，只需要将 $p$ 选成第一次传送时的颜色，然后反证法即可。

那么 $d_{a,c}$ 是好求的，只需要跑 $k$ 遍 多源最短路 即可， 每次 $bfs$ 总复杂度 $O(nk)$。

唯一存在问题的情况是 $a,b$ 在同一条链上并且 $a$ 只经过链上的边到达 $b$。我们先不考虑这种情况。

接下来考虑怎么整体计算两类点之间的花费：
设 $D_{x,y}$ 表示 任意一个颜色为 $x$ 的点到达 任意一个颜色为 $y$ 的点的最小花费。
那么有性质：$d_{a,p}\le D_{c_a,p}+1$。这是因为你可以多花费 $1$ 的代价传送取到 $D_{c_a,p}$。

由于我们想整体计算两种颜色的贡献，因此我们将点对之间的花费 放缩 成两种颜色之间的花费：

$$\underset{p=1}{\overset{k}{\min }}(D_{x,p}+D_{y,p}+1)\le dis(a,b)\le \underset{p=1}{\overset{k}{\min }}(D_{x,p}+D_{y,p}+1)+2$$

设 $d{1}_{x,y}=\underset{p=1}{\overset{k}{\min }}(D_{x,p}+D_{y,p}+1)$。
取值范围内只有 { d 1 x , y , d 1 x , y + 1 , d 1 x , y + 2 } \{d1_{x, y}, d1_{x, y} + 1, d1_{x, y} + 2\} {d1x,y​,d1x,y​+1,d1x,y​+2}，只需要计算有多少点对分别取到这三种值就可以算出答案。

我们来计算 $d{1}_{x,y}$ 和 $d{1}_{x,y}+2$ 的数量，剩下的可以用总数减去这两个得到。

设 $T_a$ 表示 $d_{a,p}$ 和 $D_{c_a,p}$ 取等的 $p$ 的集合。(一个在 $[0,2^k)$ 中的数字)
设 $F_{x,y}$ 表示 $D_{x,p}+D_{y,p}+1$ 取到 $d{1}_{x,y}$ 的 $p$ 的集合，$F_{x,y}^{\prime }$ 表示取到 $d{1}_{x,y}+1$ 的 $p$ 的集合。

1. $dis(a,b)=d{1}_{x,y}$：需要满足 $T_a\cap T_b\cap F_{x,y}\ne \varnothing$。

2. $dis(a,b)=d{1}_{x,y}+2$：需要满足 $T_a\cap T_b\cap F_{x,y}^{\prime }=\varnothing$ 且 $(T_a\cup T_b)\cap F_{x,y}=\varnothing$ 。

对于第一种，考虑容斥计算：拿总方案数减去交为空的方案数。对于交为空的方案数，同样是一个容斥，枚举 $F_{x,y}$ 的子集 $S$ 钦定不合法，那么需要求出 颜色为 $x$ 的点中有多少个 $a$ 满足 $T_a$ 是 $S$ 的超集，和颜色为 $y$ 的点中有多少个 $b$ 满足 $T_b$ 是 $S$ 的超集。这个只需要对于每种颜色跑一遍 高维前缀和 预处理 超集和 即可。复杂度 $O(2^k)$。

对于第二种也类似：有 $\cup$ 不好看，将限制拆成 $T_a\cap F_{x,y}=\varnothing$ 且 $T_b\cap F_{x,y}=\varnothing$。那么暴力可以写成：
$$\sum _{S_1\subseteq F_{x,y}^{\prime }}\sum _{S_2\subseteq F_{x,y}}\sum _{S_3\subseteq F_{x,y}}(-1{)}^{|S_1|+|S_2|+|S_3|}\times h_{x,S_1\cup S_2}\times h_{y,S1\cup S_3}$$

其中 $h_{a,S}$ 是求出的超集和数组。

那么可以写成：
$$\sum _{S_1\subseteq F_{x,y}^{\prime }}(-1{)}^{|S_1|}(\sum _{S_2\subseteq F_{x,y}}(-1{)}^{|S_2|}\times h_{x,S_1\cup S_2})(\sum _{S_3\subseteq F_{x,y}}(-1{)}^{|S_3|}\times h_{y,S1\cup S_3})$$

那么枚举 $S_1$ 后， $S_2,S_3$ 的枚举就独立了。注意到 $|F_{x,y}^{\prime }|+|F_{x,y}|\le k$，因此复杂度还是 $O(2^k)$。

还剩下最开始的一个问题：同一条链上的点对这样求可能不对，怎么改成对的？

我们发现任意两个点之间花费不会超过 $2k$。这是因为如果将最优路径的点的颜色依次写下来，如果存在一种颜色出现次数 $\ge 3$，那么显然可以调整为更优。因此每种颜色不会出现超过 $2$ 次。

那么就枚举每一条链上距离不超过 $2k$ 的点对，先将它们在整体计算时的贡献撤销，然后算出正确答案加进来即可。枚举量为 $O(nk)$。

总复杂度就是 $O(nk+k^2{2}^k)$。

CODE：

// 核心思路是根据 k 比较小想到将不同颜色的两类点整体算它们之间的贡献 
// 需要处理：每个点到某种颜色的最小距离， 每种颜色到其它颜色的最小值 
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
typedef long long LL;
const int N = 1e6 + 50;
const int M = 31; 
unordered_map< int, int > cm[M];
int n, m, K, idx[500], rk, nc, node[M], col[N];
int dis[M][N], d[M][M], d1[M][M], Dis[N];
int Cnt[M][1 << 20], T[N], S[M][M], S_[M][M]; 
LL res;
string r[N];
vector< int > cnd[M];
struct edge {int v, last, w;
} E[N * 4];
int tot, head[N];
inline void add(int u, int v, int w) {E[++ tot] = (edge) {v, head[u], w};head[u] = tot;
}
bool vis[N];
inline void bfs(int c) {deque< int > q; memset(dis[c], 0x3f, sizeof dis[c]); for(auto v : cnd[c]) dis[c][v] = 0, q.push_back(v);while(!q.empty()) {int u = q.front(); q.pop_front(); for(int i = head[u]; i; i = E[i].last) {int v = E[i].v; if(dis[c][v] > dis[c][u] + E[i].w) {dis[c][v] = dis[c][u] + E[i].w;if(!E[i].w) q.push_front(v);else q.push_back(v);}}}for(int i = 1; i <= nc; i ++ ) if(col[i]) d[c][col[i]] = min(d[c][col[i]], dis[c][i]);
}
inline void fwt(int *f) {for(int i = 0; i < K; i ++ ) for(int s = 0; s < (1 << K); s ++ ) if((s >> i & 1)) f[s ^ (1 << i)] += f[s];
}
inline int get(int x, int y) { // 在不考虑同一条链下 (x, y) 之间的答案 if(col[x] == col[y]) return 1;else if((T[x] & T[y] & S[col[x]][col[y]]) != 0) return d1[col[x]][col[y]];else if(((T[x] | T[y]) & S[col[x]][col[y]]) == 0 && (T[x] & T[y] & S_[col[x]][col[y]]) == 0) return d1[col[x]][col[y]] + 2;else return d1[col[x]][col[y]] + 1;
}
inline int sz(int x) {return __builtin_popcount(x);}
inline int sign(int x) {return (x & 1) ? -1 : 1;}
inline LL calc(int x, int y) { // x, y 两种颜色的贡献 if(x == y) {int cnt = cnd[x].size(); return 1LL * cnt * (cnt - 1) / 2;}if(K <= 20) {	// 首先计算答案是 d1[x][y]的点对数量 int cx = cnd[x].size(), cy = cnd[y].size();LL res = 0, rest = 0;for(int ts = S[x][y]; ; ts = (ts - 1 & S[x][y])) {rest = rest + 1LL * Cnt[x][ts] * Cnt[y][ts] * sign(sz(ts));if(!ts) break;}res += (1LL * cx * cy - rest) * d1[x][y];// 接着计算有多少是 d1[x][y] + 2 LL num = 0;for(int ts1 = S_[x][y]; ; ts1 = (ts1 - 1 & S_[x][y])) { // 容斥两次 LL rx = 0, ry = 0;for(int ts2 = S[x][y]; ; ts2 = (ts2 - 1 & S[x][y])) {rx += 1LL * Cnt[x][ts1 | ts2] * sign(sz(ts2));ry += 1LL * Cnt[y][ts1 | ts2] * sign(sz(ts2));if(!ts2) break;}num += rx * ry * sign(sz(ts1));if(!ts1) break;}res += num * (d1[x][y] + 2);rest -= num;res += rest * (d1[x][y] + 1);return res;}else {LL res = 0;for(auto u : cm[x]) for(auto v : cm[y]) {LL c1 = u.second, c2 = v.second;int tx = u.first, ty = v.first;if((tx & ty & S[x][y]) != 0) res += c1 * c2 * d1[x][y];else if((tx & ty & S_[x][y]) == 0 && ((tx | ty) & S[x][y]) == 0) res += c1 * c2 * (d1[x][y] + 2);else res += c1 * c2 * (d1[x][y] + 1);}return res;}
}
int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n >> m >> K;memset(d, 0x3f, sizeof d);for(int i = 1; i <= K; i ++ ) node[i] = ++ nc;for(int i = 1; i <= m; i ++ ) {cin >> r[i];for(int j = 0; j < r[i].size(); j ++ ) {if(!idx[r[i][j]]) idx[r[i][j]] = ++ rk;nc ++; col[nc] = idx[r[i][j]]; cnd[col[nc]].pb(nc);add(nc, node[col[nc]], 0); add(node[col[nc]], nc, 1);if(j) add(nc, nc - 1, 1), add(nc - 1, nc, 1);}}for(int i = 1; i <= K; i ++ ) bfs(i);for(int i = 1; i <= K; i ++ ) {for(int j = 1; j <= K; j ++ ) {d1[i][j] = 1e8;for(int k = 1; k <= K; k ++ ) {d1[i][j] = min(d1[i][j], d[i][k] + d[j][k] + 1);}for(int k = 1; k <= K; k ++ ) {if(d[i][k] + d[j][k] + 1 == d1[i][j]) S[i][j] |= (1 << k - 1);else if(d[i][k] + d[j][k] + 1 == d1[i][j] + 1) S_[i][j] |= (1 << k - 1);}}}for(int i = 1; i <= K; i ++ ) {for(auto v : cnd[i]) {int S = 0;for(int j = 1; j <= K; j ++ ) if(dis[j][v] == d[i][j]) S |= (1 << j - 1);if(K <= 20) Cnt[i][S] ++;else cm[i][S] ++;T[v] = S;}if(K <= 20) fwt(Cnt[i]); // 超集贡献 }for(int i = 1; i <= K; i ++ ) for(int j = i; j <= K; j ++ )  res += calc(i, j);int id = K;for(int i = 1; i <= m; i ++ ) { // 计算同一条链上的贡献。 答案不超过 2 * K  int len = r[i].size() - 1;for(int j = 0; j <= len; j ++ ) {for(int k = 1; k <= 2 * K && j + k <= len; k ++ ) {res = res - get(id + j + 1, id + j + k + 1) + min(get(id + j + 1, id + j + k + 1), k);}}id += len + 1;}cout << res << endl;return 0;
}