fork download
copy 
  1. // BEGIN CUT HERE
  2.  
  3. // END CUT HERE
  4. #line 5 "AquaparkPuzzle.cpp"
  5. #include <iostream>
  6. #include <sstream>
  7. #include <set>
  8. #include <map>
  9. #include <bitset>
  10. #include <algorithm>
  11. #include <utility>
  12. #include <numeric>
  13. #include <functional>
  14. #include <vector>
  15. #include <queue>
  16. #include <stack>
  17. #include <string>
  18. #include <cstdlib>
  19. #include <cstdio>
  20. #include <cstring>
  21. #include <ctime>
  22. #include <cmath>
  23. #include <cassert>
  24.  
  25. #define forn(i, n) for (int i = 0; i < int(n); i++)
  26. #define forl(i, n) for (int i = 1; i <= int(n); i++)
  27. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  28. #define fore(i, l, r) for (int i = int(l); i <= int(r); i++)
  29. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  30. #define all(a) (a).begin(), (a).end()
  31. #define sz(a) int((a).size())
  32. #define pb(a) push_back(a)
  33. #define mp(x, y) make_pair((x), (y))
  34. #define ft first
  35. #define sc second
  36. #define isnan(a) false
  37. #define isinf(a) false
  38.  
  39. using namespace std;
  40.  
  41. typedef long long li;
  42. typedef long double ld;
  43. typedef pair<int, int> pt;
  44.  
  45. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  46. template<typename X> inline X sqr(const X& a) { return a * a; }
  47.  
  48. const int INF = int(1e9);
  49. const li INF64 = li(1e18);
  50. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  51.  
  52. class AquaparkPuzzle
  53. {
  54. 	public:
  55. 	int countSchedules(int k, int m, vector <int> c);
  56. };
  57.  
  58. int gcd(int a, int b, int& x, int& y)
  59. {
  60. 	if (a == 0)
  61. 	{
  62. 		x = 0, y = 1;
  63. 		return b;
  64. 	}
  65.  
  66. 	int xx, yy, g = gcd(b % a, a, xx, yy);
  67. 	x = yy - b / a * xx;
  68. 	y = xx;
  69. 	return g;
  70. }
  71.  
  72. const int mod = 1000 * 1000 * 1000 + 7;
  73.  
  74. int inv(int a)
  75. {
  76. 	int x, y;
  77. 	assert(gcd(a, mod, x, y) == 1);
  78. 	x %= mod;
  79. 	(x < 0) && (x += mod);
  80. 	return x;
  81. }
  82.  
  83. const int N = 11 + 3, K = 1000 * 1000 + 3, EXPN = (1 << 11) + 3, EXPN3 = 180000;
  84.  
  85. int pw[N], fact[K], ifact[K];
  86. int g[EXPN], c[EXPN];
  87.  
  88. int get(int mask, int i) { return (mask / pw[i]) % 3; }
  89. int _set(int mask, int i, int v) { return mask - (get(mask, i) - v) * pw[i]; }
  90.  
  91. int C(int n, int k)
  92. {
  93. 	if (k < 0 || k > n) return 0;
  94. 	int ans = int((fact[n] * 1ll * ifact[k]) % mod);
  95. 	ans = int((ans * 1ll * ifact[n - k]) % mod);
  96. 	return ans;
  97. }
  98.  
  99. int binPow(int a, int b)
  100. {
  101. 	int ans = 1;
  102. 	while (b)
  103. 	{
  104. 		if (b & 1) ans = int((ans * 1ll * a) % mod);
  105. 		a = int((a * 1ll * a) % mod);
  106. 		b >>= 1;
  107. 	}
  108. 	return ans;
  109. }
  110.  
  111. int n;
  112.  
  113. string get(int mask)
  114. {
  115. 	string s;
  116. 	ford(i, n) s.pb(char('0' + get(mask, i)));
  117. 	return s;
  118. }
  119.  
  120. int b[N];
  121. int z[EXPN3][N];
  122.  
  123. int AquaparkPuzzle::countSchedules(int k, int m, vector <int> cost)
  124. {
  125. 	pw[0] = 1; forl(i, N - 1) pw[i] = pw[i - 1] * 3;
  126.  
  127. 	fact[0] = 1; forl(i, K - 1) fact[i] = int((fact[i - 1] * 1ll * i) % mod);
  128. 	forn(i, K) ifact[i] = inv(fact[i]);
  129.  
  130. 	n = sz(cost);
  131. 	forn(mask, (1 << n))
  132. 	{
  133. 		int s = 0;
  134. 		forn(i, n) if (mask & (1 << i)) s += cost[i];
  135. 		g[mask] = s <= m;
  136. 	}
  137.  
  138. 	forn(mask, (1 << n))
  139. 	{
  140. 		c[mask] = 0;
  141. 		forn(msk, (1 << n)) if (!(mask & msk)) c[mask] += g[msk];
  142. 	}
  143.  
  144. 	memset(z, 0, sizeof(z)); 
  145. 	forn(mask, pw[n])
  146. 	{
  147. 		forn(i, n) b[i] = get(mask, i);
  148. 		int bmsk[3] = { 0 };
  149. 		forn(i, n) bmsk[b[i]] |= (1 << i);
  150.  
  151. 		if (bmsk[1] == 0)
  152. 		{
  153. 			z[mask][0] = 1;
  154. 			continue;
  155. 		}
  156.  
  157. 		int msk = bmsk[1] | bmsk[2];
  158. 		for (int cmsk = msk; cmsk > 0; cmsk = (cmsk - 1) & msk)
  159. 		{
  160. 			if ((cmsk & bmsk[1]) && g[cmsk])
  161. 			{
  162. 				int nmsk = mask;
  163. 				forn(i, n) if (b[i] == 1 && (cmsk & (1 << i))) nmsk -= pw[i];
  164.  
  165. 				int* p1 = &z[mask][1];
  166. 				int* p2 = &z[nmsk][0];
  167. 				forl(i, n)
  168. 				{
  169. 					*p1 += *p2;
  170. 					(*p1 >= mod) && (*p1 -= mod);
  171. 					p1++, p2++;
  172. 					/*int& dv = z[mask][i];
  173. 					dv += z[nmsk][i - 1];
  174. 					(dv >= mod) && (dv -= mod);*/
  175. 				}
  176. 			}
  177. 		}
  178. 	}
  179.  
  180. 	/*forn(mask, pw[n])
  181. 		forn(i, n + 1)
  182. 		{
  183. 			ford(j, n) cerr << get(mask, j);
  184. 			cerr << ' ' << i << ": " << z[mask][i] << endl;
  185. 		}*/
  186.  
  187. 	int ans = 0;
  188. 	forn(mask, pw[n])
  189. 	{
  190. 		forn(i, n) b[i] = get(mask, i);
  191. 		int bmsk[3] = { 0 };
  192. 		forn(i, n) bmsk[b[i]] |= (1 << i);
  193.  
  194. 		int sg = 1; forn(i, n) if (b[i] < 2) sg = -sg;
  195.  
  196. 		int sum = 0;
  197. 		forn(i, n + 1)
  198. 		{
  199. 			int cnt = C(k, i);
  200. 			if (cnt == 0) continue;
  201. 			cnt = int((cnt * 1ll * z[mask][i]) % mod);
  202. 			cnt = int((cnt * 1ll * binPow(c[bmsk[0] | bmsk[1]], k - i)) % mod);
  203. 			sum += cnt;
  204. 			(sum >= mod) && (sum -= mod);
  205. 		}
  206.  
  207. 		//cerr << get(mask) << ' ' << sum << ' ' << sg << endl;
  208. 		ans += sum * sg;
  209. 		(ans < 0) && (ans += mod);
  210. 		(ans >= mod) && (ans -= mod);
  211. 	}
  212.  
  213. 	return ans;
  214. }
  215.  
  216. // BEGIN CUT HERE
  217. namespace moj_harness {
  218. 	int run_test_case(int);
  219. 	void run_test(int casenum = -1, bool quiet = false) {
  220. 		if (casenum != -1) {
  221. 			if (run_test_case(casenum) == -1 && !quiet) {
  222. 				cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
  223. 			}
  224. 			return;
  225. 		}
  226.  
  227. 		int correct = 0, total = 0;
  228. 		for (int i=0;; ++i) {
  229. 			int x = run_test_case(i);
  230. 			if (x == -1) {
  231. 				if (i >= 100) break;
  232. 				continue;
  233. 			}
  234. 			correct += x;
  235. 			++total;
  236. 		}
  237.  
  238. 		if (total == 0) {
  239. 			cerr << "No test cases run." << endl;
  240. 		} else if (correct < total) {
  241. 			cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
  242. 		} else {
  243. 			cerr << "All " << total << " tests passed!" << endl;
  244. 		}
  245. 	}
  246.  
  247. 	int verify_case(int casenum, const int &expected, const int &received, clock_t elapsed) { 
  248. 		cerr << "Example " << casenum << "... "; 
  249.  
  250. 		string verdict;
  251. 		vector<string> info;
  252. 		char buf[100];
  253.  
  254. 		if (elapsed > CLOCKS_PER_SEC / 200) {
  255. 			sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
  256. 			info.push_back(buf);
  257. 		}
  258.  
  259. 		if (expected == received) {
  260. 			verdict = "PASSED";
  261. 		} else {
  262. 			verdict = "FAILED";
  263. 		}
  264.  
  265. 		cerr << verdict;
  266. 		if (!info.empty()) {
  267. 			cerr << " (";
  268. 			for (int i=0; i<(int)info.size(); ++i) {
  269. 				if (i > 0) cerr << ", ";
  270. 				cerr << info[i];
  271. 			}
  272. 			cerr << ")";
  273. 		}
  274. 		cerr << endl;
  275.  
  276. 		if (verdict == "FAILED") {
  277. 			cerr << "    Expected: " << expected << endl; 
  278. 			cerr << "    Received: " << received << endl; 
  279. 		}
  280.  
  281. 		return verdict == "PASSED";
  282. 	}
  283.  
  284. 	int run_test_case(int casenum) {
  285. 		switch (casenum) {
  286. 		case 0: {
  287. 			int k                     = 3;
  288. 			int m                     = 3;
  289. 			int c[]                   = {1, 2};
  290. 			int expected__            = 16;
  291.  
  292. 			clock_t start__           = clock();
  293. 			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
  294. 			return verify_case(casenum, expected__, received__, clock()-start__);
  295. 		}
  296. 		case 1: {
  297. 			int k                     = 3;
  298. 			int m                     = 3;
  299. 			int c[]                   = {2, 2};
  300. 			int expected__            = 0;
  301.  
  302. 			clock_t start__           = clock();
  303. 			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
  304. 			return verify_case(casenum, expected__, received__, clock()-start__);
  305. 		}
  306. 		case 2: {
  307. 			int k                     = 4;
  308. 			int m                     = 3;
  309. 			int c[]                   = {1, 2, 2};
  310. 			int expected__            = 66;
  311.  
  312. 			clock_t start__           = clock();
  313. 			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
  314. 			return verify_case(casenum, expected__, received__, clock()-start__);
  315. 		}
  316. 		case 3: {
  317. 			int k                     = 6;
  318. 			int m                     = 7;
  319. 			int c[]                   = {2, 3, 4, 7};
  320. 			int expected__            = 4800;
  321.  
  322. 			clock_t start__           = clock();
  323. 			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
  324. 			return verify_case(casenum, expected__, received__, clock()-start__);
  325. 		}
  326. 		case 4: {
  327. 			int k                     = 1000;
  328. 			int m                     = 20;
  329. 			int c[]                   = {8, 2, 13, 18, 7, 3};
  330. 			int expected__            = 15681195;
  331.  
  332. 			clock_t start__           = clock();
  333. 			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
  334. 			return verify_case(casenum, expected__, received__, clock()-start__);
  335. 		}
  336.  
  337. 		// custom cases
  338.  
  339.         case 5: {
  340. 			int k                     = 1000000;
  341. 			int m                     = 1000;
  342. 			int c[]                   = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
  343. 			int expected__            = 5069980;
  344.  
  345. 			clock_t start__           = clock();
  346. 			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
  347. 			return verify_case(casenum, expected__, received__, clock()-start__);
  348. 		}
  349. /*      case 6: {
  350. 			int k                     = ;
  351. 			int m                     = ;
  352. 			int c[]                   = ;
  353. 			int expected__            = ;
  354.  
  355. 			clock_t start__           = clock();
  356. 			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
  357. 			return verify_case(casenum, expected__, received__, clock()-start__);
  358. 		}*/
  359. /*      case 7: {
  360. 			int k                     = ;
  361. 			int m                     = ;
  362. 			int c[]                   = ;
  363. 			int expected__            = ;
  364.  
  365. 			clock_t start__           = clock();
  366. 			int received__            = AquaparkPuzzle().countSchedules(k, m, vector <int>(c, c + (sizeof c / sizeof c[0])));
  367. 			return verify_case(casenum, expected__, received__, clock()-start__);
  368. 		}*/
  369. 		default:
  370. 			return -1;
  371. 		}
  372. 	}
  373. }
  374.  
  375.  
  376. int main(int argc, char *argv[]) {
  377. 	if (argc == 1) {
  378. 		moj_harness::run_test();
  379. 	} else {
  380. 		for (int i=1; i<argc; ++i)
  381. 			moj_harness::run_test(atoi(argv[i]));
  382. 	}
  383. }
  384. // END CUT HERE
  385.  
Time limit exceeded #stdin #stdout #stderr 5s 20952KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Example 0... PASSED (time 0.52s)
Example 1... PASSED (time 0.50s)
Example 2... PASSED (time 0.49s)
Example 3... PASSED (time 0.50s)
Example 4... PASSED (time 0.49s)
https://ideone.com/HGequz
language:
C++ (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!