題目描述

不妨假設楓葉上有 n個穴位，穴位的編號為 1 ~ ?n。有若干條有向的脈絡連接 著這些穴位。穴位和脈絡組成一個有向無環(huán)圖——稱之為脈絡圖（例如圖 1），穴 位的編號使得穴位 1 沒有從其他穴位連向它的脈絡，即穴位 1 只有連出去的脈絡； 由上面的故事可知，這個有向無環(huán)圖存在一個樹形子圖，它是以穴位 1為根的包含 全部n個穴位的一棵樹——稱之為脈絡樹（例如圖 2和圖 3給出的樹都是圖1給出 的脈絡圖的子圖）；值得注意的是，脈絡圖中的脈絡樹方案可能有多種可能性，例 如圖2和圖 3就是圖 1給出的脈絡圖的兩個脈絡樹方案。? 脈絡樹的形式化定義為：以穴位 r 為根的脈絡樹由楓葉上全部 n個穴位以及 n - ?1 條脈絡組成，脈絡樹里沒有環(huán)，亦不存在從一個穴位連向自身的脈絡，且對于 楓葉上的每個穴位 s，都存在一條唯一的包含于脈絡樹內(nèi)的脈絡路徑，使得從穴位 r 出發(fā)沿著這條路徑可以到達穴位 s。? 現(xiàn)在向脈絡圖添加一條與已有脈絡不同的脈絡（注意：連接 2個穴位但方向不 同的脈絡是不同的脈絡，例如從穴位3到4的脈絡與從4到3的脈絡是不同的脈絡， 因此，圖 1 中不能添加從 3 到 4 的脈絡，但可添加從 4 到 3 的脈絡），這條新脈絡 可以是從一個穴位連向自身的（例如，圖 1 中可添加從 4 到 4 的脈絡）。原脈絡圖 添加這條新脈絡后得到的新脈絡圖可能會出現(xiàn)脈絡構(gòu)成的環(huán)。? 請你求出添加了這一條脈絡之后的新脈絡圖的以穴位 1 為根的脈絡樹方案數(shù)。 由于方案可能有太多太多，請輸出方案數(shù)對 1,000,000,007 取模得到的結(jié)果。? 題解 如果它是一個DAG，那么方案數(shù)就是除了根以外的所有點的入度之積。 那么如果有環(huán)，需要把所有環(huán)的方案數(shù)減掉。 如果我們枚舉了一個環(huán)，那么這個環(huán)上所有點的選擇方式已經(jīng)確定，那么其他點的父親可以隨便選，方案數(shù)為Πd[i]/Πd[u]，u為環(huán)上的點。 這個可以用記搜實現(xiàn)。 注意連向1的邊沒有意義，要判掉。 代碼

#include<iostream>
#include<cstdio>
#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;
}

轉(zhuǎn)載于:https://www.cnblogs.com/ZH-comld/p/10464461.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。