fork download
copy 
  1. #ifndef LOCAL
  2. #define NDEBUG
  3. #endif
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. namespace iefnah {
  9.  
  10. template <int MOD_> struct modnum {
  11. 	static constexpr int MOD = MOD_;
  12. 	static_assert(MOD_ > 0, "MOD must be positive");
  13.  
  14. private:
  15. 	using ll = long long;
  16.  
  17. 	int v;
  18.  
  19. 	static int minv(int a, int m) {
  20. 		a %= m;
  21. 		assert(a);
  22. 		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
  23. 	}
  24.  
  25. public:
  26.  
  27. 	modnum() : v(0) {}
  28. 	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
  29. 	explicit operator int() const { return v; }
  30. 	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
  31. 	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
  32.  
  33. 	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  34. 	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
  35.  
  36. 	modnum inv() const {
  37. 		modnum res;
  38. 		res.v = minv(v, MOD);
  39. 		return res;
  40. 	}
  41. 	friend modnum inv(const modnum& m) { return m.inv(); }
  42. 	modnum neg() const {
  43. 		modnum res;
  44. 		res.v = v ? MOD-v : 0;
  45. 		return res;
  46. 	}
  47. 	friend modnum neg(const modnum& m) { return m.neg(); }
  48.  
  49. 	modnum operator- () const {
  50. 		return neg();
  51. 	}
  52. 	modnum operator+ () const {
  53. 		return modnum(*this);
  54. 	}
  55.  
  56. 	modnum& operator ++ () {
  57. 		v ++;
  58. 		if (v == MOD) v = 0;
  59. 		return *this;
  60. 	}
  61. 	modnum& operator -- () {
  62. 		if (v == 0) v = MOD;
  63. 		v --;
  64. 		return *this;
  65. 	}
  66. 	modnum& operator += (const modnum& o) {
  67. 		v += o.v;
  68. 		if (v >= MOD) v -= MOD;
  69. 		return *this;
  70. 	}
  71. 	modnum& operator -= (const modnum& o) {
  72. 		v -= o.v;
  73. 		if (v < 0) v += MOD;
  74. 		return *this;
  75. 	}
  76. 	modnum& operator *= (const modnum& o) {
  77. 		v = int(ll(v) * ll(o.v) % MOD);
  78. 		return *this;
  79. 	}
  80. 	modnum& operator /= (const modnum& o) {
  81. 		return *this *= o.inv();
  82. 	}
  83.  
  84. 	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
  85. 	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
  86. 	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  87. 	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  88. 	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  89. 	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
  90. };
  91.  
  92. template <typename T> T pow(T a, long long b) {
  93. 	assert(b >= 0);
  94. 	T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
  95. }
  96.  
  97. using num = modnum<int(1e9)+7>;
  98.  
  99. class RestrictedLeaves {
  100.  
  101. public:
  102.  
  103. 	int count(vector<int> parent) {
  104. 		int N = int(parent.size());
  105. 		vector<vector<int>> adj(N);
  106. 		for (int i = 1; i < N; i++) {
  107. 			assert(parent[i] < i);
  108. 			adj[parent[i]].push_back(i);
  109. 		}
  110.  
  111. 		vector<array<num, 8>> dp(N); // left/right/self
  112. 		for (int cur = N-1; cur >= 0; cur--) {
  113. 			dp[cur].fill(0);
  114. 			if (adj[cur].empty()) {
  115. 				dp[cur][0] = dp[cur][7] = 1;
  116. 				continue;
  117. 			}
  118.  
  119. 			sort(adj[cur].begin(), adj[cur].end());
  120. 			for (int m = 0; m < 8; m++) {
  121. 				bool isFirst = true;
  122. 				array<num, 2> tmp = {1, 0};
  123.  
  124. 				for (int nxt : adj[cur]) {
  125. 					array<num, 2> ntmp = {};
  126. 					for (int t = 0; t < 8; t++) {
  127. 						if ((m & 4) && (t & 4)) continue;
  128. 						if (isFirst && (m & 1) != (t & 1)) continue;
  129. 						for (int a = 0; a < 2; a++) {
  130. 							if (a && (t & 1)) continue;
  131. 							ntmp[bool(t & 2)] += tmp[a] * dp[nxt][t];
  132. 						}
  133. 					}
  134. 					tmp = std::move(ntmp);
  135.  
  136. 					isFirst = false;
  137. 				}
  138.  
  139. 				dp[cur][m] = tmp[bool(m & 2)];
  140. 			}
  141. 		}
  142.  
  143. 		num ans = 0;
  144. 		for (int m = 0; m < 8; m++) {
  145. 			if (bool(m & 1) && bool(m & 2)) continue;
  146. 			ans += dp[0][m];
  147. 		}
  148. 		return int(ans);
  149. 	}
  150. };
  151.  
  152. }  // namespace iefnah
  153.  
  154. using iefnah::RestrictedLeaves;
  155.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/cxVisK
language:
C++14 (gcc 8.3)
created:
5 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!