BZOJ 4011 【HNOI2015】落忆枫音

题目链接：落忆枫音

　　以下内容参考PoPoQQQ大爷的博客

　　首先我们先来考虑一下如果没有新加入的那条边，答案怎么算。

　　由于这是一个\(DAG\)，所以我们给每个点随便选择一条入边，最后一定会构成一个树形图。于是答案就是除\(1\)号点之外所有点的入度之积。

　　现在新加入了一条边，如果形成了一个环并且\(1\)号点不在环上的话，我们给每个点随便选择入边，就可能会出现选出一个环的情况。

　　所以，我们需要考虑把这部分答案给掉。令\(S_{x\to y}\)表示\(x\)到\(y\)的任意一条路径，\(degree_u\)表示点\(u\)的入度，不难发现，我们要减去的答案就是：

\(\sum_{S_{y\to x}}\prod_{u\notin S}degree_u\)

　　然后我们就可以\(dp\)了。令\(f_i\)表示\(\sum_{S_{i\to x}}\prod_{u\notin S}degree_u\)，那么转移就很好转了。注意边界是\(f_x\)。

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define mod 1000000007

#define maxn 100010

#define maxm 400010

using namespace std;

typedef long long llg;

int n,m,du[maxn];

int head[maxn],next[maxm],to[maxm],tt;

llg f[maxn],ans;

bool vis[maxn];

int getint(){

	int w=0;bool q=0;

	char c=getchar();

	while((c>'9'||c<'0')&&c!='-') c=getchar();

	if(c=='-') c=getchar(),q=1;

	while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();

	return q?-w:w;

}

void gi(llg &x){if(x>=mod) x%=mod;}

llg mi(llg a,int b){

	llg s=1;

	while(b){

		if(b&1) s=s*a,gi(s);

		a=a*a,gi(a); b>>=1;

	}

	return s;

}

llg dfs(int u){

	if(vis[u]) return f[u]; vis[u]=1;

	for(int i=head[u];i;i=next[i])

		f[u]+=dfs(to[i]),gi(f[u]);

	f[u]*=mi(du[u],mod-2);

	gi(f[u]); return f[u];

}

int main(){

	File("maple");

	n=getint(); m=getint();

	int x=getint(),y=getint();

	while(m--){

		int u=getint(),v=getint(); du[v]++;

		to[++tt]=v;next[tt]=head[u];head[u]=tt;

	}

	du[y]++; ans=1;

	for(int i=2;i<=n;i++) ans*=du[i],gi(ans);

	if(y!=1 && x!=1){

		vis[x]=1; f[x]=ans*mi(du[x],mod-2);

		gi(f[x]); ans-=dfs(y);

		ans%=mod; if(ans<0) ans+=mod;

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

BZOJ 4011 【HNOI2015】落忆枫音

最新文章

热门文章

巴特西

BZOJ 4011 【HNOI2015】 落忆枫音

最新文章

热门文章

BZOJ 4011 【HNOI2015】落忆枫音