【題解】HNOI-2015落憶楓音

Problem

真·bzoj

真的不要強行看題面，簡要題意：

給定一個DAG，在DAG上加一條題目指定的邊，求新圖上的樹形圖個數

Solution

發現如果忽略新加的一條邊的話答案就是所有節點入度的乘積

但題目中在DAG上新加了一條邊，那麼答案一定有重的，重的就是加上這條邊後形成的環，那麼最終的答案就是原來的答案減去包含這個環的樹形圖個數，其實相當于在原DAG上拓撲找到從新邊終點到新邊起點的路徑上有多少包含這條鍊的樹形圖，和統計DAG中的答案類似，就是總答案除以這個子DAG上的點的入度積，最後用原答案減去這個即可

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg register
#define cl(x) memset(x,0,sizeof(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?(x):(-(x)))

template <typename _Tp> inline _Tp read(_Tp&x){
    rg char c11=getchar(),ob=;x=;
    while(c11^'-'&&!isdigit(c11))c11=getchar();if(c11=='-')c11=getchar(),ob=;
    while(isdigit(c11))x=x*+c11-'0',c11=getchar();if(ob)x=-x;return x;
}

const ll p=;
const int N=,M=;
struct Edge{int v,nxt;}a[M];
int head[N],deg[N],cnt[N],inv[max(N,M)],n,m,s,t,_();
ll f[N],ans();

void pre(int li){
    inv[]=;
    for(rg int i=;i<=li;++i)
        inv[i]=l*(p-p/i)*inv[p%i]%p;
    return ;
}

inline void add(int u,int v){a[++_].v=v,a[_].nxt=head[u],head[u]=_;}

void topology(){
    f[t]=ans;
    queue <int> q;while(!q.empty())q.pop();
    for(rg int i=;i<=n;++i)
        if(!(cnt[i]=deg[i]))q.push(i);
    --cnt[t];
    while(!q.empty()){
        rg int x=q.front();q.pop();
        f[x]=l*f[x]*inv[deg[x]]%p;
        for(rg int i=head[x];i;i=a[i].nxt){
            f[a[i].v]=(f[a[i].v]+f[x])%p;
            if(!(--cnt[a[i].v]))q.push(a[i].v);
        }
    }
}

int main(){
    read(n),read(m);read(s),read(t);
    pre(max(n,m));++deg[t];
    for(rg int i=,x,y;i<m;++i)
        read(x),read(y),add(x,y),++deg[y];
    for(rg int i=;i<=n;++i)ans=l*ans*deg[i]%p;
    if(t==){printf("%lld\n",ans);return ;}
    topology();
    printf("%lld\n",(ans-f[s]+p)%p);
    return ;
}