洛谷3244 [HNOI2015]落忆枫音

Luogu

BZOJ

分析

先考虑一个$\texttt{DAG}$的情况。记 $i$ 节点的入度为 $deg[i]$ ,显然答案为$\prod\limits_{i=1}^ndeg[i]$。

因为每个节点可以任意选一个父节点,根据乘法原理,答案就是这个。


现在加了一条边,原图中可能会出现一个环。于是要将成环的情况减掉。

考虑一下成环大概是什么情况,发现是选择了一条 $x\to y$ 的路径,然后又选择了 $(y,x)$ 这条边。

于是来考虑环上多贡献的答案,此时环上的每个点的父节点固定了,不在环上的点的父节点仍然可以任意选,也就是 $\prod\limits_{i\not\in circle}deg[i]$ 。


进一步考虑每一个点的贡献。为了方便,设加入的边是 $(s,t)$ 。

设 $f[i]$ 表示 $i\to s$ 的所有路径产生的贡献。

然后有 $f[i]=\sum\limits_{S}\prod\limits_{i\not\in S}deg[i]$ ,这里的 $S$ 表示一条 $i\to s$ 的路径上的点的集合。

于是就可以推出转移:$f[i]=\sum\limits_{(i,v)\in E}\frac{f[v]}{deg[i]}$。

记搜一下就行了。


最后答案就是$(\prod\limits_{i=1}^n deg[i])-f[t]$。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const int M=200000+10;
const int mod=1e9+7;

struct Edge { int v,nxt; } e[M];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int n,m,s,t,ans=1,sum=1;
int deg[N],inv[N],f[N];

inline int dfs(int u) {
    if (f[u]!=-1) return f[u];
    if (u==s) return f[u]=1ll*sum*inv[deg[u]]%mod;
    int res=0;
    for (re int i=head[u];i;i=e[i].nxt)
        res=(res+dfs(e[i].v))%mod;
    res=1ll*res*inv[deg[u]]%mod;
    return f[u]=res;
}

int main() {
    n=read(),m=read(),s=read(),t=read();
    for (re int i=1;i<=m;++i) {
        int u=read(),v=read();
        addEdge(u,v),++deg[v];
    }
    ++deg[1];
    for (re int i=1;i<=n;++i) {
        if (i==t) ans=1ll*ans*(deg[i]+1)%mod;
        else ans=1ll*ans*deg[i]%mod;
        sum=1ll*sum*deg[i]%mod;
    }
    inv[0]=inv[1]=1;
    for (re int i=2;i<=n;++i) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
    memset(f,-1,sizeof(f)); ans=(ans-dfs(t)+mod)%mod;
    printf("%d\n",ans);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 09 PM

发表评论