[HNOI2015]落忆枫音

题目

题目

做法

看题解的

不难发现,在DAG上这种神奇的树的方案是把每个点的入度乘起来,所以(ans=prodlimits_{i=1}^{n}du(i))。((du)就是入度)

但是出现环怎么处理呢?

我们考虑减去环的贡献。

我们假设现在的环是(a_1->a_2->a_3->...->a_k),那么多余的贡献就是(frac{ans}{prodlimits_{i=1}^{k}du(a_{i})}),因为除了环上是固定的,其他都可以随便向入度连边,所以用(ans)除去环上的入度即可即可。

如果你不能理解,我用一个引理你应该可以更懂一点。
这种构造方案最多存在一个简单环。
首先由于父亲边唯一,且保证(n-1)条边,所以最多是基环树森林,但事实上,每个环都必须经过新加入的边,所以最多只有一个简单环,即一个基环树,一个普通的树,证毕。

但是关键是枚举两个不同的环方案有没有可能相同?(https://www.luogu.com.cn/discuss/show/250508)
实际上是没有可能的,因为基环树的基环都不同。

好,那么关键就是如何统计的问题了,我们发现环必须经过新给出的边,所以另外一条实际上是(x->y)的路径((y->x)是新加入的边),而这个路径,我们实际上可以直接用DAG DP转移,设(g[k])(x->k)的路径的(sumfrac{ans}{路径经过点的入度乘积}),直接拓扑转移即可。

最后直接减去(g[y])就是答案。

代码

我也不知道为什么我要建反图,明明正图就可以了

时间复杂度:(O(nlog{mod}))(因为要算逆元)

但需要注意的是,如果新加入边的终点为(1),则不可以加入,因为(1)必须是根。

同时自环不会成为树边,也可以不管,而且因为管了,DFS可能会出错,所以直接不加入。

#include<cstdio>
#include<cstring>
#define  N  110000
#define  M  210000
using  namespace  std;
typedef  long  long  LL;
int  n,m,tx,ty;
LL  mod=1e9+7;
inline  LL  ksm(LL  x,int  y)
{
	LL  ans=1;
	while(y)
	{
		if(y&1)ans=(ans*x)%mod;
		x=(x*x)%mod;y>>=1;
	}
	return  ans;
}
struct  node
{
	int  y,next;
}a[M];int  len,last[N];
inline  void  ins(int  x,int  y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;}
LL  in[N],out[N],pin[N],ans=1,g[N];
bool  v[N];
void  dfs1(int  x)
{
	v[x]=1;
	for(int  k=last[x];k;k=a[k].next)
	{
		int  y=a[k].y;out[y]++;
		if(!v[y])dfs1(y);
	}
}
void  dfs(int  x)
{
	for(int  k=last[x];k;k=a[k].next)
	{
		int  y=a[k].y;out[y]--;
		g[y]+=g[x]*pin[y];g[y]%=mod;
		if(!out[y])dfs(y);
	}
}
int  main()
{
	scanf("%d%d%d%d",&n,&m,&tx,&ty);
	for(int  i=1;i<=m;i++)
	{
		int  x,y;scanf("%d%d",&x,&y);
		ins(y,x);
		in[y]++;
	}
	if(!(tx==ty  ||  ty==1))in[ty]++;
	for(int  i=2;i<=n;i++)
	{
		if(!in[i])
		{
			printf("0
");
			return  0;
		}
		pin[i]=ksm(in[i],mod-2);
		ans=ans*in[i]%mod;
	}
	if(!(tx==ty  ||  ty==1))
	{
		dfs1(tx);out[tx]--;
		g[tx]=(ans*pin[tx])%mod;
		dfs(tx);
		ans-=g[ty];ans=(ans+mod)%mod;
	}
	printf("%lld
",ans);
	return  0;
}

小结

如果一个有向图中只有一个点数大于等于二的强连通分量,那么在考虑过程中,可以先不管环进行DP,最后单独考虑把环的情况,并减去。(反正我当时就死脑筋想着如何把分量的情况像DAG一样搞出来,结果死活搞不出来,最后告诉我是容斥,实际上环的处理方法确实有容斥)

【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/zhangjianjunab/p/13805665.html