题解 P3244 【[HNOI2015]落忆枫音】

· · 题解

组合计数+dp

对于DAG来说，考虑每个点的父亲，令du(x)表示x的入度，则答案是\prod du(i)

现在加了一条边，可能是环了，我们就要考虑从\prod du(i)里减去成环的情况。假设一个大小为k的环含有节点a_1,a_2...a_k，除了这个环以外的节点的父亲随意选取，那么要减去的值就是

\frac{\prod du(i)}{\prod_{i=1}^k du(a_i)}

记新加的边为(s,t)

考虑用dp完成，令g(x)表示从t到x的路径上，上面式子里的这个值，那么g(x)=\frac{1}{du(x)}(\sum g(y))（y可达x）。由于原图是DAG，直接在原图上记忆化搜索即可。

答案就是\sum du(i) - g(s)了。

#include<bits/stdc++.h>
using namespace std;
int read() {
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar();
    return q;
}
#define RI register int
const int mod=1000000007,N=100005,M=200005;
int n,m,xx,yy,ans=1,tot,dsum=1;
int h[N],ne[M],to[M],du[N],g[N],vis[N];
void add(int x,int y) {to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
int ksm(int x,int y) {
    int re=1;
    for(;y;y>>=1,x=1LL*x*x%mod) if(y&1) re=1LL*re*x%mod;
    return re;
}
void dfs(int x) {
    if(vis[x]) return;
    vis[x]=1;
    if(x==yy) {g[x]=1LL*dsum*ksm(du[x],mod-2)%mod;return;}
    for(int i=h[x];i;i=ne[i])
        dfs(to[i]),g[x]=(g[x]+g[to[i]])%mod;
    g[x]=1LL*g[x]*ksm(du[x],mod-2)%mod;
}
int main()
{
    int x,y;
    n=read(),m=read(),xx=read(),yy=read();
    for(RI i=1;i<=m;++i)
        x=read(),y=read(),add(y,x),++du[y];
    ++du[1];
    for(RI i=1;i<=n;++i) {
        if(i==yy) ans=1LL*(du[i]+1)*ans%mod;
        else ans=1LL*du[i]*ans%mod;
        dsum=1LL*du[i]*dsum%mod;
    }
    dfs(xx);
    ans=(ans+mod-g[xx])%mod;
    printf("%d\n",ans);
    return 0;
}