luogu P3244 [HNOI2015]落忆枫音

md这题和矩阵树定理没半毛钱关系qwq

首先先不考虑有环,一个(DAG)个外向树个数为(prod_{i=2}^{n}idg_i()就是(indegree_i)),因为外向树每个点入度为一,对于一个点有入度个父亲可选,然后乘法原理起来就是答案

现在可能加一条边会有环,那么答案可以考虑总方案减不合法方案,不合法的有环方案就是环内的点连好了,然后剩下的点贡献方案,设(s)是个环,那么方案为(sum_{s}prod_{i otin s}idg_i=sum_{s}frac{prod_{i=2}^{n}idg_i}{prod_{iin s}idg_i}=prod_{i=2}^{n}idg_isum_{s}frac{1}{prod_{iin s}idg_i})

后面那个东西,因为加了边(x ightarrow y),所以一条(y)到(x)可以确定一个环,那么以(y)为初始状态,可拓扑排序一遍dp出来方案

注意(y=1)的情况

#include<bits/stdc++.h>
#define LL long long
#define db double
#define il inline
#define re register

using namespace std;
const int N=1e5+10,mod=1e9+7;
il int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
int to[N<<1],nt[N<<1],hd[N],dg[N],idg[N],tot;
void add(int x,int y){++tot,to[tot]=y,nt[tot]=hd[x],hd[x]=tot,++dg[y];}
int n,m,u,v,f[N],inv[N];
queue<int> q;

int main()
{
    n=rd(),m=rd(),u=rd(),v=rd();
    for(int i=1;i<=m;++i)
    {
        int x=rd(),y=rd();
        add(x,y);
    }
    int ans=1;
    for(int i=2;i<=n;++i) ans=1ll*ans*(dg[i]+(v==i))%mod;
    if(v!=u&&v!=1)
    {
        memcpy(idg,dg,sizeof(dg));
        inv[0]=inv[1]=1;
        for(int i=2;i<=n+1;++i) inv[i]=(mod-1ll*mod/i*inv[mod%i]%mod)%mod;
        f[v]=1,q.push(1);
        while(!q.empty())
        {
            int x=q.front();
            q.pop();
            f[x]=1ll*f[x]*inv[dg[x]+(x==v)]%mod;
            for(int i=hd[x];i;i=nt[i])
            {
                int y=to[i];
                f[y]=(f[y]+f[x])%mod,--idg[y];
                if(!idg[y]) q.push(y);
            }
        }
        ans=1ll*ans*(1-f[u]+mod)%mod;
    }
    printf("%d
",ans);
    return 0;
}

luogu P3244 [HNOI2015]落忆枫音

相关推荐