Kevin_Zhang

Untitled

Mar 6th, 2021
708
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. #define pb emplace_back
  3. #define AI(i) begin(i), end(i)
  4. using namespace std;
  5. using ll = long long;
  6. template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
  7. template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
  8. #ifdef KEV
  9. #define DE(args...) kout("[ " + string(#args) + " ] = ", args)
  10. void kout() {cerr << endl;}
  11. template<class T, class ...U> void kout (T v, U ...e) { cerr << v << ' ', kout(e...); }
  12. template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L)==R], ++L; }
  13. #else
  14. #define DE(...) 0
  15. #define debug(...) 0
  16. #endif
  17. // What I should check
  18. // 1. overflow
  19. // 2. corner cases
  20. // Enjoy the problem instead of hurrying to AC
  21. // Good luck !
  22. const int MAX_N = 7510;
  23.  
  24. /*
  25. ID: ckevin31
  26. LANG: C++14
  27. TASK:
  28. */
  29. #ifndef KEV
  30. inline void IO(string name) { freopen((name +  ".in").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); }
  31. #else
  32. #define IO(...) 0
  33. #endif
  34.  
  35. int N, mod;
  36.  
  37. bool notp[MAX_N];
  38. int pri[MAX_N], pl;
  39.  
  40. struct FastMod {
  41.     ll mod;
  42.     FastMod(const ll v = 2) : mod(v) {}
  43.     ll operator()(ll v) { return v % mod; }
  44. }FM;
  45. //struct FastMod {
  46. //  uint64_t b, m;
  47. //  FastMod(uint64_t b = 1) : b(b), m(uint64_t((__uint128_t(1) << 64) / b)) {}
  48. //  uint64_t operator()(uint64_t a) {
  49. //      return a % b;
  50. //      uint64_t q = (uint64_t)((__uint128_t(m) * a) >> 64);
  51. //      uint64_t r = a - q * b; // can be proven that 0 <= r < 2*b
  52. //      return r >= b ? r - b : r;
  53. //  }
  54. //}FM;
  55. struct mint {
  56.     ll v;
  57.     mint () : v(0) {}
  58.     mint (int v) : v(v) {}
  59.     mint (ll v) : v(v) {}
  60.     mint (uint64_t v) : v(v) {}
  61. };
  62.  
  63. mint operator + (mint a, mint b) { return FM(a.v + b.v); }
  64. //mint operator + (mint a, mint b) { a.v += b.v - mod; a.v += (a.v >> 63) & mod; return a; }
  65. mint& operator += (mint &a, mint b) { return a = a + b; }
  66. mint operator - (mint a, mint b) { return FM(a.v - b.v + mod); }
  67. //mint operator - (mint a, mint b) { a.v += b.v; a.v += (a.v >> 63) & mod; return a; }
  68. mint& operator -= (mint &a, mint b) { return a = a - b; }
  69. mint operator * (mint a, mint b) { return FM(a.v * b.v); }
  70. mint& operator *= (mint &a, mint b) { return a = a * b; }
  71. bool operator == (mint a, mint b) { return a.v == b.v; }
  72. ostream& operator << (ostream& out, mint a) { return out << a.v ; }
  73.  
  74. mint bin_pow(mint v, ll t) {
  75.     mint res = 1;
  76.     for (;t;t>>=1, v *= v)
  77.         if (t&1) res *= v;
  78.     return res;
  79. }
  80. mint getinv(mint v) { return bin_pow(v, mod-2); }
  81.  
  82. mint operator / (mint a, mint b) { return a.v * getinv(b.v); }
  83.  
  84. mint fa[MAX_N], inv[MAX_N], fai[MAX_N];
  85.  
  86. void init() {
  87.     for (int i = 0;i < 2;++i)
  88.         fa[i] = inv[i] = fai[i] = 1;
  89.     for (int i = 2;i <= N;++i) {
  90.         fa[i] = fa[i-1] * i;
  91.         inv[i] = (mod - mod / i) * inv[mod % i];
  92.         fai[i] = inv[i] * fai[i-1];
  93.     }
  94. }
  95. mint C(int N, int M) { return N < M ? 0 : fa[N] * fai[M] * fai[N-M]; }
  96.  
  97. mint dp[MAX_N];
  98.  
  99. void getdp() {
  100.     dp[0] = 1;
  101.     for (int i = 1;i <= N;++i) {
  102.         for (int j = N;j >= 0;--j) {
  103.             mint dn = 1;
  104.             for (int len = i, cnt = 1; j + len <= N; len += i, ++cnt) {
  105.                 dn *= i * cnt;
  106.                 dp[j + len] +=
  107.                     dp[j] * C(j + len, len) * fa[len] / dn;
  108.             }
  109.         }
  110.     }
  111.     assert(dp[N] == fa[N]);
  112. }
  113. mint calnot(int val) {
  114.     for (int i = val;i <= N;++i) {
  115.         if (i % val) continue;
  116.         for (int j = 0;j <= N;++j) {
  117.             mint dn = 1;
  118.             for (int len = i, cnt = 1; j + len <= N; len += i, ++cnt) {
  119.                 dn *= i * cnt;
  120.                 dp[j + len] -=
  121.                     dp[j] * C(j + len, len) * fa[len] / dn;
  122.             }
  123.         }
  124.     }
  125.     mint res = dp[N];
  126.     for (int i = 1;i <= N;++i) {
  127.         if (i % val) continue;
  128.         for (int j = N;j >= 0;--j) {
  129.             mint dn = 1;
  130.             for (int len = i, cnt = 1; j + len <= N; len += i, ++cnt) {
  131.                 dn *= i * cnt;
  132.                 dp[j + len] +=
  133.                     dp[j] * C(j + len, len) * fa[len] / dn;
  134.             }
  135.         }
  136.     }
  137.     return res;
  138. }
  139. int32_t main() {
  140.     ios_base::sync_with_stdio(0), cin.tie(0);
  141.     IO("exercise");
  142.  
  143.     cin >> N >> mod;
  144.  
  145.     FM = FastMod(mod);
  146.  
  147.     init();
  148.     getdp();
  149.  
  150.     mint res = 1;
  151.  
  152.     for (int i = 2;i <= N;++i) if (!notp[i]) {
  153.         pri[pl++] = i;
  154.         for (int j = i + i;j <= N;j += i)
  155.             notp[j] = true;
  156.  
  157.         int v = i;
  158.         while (v <= N) {
  159.             mint way = calnot(v * i) - calnot(v);
  160.             assert(way.v >= 0);
  161.             DE(v, way);
  162.             res *= bin_pow(v, way.v);
  163.             v *= i;
  164.         }
  165.     }
  166.  
  167.     cout << res << '\n';
  168. }
  169.  
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×