正解:拓扑排序+dp
解题报告:
我好暴躁昂,,,怎么感觉HNOI每年总有那么几道题题面巨长啊,,,语文不好真是太心痛辣QAQ
所以还是要简述一下题意,,,就是说,本来是有一个DAG,然后后来又加入辣一条有向边(x,y),求形成的树的方案数
首先从比较简单的想起,假如加入之后依然麻油环,那就直接计算每个点的入度in,然后tot=Πin[i]就好,还是挺好理解的趴,就每个点可以选从所有指向自己的边中选一条就好,显然都是合法的QwQ
然后所以就会多算,多算的就是加入边(x,y)之后形成的环的数量,算出这个就可以辣
然后考虑它本来保证辣是个DAG,那要形成环肯定是和新加入的(x,y)形成的,就一定是(y,x)的路径
然后题目就变成了统计(y,x)的路径的数量
然后再考虑到它是个有向图,又要形成一棵树,所以直接按拓扑排序后的顺序dp转移就好(然后其实直接拓扑排序的时候dp转移就好了w
还是大概说下怎么转移的趴,,,
设f[i]:强制令树经过节点i到节点y的路径的方案数
初始化是f[y]=ans,因为所有方案中一定都是经过了所有点的,那么y到y的方案数就是总方案数
然后转移是f[x.to]+=f[x]/in[x.to](,,,显然要用逆元,这里强行当作就是在取模意义下的除法就是辣w
理解还是比较好理解的趴,,,?懒得解释辣!
然后关于这里其实还可以有一个理解,推出来的柿子一样但是思想什么的还是比较不一样dei
就题目也可以当作是变成了求新加入的边与原有边构成的环的个数
假如现在枚举到了环S,这个环的构成的方案数就Πin[i](i∈S
那么这个环的贡献就是tot/Πin[i](i∈S
所以结果式子还是一样的,还是拓扑排序+dp转移,只是理解还是有点儿区别所以港下
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register
#define ll long long
#define gc getchar()
#define rp(i,x,y) for(rg ll i=x;i<=y;++i)
#define my(i,x,y) for(rg ll i=x;i>=y;--i)
#define e(x) for(rg ll i=head[x];i;i=edge[i].nxt)
#define t(i) edge[i].to const ll N=+,mod=;
ll n,m,xx,yy,in[N],inv[N],f[N],ed_cnt,head[N],as=;
queue<ll>Q;
struct ed{ll to,nxt;}edge[N<<]; il ll read()
{
rg char ch=gc;rg ll x=;rg bool y=;
while(ch!='-' && (ch<'' || ch>''))ch=gc;
if(ch=='-')ch=gc,y=;
while(''<=ch && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;
return y?x:-x;
}
il void ad(ll x,ll y){edge[++ed_cnt]=(ed){y,head[x]};head[x]=ed_cnt;++in[y];}
il ll ksm(ll x,ll y){ll as=;while(y){if(y&)as=as*x%mod;x=x*x%mod;y>>=;}return as;}
il void topsort()
{
f[yy]=as*inv[yy]%mod;rp(i,,n)if(!in[i])Q.push(i);
while(!Q.empty())
{
ll nw=Q.front();Q.pop();
e(nw){f[t(i)]=(f[t(i)]+f[nw]*inv[t(i)])%mod;--in[t(i)];if(!in[t(i)])Q.push(t(i));}
}
as=(as-f[xx])%mod;if(as<)as+=mod;printf("%lld\n",as);
} int main()
{
n=read();m=read();xx=read();yy=read();rp(i,,m){ll x=read(),y=read();ad(x,y);}++in[yy];
rp(i,,n)as=as*in[i]%mod;rp(i,,n)inv[i]=ksm(in[i],mod-);--in[yy];
if(yy==)return printf("%lld\n",as),;topsort();
return ;
}