【题解】 [HNOI2015]落忆枫音 （拓扑排序+dp+容斥原理）

---

原题戳我

Solution：

（部分复制Navi_Aswon博客）

解释博客中的两个小地方：

[sum_{left(S是G中y→x的一条路径的点集 ight))}prod_{2≤j≤n,(j∉S)}degree_j ]

• 因为加了(x)到(y)这条边出现了环，所以环上一定有一条边是从(x)连向(y)，所以在没有这条边时，能从(y)连向(x)的方案都是不满足的。
• 因此，上面这个式子就是找出了一条从(y)至(x)的路径后，连边的方案数。可以看作，(y)到(x)路径上的所有边都固定只连向环中的下一个点，所以方案数就是其他不在环上的点的入度乘积

[f_i=frac{∑left(j→i ight)*f_j}{degree_i} ]

• 这个式子用(degree)总乘积除掉环路径上的点后的乘积之和，也就是不同环到这个点来后的方案和，所以最后(f[x])就是所有存在环的方案数。注意的理解的点就是，(f[ ])不是一个固定的环存在的不能满足方案数，而是所有环的情况方案数之和

• 另外还用到了费马小定律求逆元，(1e9+7)是质数

是一道需要好好理解好好思考的题目

---

Code：

//It is coded by Ning_Mew on 3.17
#include<bits/stdc++.h>
#define LL long long

using namespace std;

const int maxn=1e5+7;
const int MOD=1e9+7;

int n,m,x,y;
int head[maxn],cnt=0;
struct Edge{
  int nxt,to;
}edge[2*maxn];
int degree[maxn],in[maxn];
LL ans=0,f[maxn];

void add(int from,int to){
  edge[++cnt].nxt=head[from];
  edge[cnt].to=to;
  head[from]=cnt;
}
LL q_pow(int x,int k){
  LL box=1ll*x,ans=1;
  while(k){
    if(k%2)ans=ans*box%MOD;
    box=box*box%MOD;
    k=k/2;
  }return ans;
}
void topsort(){
  queue<int>q;
  while(!q.empty())q.pop();
  for(int i=1;i<=n;i++){if(in[i]==0)q.push(i);}
  while(!q.empty()){
    int u=q.front();q.pop();
    f[u]=f[u]*q_pow(degree[u],MOD-2)%MOD;
    for(int i=head[u];i!=0;i=edge[i].nxt){
      int v=edge[i].to;
      in[v]--;f[v]=(f[v]+f[u])%MOD;
      if(in[v]==0)q.push(v);
    }
  }return;
}
int main(){
  scanf("%d%d%d%d",&n,&m,&x,&y);
  degree[y]++;
  for(int i=1;i<=m;i++){
    int a,b;scanf("%d%d",&a,&b);
    add(a,b);degree[b]++;
  }
  ans=1;
  for(int i=2;i<=n;i++){
    in[i]=degree[i];
    ans=1ll*ans*degree[i]%MOD;
  }
  in[1]=degree[1];
  in[y]--; f[y]=ans;
  if(y!=1)topsort();
  printf("%lld
",(ans-f[x]+MOD)%MOD);
  return 0;
}