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; // (mod - 1) % MAXN == 0
  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. int cntCombine = 0;
  62.  
  63. dpValue combine(dpValue A, dpValue B)
  64. {
  65. 	int maxNonZeroA = 0;
  66. 	int maxNonZeroB = 0;
  67. 	for(int i = 0; i < MAXN; i++)
  68. 	{
  69. 		if(A.x[i] != 0)
  70. 			maxNonZeroA = i;
  71. 		if(B.x[i] != 0)
  72. 			maxNonZeroB = i;
  73. 	}
  74.  
  75. 	cntCombine ++;
  76. 	dpValue ret;
  77. 	for(int i = 0; i <= maxNonZeroA; i++)
  78. 		for(int j = 0; j <= maxNonZeroB && i+j < MAXN; j++)
  79. 		{
  80. 			ret.x[i+j] += ((A.x[i] * B.x[j]) % mod) * C(i+j, i);
  81. 			ret.x[i+j] %= mod;
  82. 		}
  83. 	return ret;
  84. }
  85.  
  86. vector <int> nodeList;
  87.  
  88. vector <int> e[MAXN];
  89. int cntNodes[MAXN];
  90.  
  91. dpValue dp[MAXN];
  92.  
  93. void dfsForSon(int cur, int from)
  94. {
  95. 	nodeList.push_back(cur);
  96. 	cntNodes[cur] = 1;
  97. 	for(int i = 0; i < e[cur].size(); i++)
  98. 	{
  99. 		int t = e[cur][i];
  100. 		if(t == from) continue;
  101. 		dfsForSon(t, cur);
  102. 		cntNodes[cur] += cntNodes[t];
  103. 	}
  104. }
  105.  
  106. void prepare()
  107. {
  108. 	factorial[0] = 1;
  109. 	for(int i = 1; i < MAXN; i++)
  110. 		factorial[i] = (factorial[i-1] * i) % mod;
  111. 	for(int i = 0; i < MAXN; i++)
  112. 		invFactorial[i] = inv(factorial[i]);
  113. }
  114.  
  115. dpValue pointwiseSum(dpValue A, dpValue B)
  116. {
  117. 	dpValue ret;
  118. 	for(int i = 0; i < MAXN; i++)
  119. 		ret.x[i] = (A.x[i] + B.x[i]) % mod;
  120. 	return ret;
  121. }
  122.  
  123. dpValue dfs(int cur, int from)
  124. {
  125. 	dpValue ret;
  126. 	ret.x[0] = 1;
  127. 	for(int i = 0; i < e[cur].size(); i++)
  128. 	{
  129. 		int t = e[cur][i];
  130. 		if(t == from) continue;
  131. 		ret = combine(ret, dfs(t, cur));
  132. 	}
  133. 	for(int i = 0; i < MAXN; i++)
  134. 		if(ret.x[i] == 0)
  135. 		{
  136. 			ret.x[i] = ret.x[i-1];
  137. 			break;
  138. 		}
  139. 	/*cout << cur << " " << from << " : ";
  140. 	for(int i = 0; i <= 2; i++)
  141. 		cout << ret.x[i] << " ";
  142. 	cout << endl;*/
  143. 	return ret;
  144. }
  145.  
  146. dpValue solve(int cur, bool rooted)
  147. {
  148. 	dfsForSon(cur, -1);
  149. 	if(rooted == true)
  150. 	{
  151. 		nodeList.clear();
  152. 		return dfs(cur, -1);
  153. 	}
  154.  
  155. 	int totalNodes = cntNodes[cur];
  156.  
  157. 	dpValue sum;
  158. 	for(int i = 0; i < nodeList.size(); i++)
  159. 	{
  160. 		sum = pointwiseSum(sum, dfs(nodeList[i], -1));
  161. 	}
  162.  
  163. 	for(int i = 0; i <= totalNodes; i++)
  164. 	{
  165. 		long long v = sum.x[i];
  166. 		v *= inv(max(1, totalNodes - i));
  167. 		v %= mod;
  168. 		sum.x[i] = v;
  169. 	}
  170. 	nodeList.clear();
  171. 	return sum;
  172. }
  173.  
  174. int n, m;
  175. int eA[MAXM];
  176. int eB[MAXM];
  177. vector <int> edge[MAXN];
  178. int deg[MAXN];
  179. int q[2 * MAXM], now , z;
  180. bool inQ[MAXN];
  181. bool canReach[MAXN];
  182. bool visited[MAXN];
  183.  
  184. void parse(int cur, int from)
  185. {
  186. 	visited[cur] = true;
  187. 	for(int i = 0; i < edge[cur].size(); i++)
  188. 	{
  189. 		int t = edge[cur][i];
  190. 		if(t == from) continue;
  191. 		e[cur].push_back(t);
  192. 		e[t].push_back(cur);
  193. 		parse(t, cur);
  194. 	}
  195. }
  196.  
  197. int MAIN()
  198. {
  199. 	prepare();
  200. 	cin >> n >> m;
  201. 	memset(canReach, false, sizeof(canReach));
  202. 	memset(visited, false, sizeof(visited));
  203. 	memset(inQ, false, sizeof(inQ));
  204. 	for(int i = 1; i <= m; i++)
  205. 	{
  206. 		cin >> eA[i] >> eB[i];
  207. 		deg[eA[i]] ++;
  208. 		deg[eB[i]] ++;
  209. 		edge[eA[i]].push_back(eB[i]);
  210. 		edge[eB[i]].push_back(eA[i]);
  211. 	}
  212. 	now = 1, z = 0;
  213. 	for(int i = 1; i <= n; i++)
  214. 		if(deg[i] <= 1)
  215. 		{
  216. 			inQ[i] = true;
  217. 			q[++z] = i;
  218. 		}
  219. 	while(now <= z)
  220. 	{
  221. 		int x = q[now];
  222. 		canReach[x] = true;
  223. 		for(int i = 0; i < edge[x].size(); i++)
  224. 		{
  225. 			int t = edge[x][i];
  226. 			deg[t] --;
  227. 			if(deg[t] <= 1 && inQ[t] == false)
  228. 			{
  229. 				inQ[t] = true;
  230. 				q[++z] = t;
  231. 			}
  232. 		}
  233. 		++ now;
  234. 	}
  235.  
  236. 	dpValue finalResult;
  237. 	finalResult.x[0] = 1;
  238.  
  239. 	for(int i = 1; i <= m; i++)
  240. 	{
  241. 		if(canReach[eA[i]] != canReach[eB[i]])
  242. 		{
  243. 			if(canReach[eB[i]])
  244. 				swap(eA[i], eB[i]);
  245. 			parse(eA[i], eB[i]);
  246. 			finalResult = combine(finalResult, solve(eA[i], true));
  247. 		}
  248. 	}
  249.  
  250. 	for(int i = 1; i <= n; i++)
  251. 		if(visited[i] == false && canReach[i] == true)
  252. 		{
  253. 			parse(i, -1);
  254. 			finalResult = combine(finalResult, solve(i, false));
  255. 		}
  256.  
  257. 	for(int i = 0; i <= n; i++)
  258. 	{
  259. 		long long v = finalResult.x[i];
  260. 		cout << v << endl;
  261. 	}
  262. 	//cout << "time = " << clock() - start << endl;
  263. 	//cout << "# " << cntCombine << endl;
  264. 	return 0;
  265. }
  266.  
  267. int main()
  268. {
  269. 	#ifdef LOCAL_TEST
  270. 		freopen("in.txt", "r", stdin);
  271. 		freopen("out.txt", "w", stdout);
  272. 	#endif
  273. 	ios :: sync_with_stdio(false);
  274. 	cout << fixed << setprecision(16);
  275. 	return MAIN();
  276. }
Success #stdin #stdout 0s 18992KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/Y7j21a
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!