fork download
copy 
  1. #include <string>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6. class RecursiveTournament {
  7. private:
  8. 	int binpow(int a, int b, int mod) {
  9. 		int res = 1;
  10. 		while (b > 0) {
  11. 			if (b & 1) res = 1LL * res * a % mod;
  12. 			a = 1LL * a * a % mod;
  13. 			b >>= 1;
  14. 		}
  15. 		return res;
  16. 	}
  17. public:
  18. 	int count(vector<string> G, int K) {
  19. 		int N = G.size();
  20. 		vector<int> out(N);
  21. 		for (int i = 0; i < N; ++i) {
  22. 			for (int j = 0; j < N; ++j) {
  23. 				if (G[i][j] == 'Y') {
  24. 					out[i] |= 1 << j;
  25. 				}
  26. 			}
  27. 		}
  28. 		vector<int> dp(1 << N, (1 << N) - 1), pop(1 << N);
  29. 		for (int i = 0; i < N; ++i) {
  30. 			for (int j = 1 << i; j < 2 << i; ++j) {
  31. 				dp[j] &= dp[j - (1 << i)] & out[i];
  32. 				pop[j] = pop[j - (1 << i)] + 1;
  33. 			}
  34. 		}
  35. 		vector<int> f(1 << N);
  36. 		for (int i = 1; i < 1 << N; ++i) {
  37. 			if (dp[i] != 0) {
  38. 				++f[i | dp[i]];
  39. 				--f[i];
  40. 				--f[dp[i]];
  41. 			}
  42. 		}
  43. 		for (int i = 0; i < N; ++i) {
  44. 			for (int j = 0; j < 1 << N; ++j) {
  45. 				if ((j >> i) & 1) {
  46. 					f[j - (1 << i)] += f[j];
  47. 				}
  48. 			}
  49. 		}
  50. 		vector<int> tbl(N + 1);
  51. 		for (int i = 1; i < 1 << N; ++i) {
  52. 			if (f[i] == 0) {
  53. 				++tbl[pop[i]];
  54. 			}
  55. 		}
  56. 		const int mod = 998244353; // assuming mod is prime and mod > N
  57. 		int ans = 0;
  58. 		for (int i = 1; i <= N; ++i) {
  59. 			for (int j = 0; j < (i == 1 ? 1 : K); ++j) {
  60. 				int part1 = binpow(2, binpow(N, j, mod - 1), mod) - 1;
  61. 				int part2 = binpow(part1, i, mod);
  62. 				int part3 = binpow(N, K - j - 1, mod);
  63. 				int part4 = 1LL * part2 * part3 % mod;
  64. 				ans = (ans + 1LL * part4 * tbl[i]) % mod;
  65. 			}
  66. 		}
  67. 		return ans;
  68. 	}
  69. };
  70. int main() {
  71. 	RecursiveTournament solver;
  72. 	int ans = solver.count({ "NYN", "NNY", "YNN" }, 2);
  73. 	cout << ans << endl;
  74. 	return 0;
  75. }
Success #stdin #stdout 0s 4364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
355
https://ideone.com/2tE7in
language:
C++14 (gcc 8.3)
created:
4 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!