这个题目感觉还是比较奇妙的, 虽然难度不是很大

做法主要还是一个拓扑图上的dp, 因为新图只是在原图(有向无环图)上添加了一条边, 所以做法肯定还是从有向无环图中拓展出来的。

比较重要的一个idea就是\(\text{ans}=\text{sum}-\text{illegal}\)

题目链接

题目大意

在一个有向无环图上添加一条边, 问新图以\(1\)为根的有向生成树的个数。

解题报告

如果没有新加入的一条边, 那么原图(一个有向无环图)的有向生成树的个数为除点\(1\)外所有点的入度的乘积, 记为\(\text{sum}\)

新加入一条边,如果这条边是\(x \rightarrow 1\) 的形式, 那么显然这个对答案没有影响(≧▽≦)/啦啦啦

否则, 按照之前的方式算出了的答案, 其中有一部分是带环的, 并且\(x \rightarrow y\)是这个方案中的边 。

考虑统计过气答案中的不合法方案, 可以发现 ,不合法的方案中\(y\)点的入边选择的是\(x \rightarrow y\) , 如果这个方案中, 存在\(y \rightarrow x\)的路径, 那么就存在一个环。

如果\(S_{y \rightarrow x}\)表示一条\(y \rightarrow x\)的一条路径, 不合法方案数是\(\sum_{S_{y \rightarrow x}}\prod_{u\notin S}degree_u\)

\(f[x]\)表示\(\sum_{S_{y \rightarrow x}}\prod_{u \notin S} \text{degree}_u\), 只需要令\(\prod_{S_{y \rightarrow x}} \text{degree}_u = \frac{sum}{\prod_{u \in S} \text{degree}_u}\) ,就非常好转移了。

最终的\(\text{ans}=\text{sum}-f[x]\) .

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=int(a),nn=int(b);i<=nn;++i)
#define vep(i,a,b) for(int i=int(a),nn=int(b);i>=nn;--i)
#define xep(i,b) for(int i=0,nn=int(b);i<nn;++i)
typedef long long ll;
const int N=100010;
const int p=1000000007;
struct edge {
int nxt,to; edge(int nxt=0,int to=0)
:nxt(nxt),to(to){}
} e[N<<1];
int inv[N],n,m,hed[N],tot,in[N],x,y; ll as=1;
template <typename T> inline void read(T &x) {
char ch=getchar(); int f=1;
for (;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
for (x=0;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48;
x*=f;
}
inline void add(int x,int y) {
e[++tot]=edge(hed[x],y),++in[y],hed[x]=tot;
}
inline void init() {
inv[1]=1; rep(i,2,n) inv[i]=p-1ll*(p/i)*inv[p%i]%p;
}
inline void topo() {
queue<int> q; q.push(1); int o,nx;
static int _in[N],f[N]; f[y]=as;
rep(i,1,n) _in[i]=in[i]; --_in[y];
while (!q.empty()) {
o=q.front(); q.pop();
f[o]=1ll*f[o]*inv[in[o]]%p;
for (int i=hed[o];i;i=e[i].nxt)
if (nx=e[i].to, _in[nx]) {
f[nx]=(f[nx]+f[o])%p;
--_in[nx]; if (!_in[nx]) q.push(nx);
}
}
as=as-f[x]; if (as<0) as+=p;
}
int main() {
read(n),read(m),read(x),read(y); int a,b;
xep(i,m) read(a),read(b),add(a,b);
++in[y];
rep(i,2,n) as=as*in[i]%p;
if (y==1) return printf("%lld\n",as),0;
init(), topo();
return printf("%lld\n",as),0;
}

留言