正題

題目鏈接:https://www.luogu.com.cn/problem/P3244

---

題目大意

給出一個$\text{DAG}$，保證$1$可以到達所有點。然后再加入一條邊（之后不一定是$\text{DAG}$）。

求有多少棵以$1$為根的外向生成樹。

$1\le n\le 10^5,1\le m\le 2\times 10^5$

---

解題思路

發現不考慮加邊都不會做/kk

其實結論不難想也很顯然，就是除了一號點以外所有點的入度乘積（每個點選擇一個父親，因為是$\text{DAG}$所以一定沒有環）

然后加一條邊怎么搞，因為可能會生成環。

可以考慮直接減去環的方案，設$del$表示加邊前的總方案，那么對于每個環上所有點的度數乘積$k$，需要減去的方案就是$\frac{del}{k}$。

現在考慮如何計算所有點的度數乘積的倒數和。

不難搞，直接$\text{DAGdp}$或者記億化$dp$隨便搞搞都可以

時間復雜度$O(n+m)$（如果線性預處理了逆元的話）

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2e5+10,P=1e9+7; struct node{ll to,next; }a[N<<1]; ll n,m,u,v,tot,ls[N],deg[N],g[N]; bool vis[N]; ll power(ll x,ll b){ll ans=1;while(b){if(b&1)ans=ans*x%P;x=x*x%P;b>>=1;}return ans; } void addl(ll x,ll y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(ll x){if(vis[x])return;vis[x]=1;if(x==u){g[x]=power(deg[x],P-2)%P;return;}for(ll i=ls[x];i;i=a[i].next)dfs(a[i].to),(g[x]+=g[a[i].to])%=P;g[x]=g[x]*power(deg[x],P-2)%P; } signed main() {scanf("%lld%lld%lld%lld",&n,&m,&u,&v);for(ll i=1;i<=m;i++){ll x,y;scanf("%lld%lld",&x,&y);addl(x,y);deg[y]++;}deg[1]++;ll ans=1,del=1;for(ll i=1;i<=n;i++)ans=ans*(deg[i]+(i==v))%P,del=del*deg[i]%P;dfs(v);printf("%lld\n",(ans-g[v]*del%P+P)%P); }

總結

以上是生活随笔為你收集整理的P3244-[HNOI2015]落忆枫音【dp】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。