API tools faq
paste
Advertisement
ec1117

Untitled

ec1117
Nov 30th, 2020
141
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 9.41 KB | None | 0 0
raw download clone embed print report
  1. #include "bits/stdc++.h"
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef long double ld;
  7. typedef double db;
  8. typedef string str;
  9.  
  10. typedef pair<int,int> pi;
  11. typedef pair<pi, int> pii;
  12. typedef pair<ll,ll> pl;
  13. typedef pair<db,db> pd;
  14.  
  15. typedef vector<int> vi;
  16. typedef vector<bool> vb;
  17. typedef vector<ll> vl;
  18. typedef vector<db> vd;
  19. typedef vector<str> vs;
  20. typedef vector<pi> vpi;
  21. typedef vector<pl> vpl;
  22. typedef vector<pd> vpd;
  23. template<class T> using V = vector<T>;
  24. template<class T, size_t SZ> using AR = array<T,SZ>;
  25.  
  26. #define mp make_pair
  27. #define f first
  28. #define s second
  29. #define sz(x) (int)(x).size()
  30. #define all(x) begin(x), end(x)
  31. #define rall(x) (x).rbegin(), (x).rend()
  32. #define sor(x) sort(all(x))
  33. #define rsz resize
  34. #define ins insert
  35. #define ft front()
  36. #define bk back()
  37. #define pf push_front
  38. #define pb push_back
  39. #define eb emplace_back
  40. #define lb lower_bound
  41. #define ub upper_bound
  42.  
  43. #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
  44. #define F0R(i,a) FOR(i,0,a)
  45. #define For(i,a) FOR(i,0,a)
  46. #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
  47. #define R0F(i,a) ROF(i,0,a)
  48. #define Rof(i,a) ROF(i,0,a)
  49. #define trav(a,x) for (auto& a: x)
  50.  
  51. template<class T> bool ckmin(T& a, const T& b) {
  52.         return b < a ? a = b, 1 : 0; }
  53. template<class T> bool ckmax(T& a, const T& b) {
  54.         return a < b ? a = b, 1 : 0; }
  55. constexpr int pct(int x) { return __builtin_popcount(x); }
  56. constexpr int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x))
  57. ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
  58. ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
  59. ll half(ll x) { return fdiv(x,2); }
  60.  
  61. template<class T, class U> T fstTrue(T lo, T hi, U f) {
  62.         // note: if (lo+hi)/2 is used instead of half(lo+hi) then this will loop infinitely when lo=hi
  63.         hi ++; assert(lo <= hi); // assuming f is increasing
  64.         while (lo < hi) { // find first index such that f is true
  65.                 T mid = half(lo+hi);
  66.                 f(mid) ? hi = mid : lo = mid+1;
  67.         }
  68.         return lo;
  69. }
  70. template<class T, class U> T lstTrue(T lo, T hi, U f) {
  71.         lo --; assert(lo <= hi); // assuming f is decreasing
  72.         while (lo < hi) { // find first index such that f is true
  73.                 T mid = half(lo+hi+1);
  74.                 f(mid) ? lo = mid : hi = mid-1;
  75.         }
  76.         return lo;
  77. }
  78. template<class T> void remDup(vector<T>& v) {
  79.         sort(all(v)); v.erase(unique(all(v)),end(v)); }
  80.  
  81. // INPUT
  82. template<class A> void re(complex<A>& c);
  83. template<class A, class B> void re(pair<A,B>& p);
  84. template<class A> void re(vector<A>& v);
  85. template<class A, size_t SZ> void re(array<A,SZ>& a);
  86.  
  87. template<class T> void re(T& x) { cin >> x; }
  88. void re(db& d) { str t; re(t); d = stod(t); }
  89. void re(ld& d) { str t; re(t); d = stold(t); }
  90. template<class H, class... T> void re(H& h, T&... t) { re(h); re(t...); }
  91.  
  92. template<class A> void re(complex<A>& c) { A a,b; re(a,b); c = {a,b}; }
  93. template<class A, class B> void re(pair<A,B>& p) { re(p.f,p.s); }
  94. template<class A> void re(vector<A>& x) { trav(a,x) re(a); }
  95. template<class A, size_t SZ> void re(array<A,SZ>& x) { trav(a,x) re(a); }
  96.  
  97. // TO_STRING
  98. #define ts to_string
  99. str ts(char c) { return str(1,c); }
  100. str ts(const char* s) { return (str)s; }
  101. str ts(str s) { return s; }
  102. str ts(bool b) {
  103.         #ifdef LOCAL
  104.                 return b ? "true" : "false";
  105.         #else
  106.                 return ts((int)b);
  107.         #endif
  108. }
  109. template<class A> str ts(complex<A> c) {
  110.         stringstream ss; ss << c; return ss.str(); }
  111. str ts(vector<bool> v) {
  112.         str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]);
  113.         res += "}"; return res; }
  114. template<size_t SZ> str ts(bitset<SZ> b) {
  115.         str res = ""; F0R(i,SZ) res += char('0'+b[i]);
  116.         return res; }
  117. template<class A, class B> str ts(pair<A,B> p);
  118. template<class T> str ts(T v) { // containers with begin(), end()
  119.         #ifdef LOCAL
  120.                 bool fst = 1; str res = "{";
  121.                 for (const auto& x: v) {
  122.                         if (!fst) res += ", ";
  123.                         fst = 0; res += ts(x);
  124.                 }
  125.                 res += "}"; return res;
  126.         #else
  127.                 bool fst = 1; str res = "";
  128.                 for (const auto& x: v) {
  129.                         if (!fst) res += " ";
  130.                         fst = 0; res += ts(x);
  131.                 }
  132.                 return res;
  133.  
  134.         #endif
  135. }
  136. template<class A, class B> str ts(pair<A,B> p) {
  137.         #ifdef LOCAL
  138.                 return "("+ts(p.f)+", "+ts(p.s)+")";
  139.         #else
  140.                 return ts(p.f)+" "+ts(p.s);
  141.         #endif
  142. }
  143.  
  144. // OUTPUT
  145. template<class A> void pr(A x) { cout << ts(x); }
  146. template<class H, class... T> void pr(const H& h, const T&... t) {
  147.         pr(h); pr(t...); }
  148. void ps() { pr("\n"); } // print w/ spaces
  149. template<class H, class... T> void ps(const H& h, const T&... t) {
  150.         pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
  151.  
  152. // DEBUG
  153. void DBG() { cerr << "]" << endl; }
  154. template<class H, class... T> void DBG(H h, T... t) {
  155.         cerr << ts(h); if (sizeof...(t)) cerr << ", ";
  156.         DBG(t...); }
  157. #ifdef LOCAL // compile with -DLOCAL, chk -> fake assert
  158.         #define dbg(...) cerr << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
  159.         #define chk(...) if (!(__VA_ARGS__)) cerr << "Line(" << __LINE__ << ") -> function(" \
  160.                  << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
  161. #else
  162.         #define dbg(...) 0
  163.         #define chk(...) 0
  164. #endif
  165.  
  166. int gcd(int a, int b) {if (b == 0)return a;return gcd(b, a % b);}
  167. int max(int a,int b, int c){return max(a,max(b,c));}
  168. int min(int a,int b, int c){return min(a,min(b,c));}
  169. ll max(ll a,ll b, ll c){return max(a,max(b,c));}
  170. ll min(ll a,ll b, ll c){return min(a,min(b,c));}
  171. void dbga(int arr[], int n){vi v;For(i,n)v.pb(arr[i]);dbg(v);}
  172. void dbga(ll arr[], int n){vi v;For(i,n)v.pb(arr[i]);dbg(v);}
  173.  
  174. // FILE I/O
  175. void setIn(str s) { freopen(s.c_str(),"r",stdin); }
  176. void setOut(str s) { freopen(s.c_str(),"w",stdout); }
  177. void unsyncIO() { cin.tie(0)->sync_with_stdio(0); }
  178. void setIO(str s = "exercise") {
  179.         unsyncIO();
  180.         // cin.exceptions(cin.failbit);
  181.         // throws exception when do smth illegal
  182.         // ex. try to read letter into int
  183.         if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
  184. }
  185. // 576743 29995400689069LL
  186. int MOD = 1e9+7; // 998244353;
  187. const int MX = 50+5;
  188. const ll INF = 1e18;
  189. const ld PI = acos((ld)-1);
  190. const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1};
  191. mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
  192.  
  193. template<int SZ> struct Sieve {
  194.     bitset<SZ> pri; vi pr;
  195.     Sieve() { // cum[i] = # of primes up to i
  196.         pri.set(); pri[0] = pri[1] = 0;
  197.         for (int i = 4; i < SZ; i += 2) pri[i] = 0;
  198.         for (int i = 3; i*i < SZ; i += 2) if (pri[i])
  199.             for (int j = i*i; j < SZ; j += i*2) pri[j] = 0;
  200.         F0R(i,SZ) if (pri[i]) pr.pb(i);
  201.     }
  202. };
  203. Sieve<320000> S;
  204.  
  205. vi invs, fac, ifac; // make sure to convert to LL before doing any multiplications ...
  206. void genFac(int SZ) {
  207.     invs.rsz(SZ), fac.rsz(SZ), ifac.rsz(SZ);
  208.     invs[1] = fac[0] = ifac[0] = 1;
  209.     FOR(i,2,SZ) invs[i] = MOD-(ll)MOD/i*invs[MOD%i]%MOD;
  210.     FOR(i,1,SZ) {
  211.         fac[i] = (ll)fac[i-1]*i%MOD;
  212.         ifac[i] = (ll)ifac[i-1]*invs[i]%MOD;
  213.     }
  214. }
  215.  
  216. ll comb(int a, int b) {
  217.     if (a < b || b < 0) return 0;
  218.     return (ll)fac[a]*ifac[b]%MOD*ifac[a-b]%MOD;
  219. }
  220.  
  221.  
  222. typedef unsigned long long ul;
  223. ul mul(ul a, ul b, const ul mod = MOD) {
  224.     ll ret = a*b-mod*(ul)((ld)a*b/mod);
  225.     return ret+((ret<0)-(ret>=(ll)mod))*mod; }
  226. ul modPow(ul a, ul b, const ul mod = MOD) {
  227.     if (b == 0) return 1;
  228.     ul res = modPow(a,b/2,mod); res = mul(res,res,mod);
  229.     return b&1 ? mul(res,a,mod) : res;
  230. }
  231.  
  232. ll n;
  233. ll cnt[MX], dp[MX][MX][2];
  234. void go(int x, int prim){
  235.     For(i,n+1)For(j,n+1)For(k,2)dp[i][j][k]=0LL;
  236.     For(i,n+1)dp[0][i][0]=1LL;
  237.  
  238.     FOR(i,1,n+1)FOR(j,1,n+1){
  239.         if(__gcd(x*prim, j)==x*prim){
  240.             For(k,2)dp[i][j][k]=dp[i][j-1][k];
  241.             continue;
  242.         }
  243.         int w=0;
  244.         For(gr,fdiv(i,j)+1){
  245.             if(gr==1 && __gcd(x,j)==x)w=1;
  246.             int space=gr*j;
  247.             For(k,2){
  248.                 ll tmp=dp[i-space][j-1][k];
  249.                 tmp=mul(tmp,comb(i,space));//choose from
  250.                 tmp=mul(tmp,modPow(modPow(j,gr),MOD-2));//rotations
  251.                 tmp=mul(tmp,ifac[gr]);
  252.                 tmp=mul(tmp,fac[space]);
  253.                 dp[i][j][w|k]+=tmp;
  254.                 dp[i][j][w|k]%=MOD;
  255.             }
  256.         }
  257.     }
  258.     cnt[x]=dp[n][n][1];
  259.     assert(cnt[x]<MOD);
  260. }
  261.                 // if(dp[i][j][k]>=MOD)dp[i][j][w|k]-=MOD;
  262.  
  263. void solve(){
  264.     re(n,MOD);
  265.     genFac(n+5);
  266.     FOR(i,2,n+1)if(S.pri[i]){
  267.         int tmp=i;
  268.         while(tmp<=n){
  269.             go(tmp,i);
  270.             tmp*=i;
  271.         }
  272.     }
  273.     ll ret=1LL;
  274.     FOR(i,2,n+1)if(cnt[i]){
  275.         ret=mul(ret,modPow(i,cnt[i]));
  276.         dbg(i,cnt[i]);
  277.     }
  278.     ps(ret);
  279. }
  280.  
  281. int main() {
  282.         setIO();
  283.         solve();
  284.         // you should actually read the stuff at the bottom
  285. }
  286.  
  287. /* stuff you should look for
  288.         * int overflow, array bounds
  289.         * special cases (n=1?)
  290.         * do smth instead of nothing and stay organized
  291.         * WRITE STUFF DOWN
  292.         * DON'T GET STUCK ON ONE APPROACH
  293. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!