题目描述
不妨假设枫叶上有 n个穴位，穴位的编号为 1 ~ n。有若干条有向的脉络连接
着这些穴位。穴位和脉络组成一个有向无环图——称之为脉络图（例如图 1），穴
位的编号使得穴位 1 没有从其他穴位连向它的脉络，即穴位 1 只有连出去的脉络；
由上面的故事可知，这个有向无环图存在一个树形子图，它是以穴位 1为根的包含
全部n个穴位的一棵树——称之为脉络树（例如图 2和图 3给出的树都是图1给出
的脉络图的子图）；值得注意的是，脉络图中的脉络树方案可能有多种可能性，例
如图2和图 3就是图 1给出的脉络图的两个脉络树方案。
脉络树的形式化定义为：以穴位 r 为根的脉络树由枫叶上全部 n个穴位以及 n
- 1 条脉络组成，脉络树里没有环，亦不存在从一个穴位连向自身的脉络，且对于
枫叶上的每个穴位 s，都存在一条唯一的包含于脉络树内的脉络路径，使得从穴位
r 出发沿着这条路径可以到达穴位 s。
现在向脉络图添加一条与已有脉络不同的脉络（注意：连接 2个穴位但方向不
同的脉络是不同的脉络，例如从穴位3到4的脉络与从4到3的脉络是不同的脉络，
因此，图 1 中不能添加从 3 到 4 的脉络，但可添加从 4 到 3 的脉络），这条新脉络
可以是从一个穴位连向自身的（例如，图 1 中可添加从 4 到 4 的脉络）。原脉络图
添加这条新脉络后得到的新脉络图可能会出现脉络构成的环。
请你求出添加了这一条脉络之后的新脉络图的以穴位 1 为根的脉络树方案数。
由于方案可能有太多太多，请输出方案数对 1,000,000,007 取模得到的结果。
题解
如果它是一个DAG，那么方案数就是除了根以外的所有点的入度之积。
那么如果有环，需要把所有环的方案数减掉。
如果我们枚举了一个环，那么这个环上所有点的选择方式已经确定，那么其他点的父亲可以随便选，方案数为Πd[i]/Πd[u]，u为环上的点。
这个可以用记搜实现。
注意连向1的边没有意义，要判掉。
代码
#include#include #define N 100002 using namespace std; typedef long long ll; const int mod=1e9+7; int n,m,tot,head[N],xx,yy; bool vis[N]; ll dp[N],ans=1,du[N]; struct edge{int n,to; }e[N<<1]; inline int rd(){int x=0;char c=getchar();bool f=0;while(!isdigit(c)){ if(c=='-')f=1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}return f?-x:x; } inline ll power(ll x,ll y){ll ans=1;while(y){ if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans; } inline void add(int u,int v){e[++tot].n=head[u];e[tot].to=v;head[u]=tot; } void dfs(int u){if(vis[u])return;vis[u]=1;if(u==xx){dp[u]=ans*power(du[u],mod-2)%mod;return;}for(int i=head[u];i;i=e[i].n){int v=e[i].to;dfs(v);(dp[u]+=dp[v])%=mod;}dp[u]=dp[u]*power(du[u],mod-2)%mod; } int main(){n=rd();m=rd();xx=rd();yy=rd();int x,y;for(int i=1;i<=m;++i){x=rd();y=rd();add(x,y);du[y]++;}du[yy]++;ans=1;for(int i=1;i<=n;++i)if(du[i])ans=ans*du[i]%mod;if(yy!=1)dfs(yy); cout<<(ans-dp[yy]+mod)%mod;return 0; }