LOJ#2115. 「HNOI2015」落忆枫音

拓扑序DP。

考虑有向无环图，答案显然为 $\prod_i \deg_i$。但是加了一条边可能会出现环，产生不合法的方案。我们考虑将不合法的方案减去。

把环从图中剖出来，那么剩下点的 $\prod_i \deg_i$ 就是该环不合法的方案数。理由很简单，这个环没有入度的，而其它所有点都可以随便选父亲。于是我们将环上点的 $\deg_i$ 除掉即可。

可能会出现多个环。但其实 $a$ 与 $b$ 一定会出现在环上的。此过程可以 DP，计算 $f_i$ 为从 $b$ 到 $i$ 的方案数，最终用原答案减去 $f_a$ 即可。

Code

#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int N=1e5+10,M=2e5+10,mod=1e9+7;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,a,b;
int tot,head[N],ver[M],ne[M];
int deg[N];
ll ans=1,sum=1,f[N];
bool vis[N];

inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}
ll inv(int x)
{
    if(x<=1)return 1;
    return mod-(mod/x)*inv(mod%x)%mod;
}
void dfs(int x)
{
    if(vis[x])
        return ;
    if(x==b)
    {
        f[x]=sum*inv(deg[x])%mod;
        return ;
    }
    vis[x]=1;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        dfs(y);
        f[x]=(f[x]+f[y])%mod;
    }
    f[x]=f[x]*inv(deg[x])%mod;
}
int main()
{
    read(n,m,a,b);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        read(u,v);
        add(v,u);
        deg[v]++;
    }
    deg[1]++;
    for(int i=1;i<=n;i++)
    {
        if(i==b)ans=ans*(deg[i]+1)%mod;
        else ans=ans*deg[i]%mod;
        sum=sum*deg[i]%mod;
    }
    dfs(a);
    printf("%lld\n",(ans+mod-f[a])%mod);
    return 0;
}