BZOJ 4011: [HNOI2015]落忆枫音 计数 + 拓扑排序

#include <cstdio> 
#include <algorithm> 
#include <cstring> 
#include <queue> 
#include <cstring> 
#define N 100005 
#define mod 1000000007 
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)  
using namespace std;   
namespace IO
{
    char *p1,*p2,buf[100000]; 
    #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )
    int rd() {int x = 0, f = 1;char c = nc();while (c < 48) {if (c == ‘-‘)f = -1;c = nc();}while (c > 47) {x = (((x << 2) + x) << 1) + (c ^ 48), c = nc();}return x * f;}
};           
queue<int>q;   
ll qpow(ll base,ll k) { ll tmp=1; for(;k;base=base*base%mod,k>>=1)if(k&1) tmp=tmp*base%mod; return tmp; }    
ll inv(int x) { return qpow(x, mod-2); }
ll ans=1; 
int n,m,s,t,edges;   
int hd[N],nex[N<<1],deg[N],dp[N],tp[N],to[N<<1];     
inline void addedge(int u,int v) { nex[++edges]=hd[u],hd[u]=edges,to[edges]=v; }  
inline ll bfs() 
{  
    int i;        
    dp[t]=ans;        
    for(i=1;i<=n;++i) if(!tp[i]) q.push(i);    
    while(!q.empty()) 
    {
        int u=q.front();q.pop();     
        dp[u]=dp[u]*inv(deg[u])%mod;   
        for(i=hd[u];i;i=nex[i]) 
        {
            int v=to[i];    
            dp[v]=(dp[v]+dp[u])%mod;    
            --tp[v]; 
            if(!tp[v]) q.push(v);   
        }
    }
    return (ans-dp[s]+mod)%mod;   
}
int main() 
{
    using namespace IO; 
    int i,j; 
    // setIO("input"); 
    n=rd(),m=rd(),s=rd(),t=rd(),++deg[t]; 
    for(i=1;i<=m;++i) 
    {
        int x=rd(),y=rd();   
        ++deg[y], ++tp[y], addedge(x,y);   
    }   
    for(i=2;i<=n;++i) ans=ans*deg[i]%mod;                     
    printf("%lld\n",t==1?ans:bfs());   
    return 0;    
}