【UOJ290】【LOJ2250】【ZJOI2017】仙人掌

Author Avatar
q234rty 3月 04, 2018

神仙数数题

（终于没有即可了233

首先，为了方便我们把每条不在任何一个环上的边加一条重边，视为在一个长度为 2 的环上。也就是说，把仙人掌的定义中没有重边且每条边在不超过一个环上改为可能有重边且每条边在刚好一个环上。

我们考虑原图是树的情况，设 f(u) 为 u 的子树中连边，并且选择一个点连向子树外（由于每条边在刚好一个环上，一定恰好有一个这样的点，我们称这个点为黑点），使得 u 的子树成为仙人掌的方案数。

考虑 u 的所有儿子的子树的黑点连向哪里。当 u 为根时，这些点要么连向 u （视为不配对），要么两两配对。否则，这些点中一定有不超过一个点连向 u 的子树外（成为新的黑点），我们认为这是和 u 子树外的联通块配对，如果没有，那么就是 u 成为新的黑点，视为 u 子树外的联通块不配对，而其它点和 u 为根的情况一样。

总之，设 h(n) 为 n 个点两两配对（可以不配对）的方案数。那么由乘法原理：

f(u)=h(deg(u))\times\prod_{v \in son(u)} f(v)

其中 deg(u) 表示 u 的度数， son(u) 表示 u 的儿子节点集合。

而 h(n) 可以直接递推：

h(n)=h(n-1)+(n-1) \times h(n-2)

这样就解决了原图是树的情况。

如果原图不是树，我们dfs出一棵生成树和一些返祖边，利用树上差分找出所有被返祖边覆盖过的边，特别的，如果有边被覆盖两次说明原图不是仙人掌，答案显然为 0 。否则我们把返祖边和被覆盖的边全部删去，得到一个森林，由于各个连通块之间显然不能连边，把各个连通块的答案乘起来就行了。

如果看不懂可以去看看cogito的题解。

Code

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=20000020;
  5. const int mod=998244353;
  6. int bufpos;
  7. char buf[MAXSIZE];
  8. #define NEG 0
  9. void init(){
  10. 	#ifdef LOCAL
  11. 		freopen("290.txt","r",stdin);
  12. 	#endif
  13. 	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  14. 	bufpos=0;
  15. }
  16. #if NEG
  17. int readint(){
  18. 	bool isneg;
  19. 	int val=0;
  20. 	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  21. 	bufpos+=(isneg=buf[bufpos]=='-');
  22. 	for(;isdigit(buf[bufpos]);bufpos++)
  23. 		val=val*10+buf[bufpos]-'0';
  24. 	return isneg?-val:val;
  25. }
  26. #else
  27. int readint(){
  28. 	int val=0;
  29. 	for(;!isdigit(buf[bufpos]);bufpos++);
  30. 	for(;isdigit(buf[bufpos]);bufpos++)
  31. 		val=val*10+buf[bufpos]-'0';
  32. 	return val;
  33. }
  34. #endif
  35. char readchar(){
  36. 	for(;isspace(buf[bufpos]);bufpos++);
  37. 	return buf[bufpos++];
  38. }
  39. int readstr(char* s){
  40. 	int cur=0;
  41. 	for(;isspace(buf[bufpos]);bufpos++);
  42. 	for(;!isspace(buf[bufpos]);bufpos++)
  43. 		s[cur++]=buf[bufpos];
  44. 	s[cur]='\0';
  45. 	return cur;
  46. }
  47. const int maxn=500004;
  48. const int maxm=maxn*4;
  49. ll h[maxn];
  50. struct graph{
  51. 	int n,m;
  52. 	struct edge{
  53. 		int to,next;
  54. 		bool del;
  55. 	}e[maxm];
  56. 	int first[maxn],cnt[maxn];
  57. 	void init(int n){
  58. 		this->n=n;
  59. 		memset(first,0,(n+1)*4);
  60. 		memset(cnt,0,(n+1)*4);
  61. 		m=1;
  62. 	}
  63. 	void addedge(int from,int to){
  64. 		e[++m]=(edge){to,first[from],0};
  65. 		first[from]=m;
  66. 	}
  67. 	bool vis[maxn];
  68. 	void dfs(int u,int fa){
  69. 		vis[u]=1;
  70. 		for(int i=first[u];i;i=e[i].next){
  71. 			int v=e[i].to;
  72. 			if (!vis[v])
  73. 				dfs(v,u);
  74. 			else if (v!=fa && !e[i].del){
  75. 				e[i].del=e[i^1].del=1;
  76. 				cnt[v]--,cnt[u]++;
  77. 				// printf("233 %d %d\n",v,u);
  78. 			}
  79. 		}
  80. 	}
  81. 	void dfs2(int u){
  82. 		vis[u]=1;
  83. 		for(int i=first[u];i;i=e[i].next){
  84. 			int v=e[i].to;
  85. 			if (!vis[v]){
  86. 				dfs2(v);
  87. 				// if (u==8 && v==2)
  88. 					// printf("%d %d\n",u,v);
  89. 				cnt[u]+=cnt[v];
  90. 				if (cnt[v])
  91. 					e[i].del=e[i^1].del=1;
  92. 			}
  93. 		}
  94. 	}
  95. 	int deg[maxn];
  96. 	ll work(){
  97. 		memset(vis,0,n+1);
  98. 		dfs(1,0);
  99. 		memset(vis,0,n+1);
  100. 		dfs2(1);
  101. 		memset(deg,0,(n+1)*4);
  102. 		for(int i=1;i<=n;i++)
  103. 			if (cnt[i]>=2)
  104. 				return 0;
  105. 		for(int i=2;i<=m;i++)
  106. 			if (!e[i].del)
  107. 				deg[e[i].to]++;
  108. 			// else printf("%d\n",e[i].to);
  109. 		ll ans=1;
  110. 		for(int i=1;i<=n;i++){
  111. 			// printf("deg[%d]=%d\n",i,deg[i]);
  112. 			ans=(ans*h[deg[i]])%mod;
  113. 		}
  114. 		return ans;
  115. 	}
  116. }g;
  117. int main(){
  118. 	init();
  119. 	h[0]=h[1]=1;
  120. 	for(int i=2;i<=500000;i++)
  121. 		h[i]=(h[i-1]+h[i-2]*(i-1))%mod;
  122. 	int T=readint();
  123. 	while(T--){
  124. 		int n=readint(),m=readint();
  125. 		g.init(n);
  126. 		while(m--){
  127. 			int u=readint(),v=readint();
  128. 			g.addedge(u,v);
  129. 			g.addedge(v,u);
  130. 		}
  131. 		printf("%lld\n",g.work());
  132. 	}
  133. }

Written with StackEdit.

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2018/03/04/uoj290/

隐藏