7 月 3 日闲话

· · 题解

今天学习了 CF1338E JYPnation 的相关内容阿，虽然这样说但还是直接开摆

看到小粉兔的题解里面说这是个数竞题并写了一车 Lemma，感觉是搞复杂了，于是来投一篇题解。

首先注意到，如果两个点不在同一个 SCC 内部，那么这个点对对答案的贡献为 1+614n（正向通过一条边直接到达，反向是回不去的）。因此接下来我们只需要考虑两个点在同一个 SCC 的情况。

当然，这里有一个简化实现的点，让我们避免写 Tarjan：

可以归纳证明，一个非平凡的强连通分量必然有一个导出子图是三元环（一个大于三元的环被它的一条弦分成两半，其中有一半可以和这条弦构成一个大小更小的环）。因此原图缩点之后，只有拓扑序最大的一个可能是非平凡强连通分量，其他的都是单点。可以从后往前删除这些单点（出度从大到小），同时统计贡献。

接下来我们也来写一点 Lemma。

引理 1 答案不超过 3。

证明 1 考虑一条长度为 4 的最短路 a\rightarrow b\rightarrow c\rightarrow d \rightarrow e。由于不能继续松弛，其他边的方向确定，于是我们确定了这样一个子图。

可以发现黄色点的导出子图并不符合题目的特殊条件。

现在我们只需要统计最短路为 1, 2, 3 的点对分别有多少。最短路为 1 的点对数量就是边数。那么我们只需要在 2, 3 之间选择一个求出来即可。一般正常人都会选择 2。而 u 到 v 距离为 2 的条件是：存在边 v\rightarrow u，且存在点 a 使得 u\rightarrow a, a\rightarrow v。显然这里我们不能直接枚举，需要找到更好的性质。

一个直接的想法是，如果存在多个满足条件的 a，那么我们取拓扑序最大的一个来计入答案。并且我们发现这样一个性质： 如果 u\rightarrow a, a\rightarrow v，另外有一个 u 的出点集合中的点 b，且 a\rightarrow b，那么由于题目的特殊条件，b\rightarrow v 也应该存在。也就是说，我们只需要找到 u 的出点集合当中的拓扑序最靠后的（可能是拓扑序最靠后强连通分量当中的任意一个元素，但是你可以发现如果这个强连通分量大小不为 1，它不应该和别的点连任何边，否则就与特殊条件矛盾，所以出现这种情况 u 到其他点最短路都不是 2，我们只需要保证我们的算法在拓扑序最大的点存在时正确即可），判断其与 v 是否有边即可。

找拓扑序最大的只需要将图中的边 u\rightarrow v 视为一个偏序关系 v\leq u，在 u 的出点集合中找极小元的过程和在一个集合中找最小值的过程完全一致。

代码实现是容易的。

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

int get() {
    int x = 0, f = 1; char c = getchar();
    while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
    while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int N = 8005, rev[] = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
int n;
long long ans = 0;
int edge[N][N], ind[N], oud[N];
char s[N];
int bin[N], vis[N], mn[N];

int mp(char c) { if(isdigit(c)) return c - '0'; else return 10 + c - 'A'; }
void add(int u, int v) { edge[u][v] = 1, ++oud[u], ++ind[v]; }

main() {
    n = get();
    for(int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        for(int j = 1; j * 4 <= n; j++) {
            int now = rev[mp(s[j])];
            for(int k = 0; k < 4; k++) if(now >> k & 1) add(i, 4 * (j - 1) + k + 1); 
        }
    }
    for(int i = 1; i <= n; i++) bin[i] = i;
    sort(bin + 1, bin + 1 + n, [](int x, int y) { return oud[x] < oud[y]; });
    int top = n;
    while(top && oud[bin[top]] == top - 1) 
        ans += top - 1 + 1ll * n * 614 * (top - 1), vis[bin[top]] = 1, --top;
    for(int i = 1; i <= n; i++) if(!vis[i])
        for(int j = 1; j <= n; j++) if(!vis[j])
            if(edge[i][j]) {
                if(!mn[i] || edge[mn[i]][j]) mn[i] = j;
            }

    int dis1 = top * (top - 1) / 2, dis2 = 0, dis3;
    for(int i = 1; i <= n; i++) if(!vis[i])
        for(int j = 1; j <= n; j++) if(!vis[j])
            if(edge[j][i] && edge[mn[i]][j]) dis2++;
    dis3 = top * (top - 1) / 2 - dis2;
    ans += dis1 + dis2 * 2 + dis3 * 3;

    cout << ans << endl;
    return 0;
}