fork download
copy 
  1. #line 5 "CandyDrawing.cpp"
  2. #include <iostream>
  3. #include <sstream>
  4. #include <set>
  5. #include <map>
  6. #include <bitset>
  7. #include <algorithm>
  8. #include <utility>
  9. #include <numeric>
  10. #include <functional>
  11. #include <vector>
  12. #include <queue>
  13. #include <stack>
  14. #include <string>
  15. #include <cstdlib>
  16. #include <cstdio>
  17. #include <cstring>
  18. #include <ctime>
  19. #include <cmath>
  20. #include <cassert>
  21. #include <climits>
  22.  
  23. #define forn(i, n) for (int i = 0; i < int(n); i++)
  24. #define forl(i, n) for (int i = 1; i <= int(n); i++)
  25. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  26. #define fore(i, l, r) for (int i = int(l); i <= int(r); i++)
  27. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  28. #define all(a) (a).begin(), (a).end()
  29. #define sz(a) int((a).size())
  30. #define pb(a) push_back(a)
  31. #define mp(x, y) make_pair((x), (y))
  32. #define ft first
  33. #define sc second
  34. #define x first
  35. #define y 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 CandyDrawing
  53. {
  54. 	public:
  55. 	int findProbability(int N, int K, int MOD);
  56. };
  57.  
  58. li gcd(li a, li b, li& x, li& y)
  59. {
  60. 	if (a == 0)
  61. 	{
  62. 		x = 0, y = 1;
  63. 		return b;
  64. 	}
  65.  
  66. 	li xx, yy, g = gcd(b % a, a, xx, yy);
  67. 	x = yy - b / a * xx;
  68. 	y = xx;
  69. 	return g;
  70. }
  71.  
  72. li inv(li a, li mod)
  73. {
  74. 	li x, y;
  75. 	assert(gcd(a, mod, x, y) == 1);
  76. 	return (x % mod + mod) % mod;
  77. }
  78.  
  79. int mod;
  80. li bmod;
  81.  
  82. inline int add(int a, int b) { return int((a + 0ll + b) % mod); }
  83. inline int sub(int a, int b) { return add(a, mod - b); }
  84. inline int mul(int a, int b) { return int((a * 1ll * b) % mod); }
  85.  
  86. const int MAXK = 2000 + 3, LOGN = 32;
  87.  
  88. int z[2][MAXK];
  89. int p[2][MAXK];
  90. int C[MAXK];
  91. int invc[MAXK];
  92. int cc[MAXK];
  93. int cc1[MAXK];
  94. int cc2[MAXK];
  95.  
  96. inline li smul(li a, li b)
  97. {
  98. 	li q = li(ld(a) * b / bmod);
  99. 	li ans = (a * b - q * bmod) % bmod;
  100. 	return ans < 0 ? ans + bmod : ans;
  101. }
  102.  
  103. int CandyDrawing::findProbability(int N, int K, int MOD)
  104. {
  105. 	mod = MOD;
  106. 	bmod = MOD * 2300000000ll;
  107.  
  108. 	vector<int> nn;
  109. 	{
  110.     	int n = N;
  111.     	while (n) nn.pb(n), n >>= 1;
  112.     	reverse(all(nn));
  113. 	}
  114.  
  115. 	forl(i, MAXK - 1) invc[i] = int(inv(i, mod));
  116.  
  117. 	memset(z, 0, sizeof(z));
  118. 	memset(p, 0, sizeof(p));
  119.  
  120. 	z[0][0] = 1;
  121. 	z[0][1] = 1;
  122. 	forl(ii, sz(nn) - 1)
  123. 	{
  124. 		int cur = ii & 1;
  125. 		int prev = cur ^ 1;
  126.  
  127. 		int n = nn[ii];
  128. 		int n2 = n / 2;
  129.  
  130. 		forn(i, K + 1) cc[i] = mul(invc[i], n + 1);
  131. 		forn(i, K + 1) cc1[i] = mul(n2 - i + 1, cc[i]);
  132. 		forn(i, K + 1) cc2[i] = mul(i, cc[i]);
  133.  
  134. 		forn(k, K + 1)
  135. 		{
  136. 			if (k > n2) continue;
  137.  
  138. 			if (k > 0)
  139. 				forn(i, k + 1)
  140. 				{
  141. 					cc1[i] -= cc[i];
  142. 					(cc1[i] < 0) && (cc1[i] += mod);
  143. 				}
  144.  
  145. 			li dv = 0;
  146. 			int q = 1;
  147. 			ford(i, k + 1)
  148. 			{
  149. 				if (i < k)
  150. 				{
  151. 					int c = cc1[k - i] - mod + cc2[k - i];
  152. 					(c < 0) && (c += mod);
  153. 					q = mul(q, c);
  154. 				}
  155.  
  156. 				if (i & 1)
  157. 				{
  158. 					dv += bmod - q * 1ll * z[prev][i];
  159. 					(dv >= bmod) && (dv -= bmod);
  160. 				}
  161. 				else
  162. 				{
  163. 					dv += q * 1ll * z[prev][i];
  164. 					(dv >= bmod) && (dv -= bmod);
  165. 				}
  166. 			}
  167. 			p[cur][k] = int(dv % mod);
  168. 		}
  169.  
  170. 		li pp = 0;
  171. 		forn(k, K + 1)
  172. 		{
  173. 			if (k > n) continue;
  174.  
  175. 			li dv = 0;
  176.  
  177. 			forn(i, k + 1)
  178. 			{
  179. 				dv += z[prev][i] * 1ll * p[cur][k - i];
  180. 				(dv >= bmod) && (dv -= bmod);
  181. 			}
  182.  
  183. 			li odv = dv;
  184. 			if (n & 1) dv = (dv + pp % mod * ((n + 1) / 2)) % mod;
  185. 			pp = odv;
  186.  
  187. 			z[cur][k] = int(dv % mod);
  188. 		}
  189. 	}
  190.  
  191. 	return z[(sz(nn) - 1) & 1][K];
  192. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/i486-linux-gnu/4.8/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/gw5gNX
language:
C++ (gcc 8.3)
created:
9 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!