【学习笔记】CF1835D Doctor‘s Brown Hypothesis-Toy模板网

这篇具有很好参考价值的文章主要介绍了【学习笔记】CF1835D Doctor‘s Brown Hypothesis。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

有点难😅

发现 $x, y$ 在一个强连通块内，这样一定有环🤔

发现可以找到强连通块内所有环长度的 $\gcd$ ，这样从 $x$ 到 $y$ 的所有路径的长度都模这个数同余，又因为 $K$ 非常大，所以我们总可以遍历整个强连通块并走若干个环，因此只需要从 $x$ 到 $y$ 的任意一条路径的长度和 $K$ 模 $\gcd$ 同余即可

首先要做过这道题 [ABC306G] Return to 1

发现直接 $D FS$ 即可，感觉没啥区别啊😅

复杂度 $O(n\log n)$ 。文章来源地址https://www.toymoban.com/news/detail-709535.html

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
using namespace std;
const int N=1e5+5;
int n,m;
int dfn[N],low[N],num,vs[N],cnt;
int dis[N],ps[N],sz[N],g;
ll K,res;
vector<int>G[N];
stack<int>s;
int gcd(int x,int y){
    return y==0?x:gcd(y,x%y);
}
vector<int>vec;
void dfs(int u){
    vec.pb(dis[u]);
    for(auto v:G[u]){
        if(ps[v]!=cnt)continue;
        if(dis[v]==-1)dis[v]=dis[u]+1,dfs(v);
        else g=gcd(g,abs(dis[u]+1-dis[v]));
    }
}
ll calc(ll x){
    return x*(x+1)/2;
}
void tarjan(int u){
    dfn[u]=low[u]=++num,vs[u]=1,s.push(u);
    for(auto v:G[u]){
        if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
        else if(vs[v])low[u]=min(low[u],dfn[v]);
    }if(low[u]==dfn[u]){
        int tmp;cnt++;
        do{
            tmp=s.top(),s.pop();
            vs[tmp]=0,ps[tmp]=cnt,ps[tmp]=cnt;
        }while(tmp!=u);
        g=0,dis[u]=0,vec.clear(),dfs(u);
        if(g){
            for(auto e:vec)sz[e%g]++;
            if(K%g==0){
                for(int i=0;i<g;i++){
                    res+=calc(sz[i]);
                }
            }
            if(g%2==0&&K%g==g/2){
                for(int i=0;i<g;i++){
                    int j=(i+g/2)%g;
                    if(i<j)res+=(ll)sz[i]*sz[j];
                }
            }
            for(auto e:vec)sz[e%g]--;
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>K,memset(dis,-1,sizeof dis);
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        G[x].pb(y);
    }for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
    cout<<res;
}