题解：CF1835D Doctor's Brown Hypothesis

· · 题解

给出有向图，求满足存在长度为 k 的路径 u\to v 以及 v \to u 的无序点对 (u,v) 的数量。

前置知识：CF1515G Phoenix and Odometers 。

合法的点对一定在同一个强连通分量中。

先注意在求 \gcd 下的几个事实。设 dis_u 为 u 到强连通分量的根（初始点）的距离。

  1. 对于强连通分量所有点，都可以视作在强连通分量的所有环上。

    由于 \gcd(a,b)=\gcd(a+b,b)，而一个 u 可以在一个环 A 上走到别的环 B，结束后再由 A 环走回 u。又 \gcd(len_A,len_B)=\gcd(len_B+len_A,len_A)。推广即可得到该结论。

  2. 在模 p 意义下（p 为环长的约数），对于强连通分量的路径 u\to v 长为 w，必然存在 v\to u 的路径长为 -w。

    考虑 u,v 所在环，从 v 出发走 p 圈，最后一圈走到 u 停止。

  3. 强连通分量的 dfs 树，横叉边 u\to v 的环长可视作 dis_u-dis_v+w_{u\to v}。

    2 的推论以及 \gcd(a,b)=\gcd(a+b,b)。

  4. 强连通分量的环的 \gcd，只需考虑非树边上的就足够。

    仍然是由于 \gcd(a,b)=\gcd(a+b,b)，另外对于返祖边是显然的，对于横叉边就是由 3 而来，相互组合再根据这个 \gcd 公式得来。

根据这些，我们可在 \mathcal O(n\log V) 时间内求出图中每个强连通分量的环长 \gcd。

注意到 k\ge n^3，即 k 足够大，可以在强连通分量中走足够多的环。

假设强连通分量内的点对 (u,v) 满足条件，则必然满足：

dis_u-dis_v\equiv dis_v-dis_u\equiv k\pmod d

其中 d 为该强联通分量内链的 \gcd。

考虑 d 作为所有环 \gcd 的意义，即 (u,v) 的距离必然是 dis_u-dis_v 与 d 任意倍之和。这个式子就比较显然了。

对第一个等式变形，有 2(dis_u-dis_v)\equiv 0\pmod d。两个解是 dis_u-dis_v\equiv 0\pmod d 或者 dis_u-dis_v\equiv \dfrac d2 \pmod d。然后直接计数即可。

#include <vector>
#include <iostream>

using ll = long long;

using namespace std;

const int N = 2e5 + 10;

int n, m;
vector < pair <int, int> > g[N];
int dfn[N], low[N], tim, col[N], colid;
int stk[N], tp, inst[N], rt[N]; 
vector <int> ccc[N];

void tarjan (int u) {
    dfn[u] = low[u] = ++ tim;
    inst[u] = true; stk[++ tp] = u;
    for (const auto& [v, w] : g[u])
        if (!dfn[v])        tarjan (v), low[u] = min (low[v], low[u]);
        else if (inst[v])   low[u] = min (low[u], dfn[v]);
    if (dfn[u] == low[u]) {
        rt[++ colid] = u;
        do {
            ccc[colid].push_back (stk[tp]);
            col[stk[tp]] = colid;
            inst[stk[tp]] = false;
        } while (stk[tp --] != u);
    }
}

bool vis[N];
ll dis[N], gcdsum[N], cnt[N];
ll ans = 0, k, d;

ll gcd (ll a, ll b) { return !b ? a : gcd (b, a % b); }

void dfs (int u, int id) {
    vis[u] = true;
    for (const auto& [v, w] : g[u]) 
    if (col[v] == id)
        if (!vis[v]) dis[v] = dis[u] + w, dfs (v, id); 
        else gcdsum[id] = gcd (abs (dis[u] + w - dis[v]), gcdsum[id]);
}

int main (void) {

    scanf ("%d%d%lld", &n, &m, &k);
    for (int i = 1; i <= m; i ++) {
        int u, v, w; scanf ("%d%d", &u, &v);
        g[u].emplace_back (v, 1);
    }
    for (int i = 1; i <= n; i ++)   if (!dfn[i]) tarjan (i);
    for (int i = 1; i <= colid; i ++) {
        dfs (rt[i], i); d = gcdsum[i];
        if (!d) continue;
        for (const auto& v : ccc[i]) cnt[dis[v] % d] ++;
        if (!(d & 1) && k % d == (d >> 1)) for (int i = d >> 1; i < d; i ++) ans += cnt[i] * 1ll * cnt[i - d / 2];
        else    if (k % d == 0)  for (int i = 0; i < d; i ++) ans += cnt[i] * (cnt[i] + 1) / 2;
        for (const auto& v : ccc[i]) cnt[dis[v] % d] = 0;
    }

    printf ("%lld\n", ans);

    return 0;
}