D - Doctor's Brown Hypothesis
首先，一对合法的\((x,y)\)一定是在同一个\(scc\)中的，所以我们将每个\(scc\)分开处理
若我们当前在处理某一个\(scc\)，考虑给这个\(scc\)建一棵\(dfn\)树，设当前\(scc\)中的所有的环长度的\(gcd\)为\(d\)，由数论得当\(g|k\)且\(k\)足够大时，一定有解
设环长为\(len_i\)，那么题目就是求\(\sum len_i\times x_i=k\)
若原图中有边\((u,v)\)，那么一定有\(depth_v-depth_u\equiv 1\mod d\)
因为\((u,v)\)一定被包含在某一个环里，设环长为\(len\)，一定有\(d|len\)，而在树上\(depth_x-depth_y\)就是\(y\)到\(x\)的距离\(\mod d\)，所以有\(depth_u-depth_v\equiv len-1\mod d\)，那么\(depth_v-depth_u\equiv 1-len\equiv 1\mod d\)
由此可得，满足题目的\((x,y)\)当且仅当
\[\begin{cases}
depth_u-depth_v\equiv k\mod d\\
depth_v-depth_u\equiv k\mod d
\end{cases}
\]
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
const int N=1e5+5,M=2e5+5;
int n,m,k,d;
ll K,ans;
int head[N],cnt=1;
struct node{
int nxt,v;
}tree[M];
void add(int u,int v){
tree[++cnt]={head[u],v},head[u]=cnt;
}
int dfn[N],low[N],tot,stk[N],top,scc,c[N];
bool ins[N];
vector<int> pos,d_pos[N];
int depth[N],maxd;
void dfs(int x){
maxd=max(maxd,depth[x]),d_pos[depth[x]].pb(x);
for(int i=head[x],y;i;i=tree[i].nxt){
if(depth[y=tree[i].v]||c[y]!=c[x]) continue;
depth[y]=depth[x]+1,dfs(y);
}
}
map<int,int> mp;
void get(int dep){
if(dep>maxd) return;
for(auto x:d_pos[dep]) ++mp[(depth[x]+k)%d],ans+=mp[depth[x]%d];
get(dep+1);
}
#define Init() for(int i=1;i<=maxd;++i) d_pos[i].clear()
void work(){
maxd=0,depth[pos[0]]=1,dfs(pos[0]);
d=0;
for(auto x:pos)
for(int i=head[x],y;i;i=tree[i].nxt)
if(c[y=tree[i].v]==c[x]){
if(!d) d=abs(depth[tree[i].v]-depth[x]-1);
else d=__gcd(d,abs(depth[tree[i].v]-depth[x]-1));
}
if(!d){ Init(); return; }
k=K%d;
if(k&&k*2!=d){ Init(); return; }
mp.clear(),get(1);
Init();
}
void tarjan(int x){
dfn[x]=low[x]=++tot,ins[x]=true,stk[++top]=x;
for(int i=head[x],y;i;i=tree[i].nxt){
if(!dfn[y=tree[i].v]) tarjan(y),low[x]=min(low[x],low[y]);
else if(ins[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
int y; ++scc,pos.clear();
do y=stk[top--],ins[y]=false,c[y]=scc,pos.pb(y);
while(y!=x);
work();
}
}
int main(){
scanf("%d%d%lld",&n,&m,&K);
for(int i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),add(u,v);
for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
printf("%lld",ans);
return 0;
}