fork download
  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
stdin
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
Standard output is empty