[HNOI2015]落忆枫音

迷南。 2023-10-11 04:56 6阅读 0赞

[题目][Link 1]

对于一个\\(\\rm DAG\\)答案非常显然，就是除去\\(1\\)以外所有节点入度的乘积

矩阵树定理显然是可以证明的，但是一个更为直观的理解方法就是对于每一个点从能到达它的点中找一个父亲

加上这条边之后，我们还是先求出所有节点入度的乘积，显然这样算出来的并不全是外向树，还有一些奇怪的环状物

考虑减掉这些环状物的影响

我们从图里搜出一个\\(k\\)个节点的环，我们强行使得这个环作为那个环状物，之后对于不在环里的点，其还是从能到达它的点里选一个作为父亲，于是带有这个环的情况就是

\\\[\\frac\{\\prod\_\{i=1\}^nr\_i\}\{\\prod\_\{i=1\}^kr\_\{a\_i\}\}\\\]

直接记搜搜出所有环算贡献即可

代码

#include<bits/stdc++.h>
    #define re register
    inline int read() {
        char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
        while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
    }
    const int maxn=1e5+5;
    const int mod=1e9+7;
    struct E{int v,nxt;}e[maxn<<1];
    int n,num,m,rx,ans,ry,vis[maxn],dp[maxn],head[maxn],r[maxn];
    inline void add(int x,int y) {
        e[++num].v=y;e[num].nxt=head[x];head[x]=num;
    }
    inline int ksm(int a,int b) {
        int S=1;
        for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) S=1ll*S*a%mod;
        return S;
    }
    int dfs(int x) {
        if(vis[x]) return dp[x];
        vis[x]=1;
        if(x==rx) return dp[x]=ksm(r[x],mod-2);
        for(re int i=head[x];i;i=e[i].nxt)
            dp[x]=(dp[x]+dfs(e[i].v))%mod;
        return dp[x]=1ll*dp[x]*ksm(r[x],mod-2)%mod;
    }
    int main() {
        n=read();m=read(),rx=read(),ry=read();
        for(re int x,y,i=1;i<=m;i++)
            x=read(),y=read(),add(x,y),r[y]++;
        r[ry]++;int ans=1;
        for(re int i=2;i<=n;i++) ans=1ll*ans*r[i]%mod; 
        printf("%d\n",ry!=1?(ans-1ll*ans*dfs(ry)%mod+mod)%mod:ans);
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11488234.html

[Link 1]: https://www.luogu.org/problem/P3244