洛谷 P3244 / loj 2115 [HNOI2015] 落忆枫音 题解【拓扑排序】【组合】【逆元】

（背景冗长请到题目页面查看）

输入输出样例

4 4 4 3
1 2
1 3
2 4
3 2


3


题解：

$$\prod_{i=2}^nd_i$$

$$sum=\prod_{i=2}^n\left(d_i+[i=y]\right)$$

$$f_u=\sum_{\left<u,v\right>\in E}\frac{f_v}{d_v}$$

$$ans=sum-\frac{f_x}{d_x}$$

Code：

#include<cstdio>
#include<cstring>
#define p 1000000007
int Plus(int x,int y)
{return (x+y>=p)?(x+y-p):(x+y);}
int Mul(int x,int y)
{return 1ll*x*y%p;}
struct edge
{
int n,nxt;
edge(int n,int nxt)
{
this->n=n;
this->nxt=nxt;
}
edge(){}
}e[200000];
int head[100100],ecnt=-1;
void add(int from,int to)
{
e[++ecnt]=edge(to,head[from]);
head[from]=ecnt;
}
int d[100100],in[100100];
//d表示真实入度 in表示拓扑排序中的入度
int q[100100],l=0,r=0;
int f[100100],inv[100100];
int main()
{
memset(head,-1,sizeof(head));
inv[1]=1;
for(int i=2;i<=100000;++i)
inv[i]=Mul(p-p/i,inv[p%i]);
int n,m,x,y,u,v;
scanf("%d%d%d%d",&n,&m,&x,&y);
for(int i=1;i<=m;++i)
{
scanf("%d%d",&u,&v);
add(v,u);
++in[u];
++d[v];
}
f[x]=1;
int sum=1;
for(int i=2;i<=n;++i)
{
if(!in[i])
q[++r]=i;
f[x]=Mul(f[x],d[i]);
sum=Mul(sum,d[i]+(i==y));
}
if(y==1)
{
printf("%d\n",sum);
return 0;
}
while(l<r)
{
int k=q[++l];
for(int i=head[k];~i;i=e[i].nxt)
{
--in[e[i].n];
f[e[i].n]=Plus(f[e[i].n],Mul(f[k],inv[d[k]]));
if(!in[e[i].n])
q[++r]=e[i].n;
}
}
printf("%d\n",Plus(sum,p-Mul(f[y],inv[d[y]])));
return 0;
}


4 说点什么

4 Comment threads
0 Thread replies
0 Followers

Most reacted comment
Hottest comment thread
0 Comment authors
Recent comment authors
Subscribe

… [Trackback]

[…] Info to that Topic: wjyyy.top/3322.html […]

… [Trackback]

[…] Info to that Topic: wjyyy.top/3322.html […]

… [Trackback]

[…] There you will find 97793 more Information on that Topic: wjyyy.top/3322.html […]

… [Trackback]

[…] Info on that Topic: wjyyy.top/3322.html […]

/* */