fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. const int MOD = int(1e9)+7;
  4. int mod_plus(int a, int b) {
  5. 	a += b;
  6. 	return a >= MOD ? a - MOD : a;
  7. }
  8. int mod_minus(int a, int b) {
  9. 	a -= b;
  10. 	return a < 0 ? a + MOD : a;
  11. }
  12. int mod_mul(int a, int b) {
  13. 	return int(int64_t(a) * int64_t(b) % MOD);
  14. }
  15. int mod_pow(int a, int b) {
  16. 	int r = 1;
  17. 	while (b) {
  18. 		if (b & 1) r = mod_mul(r, a);
  19. 		a = mod_mul(a, a);
  20. 		b >>= 1;
  21. 	}
  22. 	return r;
  23. }
  24.  
  25. int main() {
  26. 	using namespace std;
  27. 	ios_base::sync_with_stdio(false), cin.tie(nullptr);
  28.  
  29. 	int T; cin >> T;
  30. 	while (T--) {
  31. 		int N, M; cin >> N >> M;
  32. 		vector<vector<int>> adj(N);
  33. 		for (int e = 0; e < M; e++) {
  34. 			int u, v; cin >> u >> v; u--, v--;
  35. 			adj[u].push_back(v);
  36. 			adj[v].push_back(u);
  37. 		}
  38. 		vector<int> dist(N, -1);
  39. 		vector<int> dist2(N, -1);
  40. 		vector<int> q; q.reserve(2*N);
  41. 		dist[0] = 0;
  42. 		q.push_back(0);
  43. 		for (int z = 0; z < int(q.size()); z++) {
  44. 			int cur = q[z];
  45. 			if (cur >= 0) {
  46. 				for (int nxt : adj[cur]) {
  47. 					if (dist[nxt] == -1) {
  48. 						dist[nxt] = dist[cur]+1;
  49. 						q.push_back(nxt);
  50. 					} else if (dist[nxt] == dist[cur] && dist2[nxt] == -1) {
  51. 						dist2[nxt] = dist[cur]+1;
  52. 						q.push_back(~nxt);
  53. 					}
  54. 				}
  55. 			} else {
  56. 				cur = ~cur;
  57. 				for (int nxt : adj[cur]) {
  58. 					if (dist2[nxt] == -1) {
  59. 						dist2[nxt] = dist2[cur]+1;
  60. 						q.push_back(~nxt);
  61. 					}
  62. 				}
  63. 			}
  64. 		}
  65.  
  66. 		cout << [&]() -> int {
  67. 			if (dist2[0] == -1) {
  68. 				vector<int> dist_cnt(N);
  69. 				for (int i = 0; i < N; i++) dist_cnt[dist[i]]++;
  70. 				int ans = 1;
  71. 				for (int i = 1; i < N; i++) {
  72. 					if (!dist_cnt[i]) break;
  73. 					// luckily for us, 2^k != 0
  74. 					ans = mod_mul(ans, mod_pow(mod_pow(2, dist_cnt[i-1]) - 1, dist_cnt[i]));
  75. 				}
  76. 				return ans;
  77. 			}
  78.  
  79. 			vector<vector<int>> groups(2*N); // should be a big enough upper bound...
  80. 			for (int i = 0; i < N; i++) {
  81. 				assert(dist[i] % 2 != dist2[i] % 2);
  82. 				int group = (dist[i] + dist2[i] - 1) / 2;
  83. 				int layer = (dist2[i] - dist[i] - 1) / 2;
  84. 				groups[group].push_back(layer);
  85. 			}
  86.  
  87. 			vector<int> fact(N+1);
  88. 			fact[0] = 1;
  89. 			for (int i = 1; i <= N; i++) fact[i] = mod_mul(fact[i-1], i);
  90. 			vector<int> ifact(N+1);
  91. 			ifact[N] = mod_pow(fact[N], MOD-2);
  92. 			for (int i = N; i >= 1; i--) ifact[i-1] = mod_mul(ifact[i], i);
  93. 			auto choose = [&](int n, int r) {
  94. 				assert(0 <= r && r <= n);
  95. 				return mod_mul(fact[n], mod_mul(ifact[n-r], ifact[r]));
  96. 			};
  97.  
  98. 			vector<int> dp; dp.reserve(N+1);
  99. 			dp.push_back(1);
  100. 			vector<int> ndp; ndp.reserve(N+1);
  101.  
  102. 			// Let anyone who's covered claim to be uncovered
  103. 			auto relax_covering = [&]() {
  104. 				int tot = int(dp.size())-1;
  105. 				for (int i = tot; i >= 0; i--) {
  106. 					for (int j = i-1; j >= 0; j--) {
  107. 						dp[i] = mod_plus(dp[i], mod_mul(dp[j], choose(tot-j, i-j)));
  108. 					}
  109. 				}
  110. 			};
  111.  
  112. 			vector<int> bottom_ways(N+1);
  113. 			for (int i = 0; i <= N; i++) {
  114. 				bottom_ways[i] = mod_pow(2, i * (i+1) / 2);
  115. 				for (int j = 0; j < i; j++) {
  116. 					bottom_ways[i] = mod_minus(bottom_ways[i], mod_mul(bottom_ways[j], choose(i, j)));
  117. 				}
  118. 			}
  119.  
  120. 			vector<pair<int, int>> last_layer_count(N, {-2, -1});
  121. 			for (int g = 0; g < int(groups.size()); g++) {
  122. 				auto& layers = groups[g];
  123. 				if (layers.empty()) continue;
  124.  
  125. 				sort(layers.begin(), layers.end());
  126. 				vector<pair<int, int>> cur_cnts; cur_cnts.reserve(layers.size());
  127. 				for (int i : layers) {
  128. 					if (cur_cnts.empty() || cur_cnts.back().first != i) {
  129. 						cur_cnts.push_back({i, 0});
  130. 					}
  131. 					cur_cnts.back().second++;
  132. 				}
  133. 				reverse(cur_cnts.begin(), cur_cnts.end());
  134.  
  135. 				int last_l = N;
  136. 				dp.resize(1); // shrink down to nothing uncovered
  137. 				for (auto [l, cnt] : cur_cnts) {
  138. 					if (std::exchange(last_l, l) > l+1) {
  139. 						dp.resize(1);
  140. 					}
  141.  
  142. 					{
  143. 						relax_covering();
  144.  
  145. 						ndp.assign(cnt+1, 0);
  146. 						for (int j = 0; j < int(ndp.size()); j++) {
  147. 							int num_opts = mod_pow(2, j) - 1;
  148. 							int cur_ways = 1;
  149. 							for (int i = 0; i < int(dp.size()); i++, cur_ways = mod_mul(cur_ways, num_opts)) {
  150. 								ndp[j] = mod_plus(ndp[j], mod_mul(dp[i], cur_ways));
  151. 							}
  152. 						}
  153. 						for (int j = 0; j < int(ndp.size()); j++) {
  154. 							for (int i = 0; i < j; i++) {
  155. 								ndp[j] = mod_minus(ndp[j], mod_mul(ndp[i], choose(j, i)));
  156. 							}
  157. 						}
  158. 						for (int j = 0; j < int(ndp.size()); j++) {
  159. 							ndp[j] = mod_mul(ndp[j], choose(cnt, j));
  160. 						}
  161. 						reverse(ndp.begin(), ndp.end());
  162. 						std::swap(dp, ndp);
  163. 					}
  164.  
  165. 					if (l == g) {
  166. 						// Special case! This guy is necessarily unmatched because he's the root!
  167. 						// Just let him through
  168. 						assert(cnt == 1);
  169. 						assert(dp[0] == 0);
  170. 						dp[0] = dp[1];
  171. 						dp[1] = 0;
  172. 					}
  173.  
  174. 					int num_edges;
  175. 					if (last_layer_count[l].first == g-1) {
  176. 						num_edges = last_layer_count[l].second;
  177. 					} else {
  178. 						num_edges = 0;
  179. 					}
  180.  
  181. 					// pointwise-connected
  182. 					int num_opts = mod_pow(2, num_edges) - 1;
  183. 					relax_covering();
  184. 					for (int i = 0; i < int(dp.size()); i++) {
  185. 						dp[i] = mod_mul(dp[i], mod_pow(num_opts, i));
  186. 					}
  187. 					reverse(dp.begin(), dp.end());
  188.  
  189. 					last_layer_count[l] = {g, cnt};
  190. 				}
  191. 				if (last_l > 0) {
  192. 					dp.resize(1);
  193. 				} else {
  194. 					relax_covering();
  195. 					int res = 0;
  196. 					for (int j = 0; j < int(dp.size()); j++) {
  197. 						res = mod_plus(res, mod_mul(dp[j], bottom_ways[j]));
  198. 					}
  199. 					dp.resize(1);
  200. 					dp[0] = res;
  201. 				}
  202. 			}
  203.  
  204. 			return dp[0];
  205. 		}() << '\n';
  206. 	}
  207.  
  208. 	return 0;
  209. }
  210.  
  211.  
  212. // The graph is undirected, so if f_G(a,b) then f_G(a, b+2), because we can go back and forth along any edge
  213. // This means, that f_G encodes the shortest paths and the shortest paths of opposite parity.
  214. //
  215. // We can consider the edges partitioned by distance (bfs tree/dag):
  216. //   There are edges between levels, and edges within levels (including self loops)
  217. //  * A path for dist2 never needs to take >= 2 in-level edge, because then we
  218. //     could've taken the shortest path to the dest of the 2nd in-level-edge
  219. //  * Therefore, dist2 is just the shortest path to an in-level edge's endpoint
  220. //  * dist2[v] == dist[v]+1 if v has at least 1 in-level edge
  221. //  Now, cross-level edges are more interesting:
  222. //   * Each vertex must have at least 1 upwards cross-level edge (which just be to dist2[v]+-1)
  223. //   * Each vertex must either have dist2[v] == dist[v]+1 and have an in-level edge, or must have at least 1 cross-level edge to dist2[v]-1
  224. //
  225. //  Any candidate edge either satisfies both requirements for a single vertex,
  226. //    or satisfies 1 from each (which only happens if dist[u]+dist2[u] == dist[v]+dist2[v] is the same)
  227. //    or is an in-level edge (and dist[u]+1 == dist2[u])
  228. //  This means we can treat every equivalence class of dist[u]+dist2[u] almost totally separately.
  229. //  We want to find the number of edge covers of each group.
  230.  
Success #stdin #stdout 0s 4956KB
comments (?)
stdin
copy 
7

4 6
1 2
2 3
3 4
1 3
2 4
1 4

5 5
1 2
2 3
3 4
4 5
1 5

5 7
1 2
1 3
1 5
2 4
3 3
3 4
4 5

6 6
1 2
2 3
3 4
4 5
5 6
6 6

6 7
1 2
2 3
1 3
1 4
4 5
5 6
1 6

10 10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

22 28
1 2
2 3
3 4
4 5
5 6
6 7
1 7
1 8
3 9
8 10
10 11
10 12
10 13
10 14
11 15
12 16
13 17
14 18
9 15
9 16
9 17
9 18
15 19
19 20
15 20
16 21
21 22
16 22
stdout
copy 
45
35
11
1
15
371842544
256838540
https://ideone.com/qaYE9T
language:
C++14 (gcc 8.3)
created:
3 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!