题意简述
给定点
边的简单无向连通图。
现在要在图上加若干边,要求加边后还是一个简单无向连通图,且每条边至多属于一个简单环。
求加边方案数对取模的值。
算法讨论
考后再写一遍的时候发现写的好快啊QAQ
先判一下原图是不是仙人掌。具体可以先DFS一棵生成树,就有许多返祖边,树上差分一下就可以求出每个点连向父亲的边被覆盖了多少次,大于一次就无解。特殊地,等于一次的边就是环边。
首先发现加的边不可能经过某个环。也就是说,环把仙人掌分成若干棵树。树与树之间是相互独立的。所以我们可以对每棵树统计加边方案数再相乘。
问题就转化成在一棵树上加边变成仙人掌的方案数。这个问题还是有点难求。不妨考虑判定仙人掌的过程,每条边至多被覆盖一次。那么连一个环就相当于覆盖一条路径。于是问题等价于树上每条边至多被覆盖一次的路径覆盖方案数。我们发现有个至多的条件很讨厌,什么时候某条边没有被覆盖呢?就是这条边在最终方案中是一条树边。那我们可以把它强行考虑成一个两元环。就可以把问题等价成每条边恰好被覆盖一次的路径覆盖方案数了。
这个问题一看就是DP。设为
子树的答案。首先
的所有儿子内部的覆盖方案是相互独立的,于是可以先把儿子的答案先相乘。接下来我们可以发现如果这个点不是根,至多有一个儿子的路径可以经过
继续向上延伸,我们就以这个标准分一下类。
如果没有这样的儿子,那么一定有一些儿子两两配对成一些路径,其余的儿子连到根到就终止了。设个儿子时的方案数是
,考虑枚举配对的儿子对数
,有
就是
个点两两配对的方案数,推一推可以发现
如果有这样的儿子,考虑枚举是哪一个,对系数的贡献是。
把系数计算出来乘上去就转移完了。整个过程特别小清新,给出题人点个赞!
时间复杂度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
#include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ struct edge { int next,to; }; LL pow_mod(LL b,LL p,LL k) { LL res=1; for(;p;p>>=1) { if(p&1) res=res*b%k; b=b*b%k; } return res; } const int maxn=(int)(2e6)+5; const int mo=998244353; int fr[maxn]; int vi[maxn]; int bt[maxn]; int bi[maxn]; int dep[maxn]; LL f[maxn]; LL fac[maxn]; LL ivf[maxn]; LL pw[maxn]; edge e[maxn<<1]; int tote; inline void addone(int u,int v) { ++tote; e[tote].next=fr[u];fr[u]=tote;e[tote].to=v;bi[tote]=0; } inline void addedge(int u,int v) { addone(u,v);addone(v,u); } void _dfs(int x,int f) { vi[x]=1; dep[x]=dep[f]+1; RAL(i,x) if(e[i].to!=f) { if(!vi[e[i].to]) _dfs(e[i].to,x); else if(dep[e[i].to]<dep[x]) { bt[x]++;bt[e[i].to]--; } } } int fl; void _gatherS(int x) { RAL(i,x) if(dep[x]+1==dep[e[i].to]) { _gatherS(e[i].to);bt[x]+=bt[e[i].to]; if(!bt[e[i].to]) bi[i]=bi[i^1]=1; } if(bt[x]>1) fl=0; } inline LL C(int a,int b) { if(a<b) return 0; return (fac[a]*ivf[a-b]%mo)*ivf[b]%mo; } inline LL F(int x) { return (pw[x]*C(2*x,x)%mo)*fac[x]%mo; } inline LL gen(int x) { LL res=0; REP(i,0,x) if(!(i&1)) (res+=F(i/2)*C(x,i))%=mo; return res; } int rt; void dfs(int x,int fa) { f[x]=1;vi[x]=1;int idx=0; RAL(i,x) if(bi[i] && e[i].to!=fa) { dfs(e[i].to,x);f[x]=f[x]*f[e[i].to]%mo;++idx; } if(!idx) return; LL now=gen(idx);if(x!=rt) (now+=gen(idx-1)*idx)%=mo; f[x]=f[x]*now%mo; } void solve() { int n,m; read(n);read(m); REP(i,1,n) fr[i]=-1,vi[i]=bt[i]=0;tote=-1; REP(i,1,m) { int u,v; read(u);read(v); addedge(u,v); } fl=1;_dfs(1,0);_gatherS(1); if(!fl) { printf("0\n");return; } LL res=1; REP(i,1,n) vi[i]=0; REP(i,1,n) if(!vi[i]) { rt=i;dfs(i,0);res=res*f[i]%mo; } printf("%lld\n",res); } inline void initS() { int mx=1000000; pw[0]=fac[0]=ivf[0]=1; REP(i,1,mx) fac[i]=fac[i-1]*i%mo; ivf[mx]=pow_mod(fac[mx],mo-2,mo); PER(i,mx-1,1) ivf[i]=ivf[i+1]*(i+1)%mo; LL c=pow_mod(2,mo-2,mo); REP(i,1,mx) pw[i]=pw[i-1]*c%mo; } int main() { initS(); int T; read(T); while(T--) solve(); return 0; } |