P3244 [HNOI2015]落忆枫音

思路

给出了一个DAG，要求以1为根的外向树的个数

如果没有加边的条件，就非常好做

每个点都只保留一条入边，最后得到的一定就是一个符合条件的树了（因为给了一个DAG啊）

所以答案是\(\prod_{i=2}^nd_i\)

加上一条边时候，可能会出现环的情况，要把它去掉

假设环中的点是\(a_1,a_2,a_3,\dots,a_k\)，去掉的情况数就是\(\frac{\prod_{i=2}^nd_i}{\prod_{i=1}^kd_{a_i}}\)（除了环上的点之外其他随便选，成环只有环上的点每个点都选择环上的边的一种情况）

对后面的式子在原DAG上直接拓扑求一下就好了

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

#define int long long

using namespace std;

const int MOD = 1000000007;

int n,m,x,y;

int u[100100<<1],v[100100<<1],fir[100100],nxt[100100<<1],d[100100],cnt,f[100100],ans,d_t[100100];

void addedge(int ui,int vi){

    ++cnt;

    u[cnt]=ui;

    v[cnt]=vi;

    d[vi]++;

    d_t[vi]++;

    nxt[cnt]=fir[ui];

    fir[ui]=cnt;

}

int pow(int a,int b){

    int ans=1;

    while(b){

        if(b&1)

            ans=(ans*a)%MOD;

        a=(a*a)%MOD;

        b>>=1;

    }

    return ans;

}

queue<int> q;

void topu(void){

    f[y]=ans;

    for(int i=1;i<=n;i++)

        if(!d_t[i])

            q.push(i);

    while(!q.empty()){

        int x=q.front();

        q.pop();

        f[x]=(f[x]*pow(d[x],MOD-2))%MOD;

        for(int i=fir[x];i;i=nxt[i]){

            f[v[i]]=(f[v[i]]+f[x])%MOD;

            d_t[v[i]]--;

            if(!d_t[v[i]])

                q.push(v[i]);

        }

    }

}

signed main(){

    scanf("%lld %lld %lld %lld",&n,&m,&x,&y);

    d[y]++;

    for(int i=1;i<=m;i++){

        int a,b;

        scanf("%lld %lld",&a,&b);

        addedge(a,b);

    }

    ans=1;

    for(int i=2;i<=n;i++)

        ans=(ans*d[i])%MOD;

    if(y==1){

        printf("%lld\n",ans);

        return 0;

    }

    topu();

    printf("%lld\n",(ans-f[x]+MOD)%MOD);

    return 0;

}

巴特西

P3244 [HNOI2015]落忆枫音

思路

代码

最新文章

热门文章