缩点后在一个DAG上求最长点权链 和方案数

注意转移条件和转移状态

if (nowmaxn[x] > nowmaxn[v]) {                ans[v] = ans[x];                nowmaxn[v] = nowmaxn[x];            } else if (nowmaxn[x] == nowmaxn[v]) {                ans[v] = (ans[v] + ans[x]) % X;            }

#include
      
       using namespace std;typedef long long ll;const int MAXN = 100005;const int MAXM = 1000005;int deep, colorsum = 0;int top;/*sta目前的大小*/int dfn[MAXN], color[MAXN], low[MAXN];int sta[MAXN];//存着当前所有可能能构成强连通分量的点bool visit[MAXN];//表示一个点目前是否在sta中int cnt[MAXN];//各个强连通分量中含点的数目int to[MAXM << 1], nxt[MAXM << 1], Head[MAXN], ed = 1;inline void addedge(int u, int v){    to[++ed] = v;    nxt[ed] = Head[u];    Head[u] = ed;}void tarjan(int x){    dfn[x] = ++deep;    low[x] = deep;    visit[x] = 1;    sta[++top] = x;    for (int i = Head[x]; i; i = nxt[i]) {        int v = to[i];        if (!dfn[v]) {            tarjan(v);            low[x] = min(low[x], low[v]);        } else {            if (visit[v]) {                low[x] = min(low[x], low[v]);            }        }    }    if (dfn[x] == low[x]) {        color[x] = ++colorsum;        visit[x] = 0;        while (sta[top] != x) {            color[sta[top]] = colorsum;            visit[sta[top--]] = 0;        }        top--;    }}int X;int du[MAXN];vector
       
         g[MAXN];map
        
         
          , int> mp, mp2;queue
          
            que;int ans[MAXN];int nowmaxn[MAXN];int main(){    int n, m;    int u, v;    scanf("%d %d %d", &n, &m, &X);    for (int i = 1; i <= m; i++) {        scanf("%d %d", &u, &v);        if (!mp2[make_pair(u, v)]) {            addedge(u, v);            mp2[make_pair(u, v)] = 1;        }    }    for (int i = 1; i <= n; i++) {        if (!dfn[i]) {            tarjan(i);        }        cnt[color[i]]++;    }    for (u = 1; u <= n; u++) {        int x = color[u];        for (int i = Head[u]; i; i = nxt[i]) {            v = to[i];            int y = color[v];            if (x != y) {                if (!mp[make_pair(x, y)]) {                    g[x].push_back(y);                    du[y]++;                    mp[make_pair(x, y)] = 1;                }            }        }    }    for (int i = 1; i <= colorsum; i++) {        if (du[i] == 0) {            que.push(i);            ans[i] = 1;        }    }    while (que.size()) {        int x = que.front();        que.pop();        nowmaxn[x] += cnt[x];        for (int i = 0; i < g[x].size(); i++) {            v = g[x][i];            if (nowmaxn[x] > nowmaxn[v]) {                ans[v] = ans[x];                nowmaxn[v] = nowmaxn[x];            } else if (nowmaxn[x] == nowmaxn[v]) {                ans[v] = (ans[v] + ans[x]) % X;            }            du[v]--;            if (du[v] == 0) {                que.push(v);            }        }    }    int anser = 0;    int maxnn = 0;    for (int i = 1; i <= colorsum; i++) {        if (nowmaxn[i] > maxnn) {            anser = ans[i];            maxnn = nowmaxn[i];        } else if (nowmaxn[i] == maxnn) {            anser = (anser + ans[i]) % X;        }    }    cout << maxnn << endl;    cout << anser << endl;}