题目链接
题目解法
首先只有在一个强联通分量里的点对才可能合法，因此我们这里说的图默认为强联通图
但是上面的条件成立只需要满足 \(k\ge n\)，考虑用好 \(k\) 可以认为是极大的性质
所以说我们可以通过图中所有的环 \(+\) 路径来凑出 \(k\)
不难发现，所有的环能构成的长度形如 \(\sum len_ix_i\)，\(len\) 为环长，\(x_i\ge 0\)
因为 \(k\) 足够大，所以能构成长度 \(l\) 的充要条件为 \(\gcd(len_i)|l\)
求出有向图所有环长度的 \(\gcd\) 是这道题
具体过程是：建出一棵生成树，对于所有的非树边 \((x,y,z)\)，\(dis_x+z-dis_y\) 求 \(\gcd\)，其中 \(dis_x\) 为 \(root\) 到 \(x\) 的距离
证明我只会证充分性
还是说明一下充分性，可以帮助理解下面给出的结论
在强联通分量内，\(D_{rt,x}+D_{x,rt}\equiv 0(\mod g)\)，\(g\) 为所有环长的 \(\gcd\)，对于一条横叉边，不难得出 \(D_{y,rt}+D_{rt,x}+z\equiv 0(\mod g)\)，所以 \(D_{rt,x}-D_{y,rt}+z\equiv 0(\mod g)\)
可以猜出点对 \((x,y)\) 合法的充要条件为 \(dis_x-dis_y\equiv k\%g\) 且 \(dis_y-dis_x\equiv k\%g\)
对于 \(k\%g=0\) 和 \(k\%g=\frac{g}{2}\) 分类讨论即可
时间复杂度 \(O(n)\)
#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
FF=0;int RR=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
FF*=RR;
}
const int N=100100,M=200100;
int n,m;
LL k;
int e[M],ne[M],h[N],idx;
int low[N],dfn[N],dfs_clock,stk[N],top;
int scc_num[N],scc_cnt;
void tarjan(int u){
low[u]=dfn[u]=++dfs_clock,stk[++top]=u;
for(int i=h[u];~i;i=ne[i]){
int v=e[i];
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(!scc_num[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u]){
scc_num[u]=++scc_cnt;
while(stk[top]!=u) scc_num[stk[top]]=scc_cnt,top--;
top--;
}
}
vector<int> scc[N],G[N];
int depth[N],g,buc[N];
bool vis[N];
void dfs(int u){
vis[u]=1;
for(auto v:G[u])
if(!vis[v]) depth[v]=depth[u]+1,dfs(v);
else g=__gcd(g,depth[u]+1-depth[v]);
}
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
int main(){
read(n),read(m),read(k);
ms(h,-1);
F(i,1,m){
int x,y;read(x),read(y);
add(x,y);
}
F(i,1,n) if(!dfn[i]) tarjan(i);
F(i,1,n) scc[scc_num[i]].pb(i);
F(i,1,n) for(int j=h[i];~j;j=ne[j]) if(scc_num[i]==scc_num[e[j]]) G[i].pb(e[j]);
LL ans=0;
F(i,1,scc_cnt){
g=0,dfs(scc[i][0]),g=abs(g);
if(!g) continue;
for(auto x:scc[i]) depth[x]%=g,buc[depth[x]]++;
if(k%g==0) F(j,0,g-1) ans+=1ll*buc[j]*(buc[j]+1)/2;
if((~g&1)&&k%g==g/2) F(j,g/2,g-1) ans+=1ll*buc[j]*buc[j-g/2];
F(j,0,g-1) buc[j]=0;
}
printf("%lld\n",ans);
fprintf(stderr,"%d ms\n",int(1e3*clock()/CLOCKS_PER_SEC));
return 0;
}