fork download
copy 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <complex>
  5. #include <cstring>
  6. #include <cstdlib>
  7. #include <string>
  8. #include <vector>
  9. #include <cstdio>
  10. #include <cmath>
  11. #include <map>
  12. #include <set>
  13. using namespace std;
  14. //#pragma comment(linker,"/STACK:102400000,102400000")
  15.  
  16. const int MAXN = 101;
  17. const int MAXM = 1000001;
  18. long long mod = 1000000009LL;
  19.  
  20. long long power(long long a, long long b)
  21. {
  22. 	long long ret = 1;
  23. 	while(b)
  24. 	{
  25. 		if(b&1)
  26. 			ret = (ret * a) % mod;
  27. 		a = (a * a) % mod;
  28. 		b /= 2;
  29. 	}
  30. 	return ret;
  31. }
  32.  
  33. long long inv(long long x)
  34. {
  35. 	return power(x, mod - 2);
  36. }
  37.  
  38. long long factorial[MAXN];
  39. long long invFactorial[MAXN];
  40.  
  41. long long C(int aPlusb, int a)
  42. {
  43. 	int b = aPlusb - a;
  44. 	if(a < 0 || b < 0) return 0;
  45. 	long long ret = invFactorial[a] * invFactorial[b];
  46. 	ret %= mod;
  47. 	ret *= factorial[aPlusb];
  48. 	ret %= mod;
  49. 	return ret;
  50. }
  51.  
  52. struct dpValue
  53. {
  54. 	long long x[MAXN];
  55. 	dpValue()
  56. 	{
  57. 		memset(x, 0, sizeof(x));
  58. 	}
  59. };
  60.  
  61. dpValue combine(dpValue A, dpValue B)
  62. {
  63. 	int maxNonZeroA = 0;
  64. 	int maxNonZeroB = 0;
  65. 	for(int i = 0; i < MAXN; i++)
  66. 	{
  67. 		if(A.x[i] != 0)
  68. 			maxNonZeroA = i;
  69. 		if(B.x[i] != 0)
  70. 			maxNonZeroB = i;
  71. 	}
  72. 	dpValue ret;
  73. 	for(int i = 0; i <= maxNonZeroA; i++)
  74. 		for(int j = 0; j <= maxNonZeroB && i+j < MAXN; j++)
  75. 		{
  76. 			ret.x[i+j] += ((A.x[i] * B.x[j]) % mod) * C(i+j, i);
  77. 			ret.x[i+j] %= mod;
  78. 		}
  79. 	return ret;
  80. }
  81.  
  82. vector <int> nodeList;
  83.  
  84. vector <int> e[MAXN];
  85. int cntNodes[MAXN];
  86.  
  87. dpValue dp[MAXN];
  88.  
  89. void dfsForSon(int cur, int from)
  90. {
  91. 	nodeList.push_back(cur);
  92. 	cntNodes[cur] = 1;
  93. 	for(int i = 0; i < e[cur].size(); i++)
  94. 	{
  95. 		int t = e[cur][i];
  96. 		if(t == from) continue;
  97. 		dfsForSon(t, cur);
  98. 		cntNodes[cur] += cntNodes[t];
  99. 	}
  100. }
  101.  
  102. void prepare()
  103. {
  104. 	factorial[0] = 1;
  105. 	for(int i = 1; i < MAXN; i++)
  106. 		factorial[i] = (factorial[i-1] * i) % mod;
  107. 	for(int i = 0; i < MAXN; i++)
  108. 		invFactorial[i] = inv(factorial[i]);
  109. }
  110.  
  111. dpValue pointwiseSum(dpValue A, dpValue B)
  112. {
  113. 	dpValue ret;
  114. 	for(int i = 0; i < MAXN; i++)
  115. 		ret.x[i] = (A.x[i] + B.x[i]) % mod;
  116. 	return ret;
  117. }
  118.  
  119. dpValue dfs(int cur, int from)
  120. {
  121. 	dpValue ret;
  122. 	ret.x[0] = 1;
  123. 	for(int i = 0; i < e[cur].size(); i++)
  124. 	{
  125. 		int t = e[cur][i];
  126. 		if(t == from) continue;
  127. 		ret = combine(ret, dfs(t, cur));
  128. 	}
  129. 	for(int i = 0; i < MAXN; i++)
  130. 		if(ret.x[i] == 0)
  131. 		{
  132. 			ret.x[i] = ret.x[i-1];
  133. 			break;
  134. 		}
  135. 	return ret;
  136. }
  137.  
  138. dpValue solve(int cur, bool rooted)
  139. {
  140. 	dfsForSon(cur, -1);
  141. 	if(rooted == true)
  142. 	{
  143. 		nodeList.clear();
  144. 		return dfs(cur, -1);
  145. 	}
  146.  
  147. 	int totalNodes = cntNodes[cur];
  148.  
  149. 	dpValue sum;
  150. 	for(int i = 0; i < nodeList.size(); i++)
  151. 	{
  152. 		sum = pointwiseSum(sum, dfs(nodeList[i], -1));
  153. 	}
  154.  
  155. 	for(int i = 0; i <= totalNodes; i++)
  156. 	{
  157. 		long long v = sum.x[i];
  158. 		v *= inv(max(1, totalNodes - i));
  159. 		v %= mod;
  160. 		sum.x[i] = v;
  161. 	}
  162. 	nodeList.clear();
  163. 	return sum;
  164. }
  165.  
  166. int n, m;
  167. int eA[MAXM];
  168. int eB[MAXM];
  169. vector <int> edge[MAXN];
  170. int deg[MAXN];
  171. int q[2 * MAXM], now , z;
  172. bool inQ[MAXN];
  173. bool canReach[MAXN];
  174. bool visited[MAXN];
  175.  
  176. void parse(int cur, int from)
  177. {
  178. 	visited[cur] = true;
  179. 	for(int i = 0; i < edge[cur].size(); i++)
  180. 	{
  181. 		int t = edge[cur][i];
  182. 		if(t == from) continue;
  183. 		e[cur].push_back(t);
  184. 		e[t].push_back(cur);
  185. 		parse(t, cur);
  186. 	}
  187. }
  188.  
  189. int MAIN()
  190. {
  191. 	prepare();
  192. 	cin >> n >> m;
  193. 	memset(canReach, false, sizeof(canReach));
  194. 	memset(visited, false, sizeof(visited));
  195. 	memset(inQ, false, sizeof(inQ));
  196. 	for(int i = 1; i <= m; i++)
  197. 	{
  198. 		cin >> eA[i] >> eB[i];
  199. 		deg[eA[i]] ++;
  200. 		deg[eB[i]] ++;
  201. 		edge[eA[i]].push_back(eB[i]);
  202. 		edge[eB[i]].push_back(eA[i]);
  203. 	}
  204. 	now = 1, z = 0;
  205. 	for(int i = 1; i <= n; i++)
  206. 		if(deg[i] <= 1)
  207. 		{
  208. 			inQ[i] = true;
  209. 			q[++z] = i;
  210. 		}
  211. 	while(now <= z)
  212. 	{
  213. 		int x = q[now];
  214. 		canReach[x] = true;
  215. 		for(int i = 0; i < edge[x].size(); i++)
  216. 		{
  217. 			int t = edge[x][i];
  218. 			deg[t] --;
  219. 			if(deg[t] <= 1 && inQ[t] == false)
  220. 			{
  221. 				inQ[t] = true;
  222. 				q[++z] = t;
  223. 			}
  224. 		}
  225. 		++ now;
  226. 	}
  227.  
  228. 	dpValue finalResult;
  229. 	finalResult.x[0] = 1;
  230.  
  231. 	for(int i = 1; i <= m; i++)
  232. 	{
  233. 		if(canReach[eA[i]] != canReach[eB[i]])
  234. 		{
  235. 			if(canReach[eB[i]])
  236. 				swap(eA[i], eB[i]);
  237. 			parse(eA[i], eB[i]);
  238. 			finalResult = combine(finalResult, solve(eA[i], true));
  239. 		}
  240. 	}
  241.  
  242. 	for(int i = 1; i <= n; i++)
  243. 		if(visited[i] == false && canReach[i] == true)
  244. 		{
  245. 			parse(i, -1);
  246. 			finalResult = combine(finalResult, solve(i, false));
  247. 		}
  248.  
  249. 	for(int i = 0; i <= n; i++)
  250. 	{
  251. 		long long v = finalResult.x[i];
  252. 		cout << v << endl;
  253. 	}
  254. 	return 0;
  255. }
  256.  
  257. int main()
  258. {
  259. 	#ifdef LOCAL_TEST
  260. 		freopen("in.txt", "r", stdin);
  261. 		freopen("out.txt", "w", stdout);
  262. 	#endif
  263. 	ios :: sync_with_stdio(false);
  264. 	cout << fixed << setprecision(16);
  265. 	return MAIN();
  266. }
Success #stdin #stdout 0s 18952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/zHeV5h
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!