CF1835D Doctor's Brown Hypothesis 题解

题目链接

点击打开链接

题目解法

首先只有在一个强联通分量里的点对才可能合法，因此我们这里说的图默认为强联通图
但是上面的条件成立只需要满足 \(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;
}