题解

如果不加这条边，那么答案是所有点入度的乘积

加上了这条边之后，我们转而统计不合法的方案数

就是相当于统计一条路径从y到x，新图所有点度的乘积除上这条路径所有点的点度乘积

初始化为\(f[y] = \frac{\prod_{i = 2}^{n} ind[i]}{ind[y]}\)

转移按照拓扑序转移

如果u能到v

\(f[v] += \frac{f[u]}{ind[v]}\)

用总答案减掉f[x]即可

特判掉y = 1的情况

代码

#include 
    
     #define fi first#define se second#define pii pair
     
      #define mp make_pair#define pb push_back#define enter putchar('\n')#define space putchar(' ')#define MAXN 100005//#define ivorysiusing namespace std;typedef long long int64;typedef long double db;typedef unsigned int u32;template
      
       void read(T &res) {    res = 0;char c = getchar();T f = 1;    while(c < '0' || c > '9') {    if(c == '-') f = -1;    c = getchar();    }    while(c >= '0' && c <= '9') {    res = res * 10 + c - '0';    c = getchar();    }    res *= f;}template
       
        void out(T x) {    if(x < 0) {putchar('-');x = -x;}    if(x >= 10) out(x / 10);    putchar('0' + x % 10);}struct node {    int to,next;}E[MAXN * 2];const int MOD = 1000000007;int N,M,x,y,head[MAXN],sumE,ind[MAXN],f[MAXN],c[MAXN],inv[MAXN];int mul(int a,int b) {    return 1LL * a * b % MOD;}int inc(int a,int b) {    return a + b >= MOD ? a + b - MOD : a + b;}int fpow(int x,int c) {    int res = 1,t = x;    while(c) {    if(c & 1) res = mul(res,t);    t = mul(t,t);    c >>= 1;    }    return res;}void add(int u,int v) {    E[++sumE].to = v;    E[sumE].next = head[u];    head[u] = sumE;}queue
        
          Q;void BFS() {    Q.push(1);    while(!Q.empty()) {    int u = Q.front();Q.pop();    for(int i = head[u] ; i ; i = E[i].next) {        int v = E[i].to;        f[v] = inc(f[v],mul(f[u],inv[v]));        --c[v];        if(!c[v]) Q.push(v);    }    }}void Solve() {    read(N);read(M);read(x);read(y);    int u,v;    for(int i = 1 ; i <= M ; ++i) {    read(u);read(v);    add(u,v);ind[v]++;    }    if(y == 1) {    int ans = 1;    for(int i = 2 ; i <= N ; ++i) ans = mul(ans,ind[i]);    out(ans);enter;    }    else {    f[y] = 1;    for(int i = 2 ; i <= N ; ++i) {        if(i != y) f[y] = mul(f[y],ind[i]);    }    for(int i = 1 ; i <= N ; ++i) {c[i] = ind[i];inv[i] = fpow(ind[i],MOD - 2);}    BFS();    int ans = 1;    ++ind[y];    for(int i = 2 ; i <= N ; ++i) ans = mul(ans,ind[i]);    ans = inc(ans,MOD - f[x]);    out(ans);enter;    }}int main() {#ifdef ivorysi    freopen("f1.in","r",stdin);#endif    Solve();}