[HNOI2015]落忆枫音

发现了一个硬核的题单，做这个应该比睡觉提升智力快吧。。。

还有HNOI2015的题面真是又臭又长。

传送门

考虑如果没有那条新加的边的话，答案就是1以外每个点的入度的乘积，意义是给每个点选一个父亲。

新加了一条边的话，这个拓扑图出现了环，之前那个算法就会多算上这个恰好选中环的方案。

试一试dp把包括环的方案减掉，设新加了一条由s到t的边，当前这个图的答案是ans，点i的入度是$fa_i$。

那么对于s到t的一条路径P，会多算$\sum_{x\in P}ans/fa_x$种方案。

意思是方案中一定包含路径P上的所有点，路径P外的点随便选。

那么这个东西是可以在拓扑图上dp出来的，设$f_x$是x到t所有路径多算的方案数，直接在图上转移就好了。

#include<cstdio>
#include<cstring>
#include<iostream>
#define mod 1000000007
using namespace std;
struct node{
    int next,to;
}w[200001];
int ans,num,n,m,s,t,head[100001];
int fa[100001],so[100001],cnt,f[100001];
inline int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
inline int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y){return 1ll*x*y-1ll*x*y/mod*mod;}
inline void lin(int x,int y){
    w[++cnt].next=head[x];
    w[cnt].to=y; head[x]=cnt;
}
int dfs(int x){
    if (f[x]>-1) return f[x];
    f[x]++;
    for (int i=head[x]; i; i=w[i].next)
        f[x]=add(f[x],dfs(w[i].to));
    f[x]=mul(f[x],so[fa[x]]);
    return f[x];
}
int main(){
    int x,y;
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for (int i=1; i<=m; i++){
        scanf("%d%d",&x,&y);
        fa[y]++; lin(x,y);
    }
    fa[t]++; fa[1]=ans=so[1]=1;
    for (int i=2; i<=n; i++){
        ans=mul(ans,fa[i]);
        so[i]=mul(dec(mod,mod/i),so[mod%i]);
    }
    memset(f,-1,sizeof(f));
    f[s]=mul(ans,so[fa[s]]);
    if (t!=1) ans=dec(ans,dfs(t));
    printf("%d\n",ans);
    return 0;
}