正题

题目链接:https://www.luogu.com.cn/problem/P3244

题目大意

给出一个\(\text{DAG}\)，保证\(1\)可以到达所有点。然后再加入一条边（之后不一定是\(\text{DAG}\)）。

求有多少棵以\(1\)为根的外向生成树。

\(1\leq n\leq 10^5,1\leq m\leq 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】

正题

题目大意

解题思路

code

最新文章

热门文章