fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using uint = unsigned int;
  5. template<uint _mod>
  6. struct modular_fixed_base{
  7. 	static constexpr uint mod(){
  8. 		return _mod;
  9. 	}
  10. 	template<class T>
  11. 	static vector<modular_fixed_base> precalc_power(T base, int SZ){
  12. 		vector<modular_fixed_base> res(SZ + 1, 1);
  13. 		for(auto i = 1; i <= SZ; ++ i) res[i] = res[i - 1] * base;
  14. 		return res;
  15. 	}
  16. 	static vector<modular_fixed_base> _INV;
  17. 	static void precalc_inverse(int SZ){
  18. 		if(_INV.empty()) _INV.assign(2, 1);
  19. 		for(auto x = _INV.size(); x <= SZ; ++ x) _INV.push_back(_mod / x * -_INV[_mod % x]);
  20. 	}
  21. 	// _mod must be a prime
  22. 	static modular_fixed_base _primitive_root;
  23. 	static modular_fixed_base primitive_root(){
  24. 		if(_primitive_root) return _primitive_root;
  25. 		if(_mod == 2) return _primitive_root = 1;
  26. 		if(_mod == 998244353) return _primitive_root = 3;
  27. 		uint divs[20] = {};
  28. 		divs[0] = 2;
  29. 		int cnt = 1;
  30. 		uint x = (_mod - 1) / 2;
  31. 		while(x % 2 == 0) x /= 2;
  32. 		for(auto i = 3; 1LL * i * i <= x; i += 2){
  33. 			if(x % i == 0){
  34. 				divs[cnt ++] = i;
  35. 				while(x % i == 0) x /= i;
  36. 			}
  37. 		}
  38. 		if(x > 1) divs[cnt ++] = x;
  39. 		for(auto g = 2; ; ++ g){
  40. 			bool ok = true;
  41. 			for(auto i = 0; i < cnt; ++ i){
  42. 				if((modular_fixed_base(g).power((_mod - 1) / divs[i])) == 1){
  43. 					ok = false;
  44. 					break;
  45. 				}
  46. 			}
  47. 			if(ok) return _primitive_root = g;
  48. 		}
  49. 	}
  50. 	constexpr modular_fixed_base(): data(){ }
  51. 	modular_fixed_base(const double &x){ data = normalize(llround(x)); }
  52. 	modular_fixed_base(const long double &x){ data = normalize(llround(x)); }
  53. 	template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base(const T &x){ data = normalize(x); }
  54. 	template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> static uint normalize(const T &x){
  55. 		int sign = x >= 0 ? 1 : -1;
  56. 		uint v =  _mod <= sign * x ? sign * x % _mod : sign * x;
  57. 		if(sign == -1 && v) v = _mod - v;
  58. 		return v;
  59. 	}
  60. 	const uint &operator()() const{ return data; }
  61. 	template<class T> operator T() const{ return data; }
  62. 	modular_fixed_base &operator+=(const modular_fixed_base &otr){ if((data += otr.data) >= _mod) data -= _mod; return *this; }
  63. 	modular_fixed_base &operator-=(const modular_fixed_base &otr){ if((data += _mod - otr.data) >= _mod) data -= _mod; return *this; }
  64. 	template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base &operator+=(const T &otr){ return *this += modular_fixed_base(otr); }
  65. 	template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base &operator-=(const T &otr){ return *this -= modular_fixed_base(otr); }
  66. 	modular_fixed_base &operator++(){ return *this += 1; }
  67. 	modular_fixed_base &operator--(){ return *this += _mod - 1; }
  68. 	modular_fixed_base operator++(int){ modular_fixed_base result(*this); *this += 1; return result; }
  69. 	modular_fixed_base operator--(int){ modular_fixed_base result(*this); *this += _mod - 1; return result; }
  70. 	modular_fixed_base operator-() const{ return modular_fixed_base(_mod - data); }
  71. 	modular_fixed_base &operator*=(const modular_fixed_base &rhs){
  72. 		data = (unsigned long long)data * rhs.data % _mod;
  73. 		return *this;
  74. 	}
  75. 	template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr>
  76. 	modular_fixed_base &inplace_power(T e){
  77. 		if(e < 0) *this = 1 / *this, e = -e;
  78. 		modular_fixed_base res = 1;
  79. 		for(; e; *this *= *this, e >>= 1) if(e & 1) res *= *this;
  80. 		return *this = res;
  81. 	}
  82. 	template<class T, typename enable_if<is_integral<T>::value>::type* = nullptr>
  83. 	modular_fixed_base power(T e) const{
  84. 		return modular_fixed_base(*this).inplace_power(e);
  85. 	}
  86. 	modular_fixed_base &operator/=(const modular_fixed_base &otr){
  87. 		int a = otr.data, m = _mod, u = 0, v = 1;
  88. 		if(a < _INV.size()) return *this *= _INV[a];
  89. 		while(a){
  90. 			int t = m / a;
  91. 			m -= t * a; swap(a, m);
  92. 			u -= t * v; swap(u, v);
  93. 		}
  94. 		assert(m == 1);
  95. 		return *this *= u;
  96. 	}
  97. 	uint data;
  98. };
  99. template<uint _mod> vector<modular_fixed_base<_mod>> modular_fixed_base<_mod>::_INV;
  100. template<uint _mod> modular_fixed_base<_mod> modular_fixed_base<_mod>::_primitive_root;
  101. template<uint _mod> bool operator==(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data == rhs.data; }
  102. template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator==(const modular_fixed_base<_mod> &lhs, T rhs){ return lhs == modular_fixed_base<_mod>(rhs); }
  103. template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator==(T lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) == rhs; }
  104. template<uint _mod> bool operator!=(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return !(lhs == rhs); }
  105. template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator!=(const modular_fixed_base<_mod> &lhs, T rhs){ return !(lhs == rhs); }
  106. template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> bool operator!=(T lhs, const modular_fixed_base<_mod> &rhs){ return !(lhs == rhs); }
  107. template<uint _mod> bool operator<(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data < rhs.data; }
  108. template<uint _mod> bool operator>(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data > rhs.data; }
  109. template<uint _mod> bool operator<=(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data <= rhs.data; }
  110. template<uint _mod> bool operator>=(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return lhs.data >= rhs.data; }
  111. template<uint _mod> modular_fixed_base<_mod> operator+(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) += rhs; }
  112. template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator+(const modular_fixed_base<_mod> &lhs, T rhs){ return modular_fixed_base<_mod>(lhs) += rhs; }
  113. template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator+(T lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) += rhs; }
  114. template<uint _mod> modular_fixed_base<_mod> operator-(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) -= rhs; }
  115. template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator-(const modular_fixed_base<_mod> &lhs, T rhs){ return modular_fixed_base<_mod>(lhs) -= rhs; }
  116. template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator-(T lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) -= rhs; }
  117. template<uint _mod> modular_fixed_base<_mod> operator*(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) *= rhs; }
  118. template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator*(const modular_fixed_base<_mod> &lhs, T rhs){ return modular_fixed_base<_mod>(lhs) *= rhs; }
  119. template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator*(T lhs, const modular_fixed_base<_mod> &rhs){ return modular_fixed_base<_mod>(lhs) *= rhs; }
  120. template<uint _mod> modular_fixed_base<_mod> operator/(const modular_fixed_base<_mod> &lhs, const modular_fixed_base<_mod> &rhs) { return modular_fixed_base<_mod>(lhs) /= rhs; }
  121. template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator/(const modular_fixed_base<_mod> &lhs, T rhs) { return modular_fixed_base<_mod>(lhs) /= rhs; }
  122. template<uint _mod, class T, typename enable_if<is_integral<T>::value>::type* = nullptr> modular_fixed_base<_mod> operator/(T lhs, const modular_fixed_base<_mod> &rhs) { return modular_fixed_base<_mod>(lhs) /= rhs; }
  123. template<uint _mod> istream &operator>>(istream &in, modular_fixed_base<_mod> &number){
  124. 	long long x;
  125. 	in >> x;
  126. 	number.data = modular_fixed_base<_mod>::normalize(x);
  127. 	return in;
  128. }
  129. // #define _PRINT_AS_FRACTION
  130. template<uint _mod> ostream &operator<<(ostream &out, const modular_fixed_base<_mod> &number){
  131. #ifdef LOCAL
  132. #ifdef _PRINT_AS_FRACTION
  133. 	out << number();
  134. 	cerr << "(";
  135. 	for(auto d = 1; ; ++ d){
  136. 		if((number * d).data <= 1000000){
  137. 			cerr << (number * d).data << "/" << d;
  138. 			break;
  139. 		}
  140. 		else if((-number * d).data <= 1000000){
  141. 			cerr << "-" << (-number * d).data << "/" << d;
  142. 			break;
  143. 		}
  144. 	}
  145. 	cerr << ")";
  146. 	return out;
  147. #else
  148. 	return out << number();
  149. #endif
  150. #else
  151. 	return out << number();
  152. #endif
  153. }
  154. #undef _PRINT_AS_FRACTION
  155.  
  156. const uint mod = 1e9 + 7; // 1000000007
  157. // const uint mod = (119 << 23) + 1; // 998244353
  158. // const uint mod = 1e9 + 9; // 1000000009
  159. using modular = modular_fixed_base<mod>;
  160.  
  161. const int N = 10, M = 200 + 5, D = 60 + 1;
  162.  
  163. int n; long long m;
  164. int a[N];
  165.  
  166. modular dp[D][M];
  167.  
  168. signed main(){
  169. 	ios_base::sync_with_stdio(0);
  170. 	cin.tie(0); cout.tie(0);
  171. 	cin >> n >> m;
  172. 	for (int i = 0; i < n; i++){
  173. 		cin >> a[i];
  174. 	}
  175.  
  176. 	dp[D - 1][0] = modular(1);
  177. 	for (int l = D - 2; l >= 0; l--){
  178. 		for (int msk = 0; msk < (1 << n); msk++){
  179. 			int sum = 0;
  180. 			for (int i = 0; i < n; i++){
  181. 				if (msk >> i & 1){
  182. 					sum += a[i];
  183. 				}
  184. 			}
  185. 			for (int j = 0; j < M; j++){
  186. 				int tj = j * 2 + (m >> l & 1) - sum;
  187. 				if (0 <= tj and tj < M){
  188. 					dp[l][tj] += dp[l + 1][j];
  189. 				}
  190. 			}
  191. 		}
  192. 	}
  193. 	auto ans = dp[0][0];
  194. 	cout << ans << "\n";
  195. }
  196.  
Success #stdin #stdout 0.01s 5444KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/2PGorO
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 years ago
visibility:
secret

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!