84pts求条

玄关

#include<bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
    ll val,cnt;
};
int n,m,X;
vector<int>v[100001],vv[100001],stck;
int dfn[100001],low[100001],scc[100001];
int Size[100001],in_stck[100001];
/////////////
void add(int a,int b){
    if(a!=b)vv[a].push_back(b);
}
int oii;
int tsc;
void tarjan(int x){
    low[x]=dfn[x]=++oii;
//  cout<<fixed<<setprecision(1);
    in_stck[x]=1,stck.push_back(x);
    for(auto i:v[x]){
        if(!dfn[i]){
            tarjan(i);
            low[x]=min(low[x],low[i]);
        }
        else if(in_stck[i]){
            low[x]=min(low[x],dfn[i]);
        }
    }
    if(low[x]==dfn[x]){
        ++tsc;
        while(stck.back()!=x){
            scc[stck.back()]=tsc;
            Size[tsc]++;
            in_stck[stck.back()]=0;
            stck.pop_back();
        }
        Size[tsc]++;
        scc[x]=tsc;
        stck.pop_back();
        in_stck[x]=0;
    }
}
void topo(){
    ll mx=0,sm=0;
    node f[100001];
    ll in[100001]={},out[100001]={};
    queue<int>que;
    for(int i=1;i<=tsc;i++){
        for(int q:vv[i])in[q]++,out[i]++;
    }
    for(int i=1;i<=tsc;i++){
        if(in[i]==0){
            que.push(i);
            f[i].val=Size[i];
            f[i].cnt=1;
        }
    }
//  for(int i=1;i<=tsc;i++)cout<<in[i]<<" ";
//  cout<<"\n";
    while(!que.empty()){
        int tmp=que.front();que.pop();
        for(int i:vv[tmp]){
            int h=f[tmp].val+Size[i];
            if(h>f[i].val) f[i].val=h,f[i].cnt=f[tmp].cnt;
            else if(h==f[i].val) f[i].cnt+=f[tmp].cnt;
            f[i].cnt%=X;
            in[i]--;
            if(in[i]==0)que.push(i);
        }
    }
    for(int i=1;i<=tsc;i++){
//      cout<<f[i].val<<" "<<f[i].cnt<<"\n";
        if(out[i]==0){
            if(f[i].val>mx) mx=f[i].val,sm=f[i].cnt;
            else if(f[i].val==mx) sm+=f[i].cnt;
        }
    }
    cout<<mx<<"\n"<<sm%X;
}
int main(){
    // freopen("T1.in","r",stdin);
    // freopen("T1.out","w",stdout);
//  ios::sync_with_stdio(0);
//  cin.tie(0);
    cin>>n>>m>>X;
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
    }
    ////////////tarjan 
    for(int i=1;i<=n;i++){
        if(!dfn[i])tarjan(i);
    }
//  for(int i=1;i<=tsc;i++){
//      cout<<Size[i]<<"\n";
//  }
    /////////////////

//  for(int i=1;i<=n;i++){
//      int h=0;
//      if((int)v[i].size())add(scc[i],scc[v[i][0]]);
//      for(int j=1;j<(int)v[i].size();j++){
//          if(scc[v[i][j-1]]!=scc[v[i][j]]){
//              add(scc[i],scc[j]);
//          }
//      }
//  }
    for(int i=1;i<=n;i++){
        for(int q:v[i]){
            add(scc[i],scc[q]);
        }
    }
    /////////////////////////////////////
    for(int i=1;i<=tsc;i++){
        sort(vv[i].begin(), vv[i].end());
        vv[i].erase(unique(vv[i].begin(), vv[i].end()), vv[i].end());
    }

//  for(int i=1;i<=tsc;i++){
//      cout<<i<<":";
//      for(int q:vv[i])cout<<q<<" ";
//      cout<<"\n";
//  }
    topo();
}