题意简述
给你一张 \(n\) 个点 \(m\) 条边的有向图，你需要找出有多少个点对 \((u, v), 1 \le u \le v \le n\)，满足存在一条从 \(u\) 到 \(v\) 的长度为 \(k\) 的途径，和一条从 \(v\) 到 \(u\) 的长度为 \(k\) 的途径。
\(1 \le n \le 10^5\)，\(0 \le m \le 2 \times 10^5\)，\(n^3 \le k \le 10^{18}\)。
题解
本文做法边带权也能做，因此不妨假设边带权。
容易发现只有在同一个强连通分量内的点对 \((u, v)\) 才可能满足条件，因此可以对每个强连通分量分别考虑。我们不妨假设原图强连通。
\(k \ge n^3\) 的条件暗示 \(k\) 足够大。在强连通图中，这意味着我们可以经过所有节点，并使用图上的每一个环对途径进行增广。记所有环长为 \(len_1, len_2, \dots, len_m\)，不难发现我们增广的长度可以表示为 \(len_1x_1 + len_2x_2 + \dots + len_m x_m, \,x_1, x_2, \dots, x_m \ge 0\)。记 \(d = \gcd_{i = 1}^m len_i\)，根据裴蜀定理和类似同余最短路的构造，可以证明对于足够大的 \(s\) 满足 \(d \mid s\)，我们一定能够增广出长度 \(s\)。
于是不难想到我们需要求解 \(d\)。我声称，对于正整数 \(p\)，\(p \mid d\) 的一个充分必要条件是能够找到一组 \(\{dis_n\}\)，使得原图的所有边 \((u, v, w)\) 有 \(dis_v - dis_u \equiv w \,(\bmod \, t)\)。
充分性：
对于原图所有的环，记组成它的所有边为 \((u_1, u_2, w_1), (u_2, u_3, w_2), \dots, (u_l, u_1, w_l)\)，必有 \(\sum_{i = 1}^l w_i \equiv \sum_{i = 1}^{l - 1} (dis_{u_{i + 1}} - dis_{u_i}) + dis_{u_1} - dis_{u_l} \equiv 0 \, (\bmod \, p)\)。因此 \(p\) 是所有环长的因数，即 \(p \mid d\)。
必要性：
考虑构造证明。由于原图强连通，我们可以找到一棵以 \(rt\) 为根的外向生成树。令 \(dis_{rt} = 0\)，对于外向树上的每一条边 \((u, v, w)\)，令 \(dis_v = dis_u + w\)。
该构造对于所有树边是合法的。
该构造对于所有反祖边同样合法，证明类似充分性证明的逆过程。
考虑横叉边 \((u, v)\)，在外向树上从 \(v\) 走到 \(u\) 会反着经过若干条边。我们可以证明对于一条边 \((u, v, w)\)，必然有一条从 \(v\) 到 \(u\) 的在模 \(p\) 意义下同余 \(-w\) 的途径。因此还是可以类似充分性证明的逆过程进行证明。
由于原图强连通，任取一条从 \(v\) 到 \(u\) 的路径。加上边 \((u, v, w)\) 我们形成了一个环。从 \(v\) 开始绕这个环 \(p - 1\) 圈，然后再走到 \(u\)，这样我们就构造出了一条从 \(v\) 到 \(u\) 的在模 \(p\) 意义下同余 \(-w\) 的途径。
前向边的证明类似横叉边，在此略去。
基于上述结论以及必要性的证明过程，任取一棵外向生成树构造出 \(\{dis_n\}\)，这个构造在模 \(p\) 意义下成立是 \(p \mid d\) 的充分必要条件。因此对于所有边 \((u, v, w)\)，\(d\) 即为所有 \(dis_v - dis_u - w\) 的 \(\gcd\)。
求出 \(d\) 后，不难发现，\(u, v\) 之前的所有途径长度一定在模 \(d\) 意义下和 \(dis_v - dis_u\) 同余。所以判断点对 \((u, v)\) 是否满足题目条件即判断 \(dis_v - dis_u\) 和 \(dis_u - dis_v\) 是否在都模 \(d\) 意义下同余 \(k\)。
容易发现要么 \(k \equiv 0 \, (\bmod\,d)\)，要么 \(d\) 是偶数并且 \(k \equiv \frac{d}{2} \, (\bmod \, d)\) 才能找到合法点对。如果 \(k\) 满足上述两个条件之一，限制就只要求 \(dis_v - dis_u \, \equiv k \, (\bmod \, d)\)。原题没有边权，因此直接前缀和优化即可。
时间复杂度 \(O(n)\)。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template <typename T>
void chkmax(T &x, const T &y) {
if (x < y) x = y;
}
template <typename T>
void chkmin(T &x, const T &y) {
if (y < x) x = y;
}
constexpr int MAXN = 1e5 + 10;
int n, m, dfn[MAXN], low[MAXN], dfc, stk[MAXN], tp, dep[MAXN];
int cnt[MAXN];
bool ins[MAXN], vis[MAXN];
ll k, ans;
vector<int> g[MAXN];
void tarjan(int u) {
dfn[u] = low[u] = ++dfc;
stk[++tp] = u;
ins[u] = true;
for (auto v : g[u]) {
if (!dfn[v]) {
dep[v] = dep[u] + 1;
tarjan(v);
chkmin(low[u], low[v]);
} else if (ins[v]) {
chkmin(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
vector<int> buc;
while (true) {
int t = stk[tp--];
ins[t] = false;
buc.emplace_back(t);
if (t == u) break;
}
for (auto i : buc) vis[i] = true;
int d = 0;
for (auto i : buc) {
for (auto j : g[i])
if (vis[j]) d = __gcd(d, dep[j] - dep[i] - 1);
}
d = abs(d);
if (d) {
int mxdep = 0;
for (auto i : buc) {
++cnt[dep[i]];
chkmax(mxdep, dep[i]);
}
if (k % d == 0) {
for (int i = dep[u]; i <= mxdep; ++i) {
ans += (ll)(cnt[i] + 1) * cnt[i] / 2;
if (i - d >= dep[u]) {
ans += (ll)cnt[i] * cnt[i - d];
cnt[i] += cnt[i - d];
}
}
} else if (!(d & 1) && k % d == d / 2) {
for (int i = dep[u]; i <= mxdep; ++i) {
if (i - d / 2 >= dep[u]) ans += (ll)cnt[i] * cnt[i - d / 2];
if (i - d >= dep[u]) cnt[i] += cnt[i - d];
}
}
fill(cnt + dep[u], cnt + mxdep + 1, 0);
}
for (auto i : buc) vis[i] = false;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> k;
while (m--) {
int u, v;
cin >> u >> v;
g[u].emplace_back(v);
}
for (int i = 1; i <= n; ++i)
if (!dfn[i]) tarjan(i);
cout << ans << "\n";
return 0;
}