淘宝客网站源码加各类插件,柳江网站虚拟主机公司,口碑好的定制网站建设服务商,长春iso认证公司传送门 md这题和矩阵树定理没半毛钱关系qwq 首先先不考虑有环,一个\(DAG\)个外向树个数为\(\prod_{i2}^{n}idg_i(\)就是\(indegree_i)\),因为外向树每个点入度为一,对于一个点有入度个父亲可选,然后乘法原理起来就是答案 现在可能加一条边会有环,那么答案可以考虑总方案减不合法…传送门 md这题和矩阵树定理没半毛钱关系qwq 首先先不考虑有环,一个\(DAG\)个外向树个数为\(\prod_{i2}^{n}idg_i(\)就是\(indegree_i)\),因为外向树每个点入度为一,对于一个点有入度个父亲可选,然后乘法原理起来就是答案 现在可能加一条边会有环,那么答案可以考虑总方案减不合法方案,不合法的有环方案就是环内的点连好了,然后剩下的点贡献方案,设\(s\)是个环,那么方案为\(\sum_{s}\prod_{i\notin s}idg_i\sum_{s}\frac{\prod_{i2}^{n}idg_i}{\prod_{i\in s}idg_i}\prod_{i2}^{n}idg_i\sum_{s}\frac{1}{\prod_{i\in s}idg_i}\) 后面那个东西,因为加了边\(x\rightarrow y\),所以一条\(y\)到\(x\)可以确定一个环,那么以\(y\)为初始状态,可拓扑排序一遍dp出来方案 注意\(y1\)的情况 #includebits/stdc.h
#define LL long long
#define db double
#define il inline
#define re registerusing namespace std;
const int N1e510,mod1e97;
il int rd()
{int x0,w1;char ch0;while(ch0||ch9) {if(ch-) w-1;chgetchar();}while(ch0ch9) {x(x3)(x1)(ch^48);chgetchar();}return x*w;
}
int to[N1],nt[N1],hd[N],dg[N],idg[N],tot;
void add(int x,int y){tot,to[tot]y,nt[tot]hd[x],hd[x]tot,dg[y];}
int n,m,u,v,f[N],inv[N];
queueint q;int main()
{nrd(),mrd(),urd(),vrd();for(int i1;im;i){int xrd(),yrd();add(x,y);}int ans1;for(int i2;in;i) ans1ll*ans*(dg[i](vi))%mod;if(v!uv!1){memcpy(idg,dg,sizeof(dg));inv[0]inv[1]1;for(int i2;in1;i) inv[i](mod-1ll*mod/i*inv[mod%i]%mod)%mod;f[v]1,q.push(1);while(!q.empty()){int xq.front();q.pop();f[x]1ll*f[x]*inv[dg[x](xv)]%mod;for(int ihd[x];i;int[i]){int yto[i];f[y](f[y]f[x])%mod,--idg[y];if(!idg[y]) q.push(y);}}ans1ll*ans*(1-f[u]mod)%mod;}printf(%d\n,ans);return 0;
} 转载于:https://www.cnblogs.com/smyjr/p/10433079.html
