fork(1) download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include <stack>
  4. #include <queue>
  5. #include <deque>
  6. #include <vector>
  7. #include <string>
  8. #include <string.h>
  9. #include <cstdlib>
  10. #include <ctime>
  11. #include <cmath>
  12. #include <map>
  13. #include <set>
  14. #include <iostream>
  15. #include <sstream>
  16. #include <numeric>
  17. #include <cctype>
  18. #define fi first
  19. #define se second
  20. #define rep(i,n) for(int i = 0; i < n; ++i)
  21. #define rrep(i,n) for(int i = 1; i <= n; ++i)
  22. #define drep(i,n) for(int i = n-1; i >= 0; --i)
  23. #define gep(i,g,j) for(int i = g.head[j]; i != -1; i = g.e[i].next)
  24. #define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
  25. #define rng(a) a.begin(),a.end()
  26. #define maxs(x,y) x = max(x,y)
  27. #define mins(x,y) x = min(x,y)
  28. #define pb push_back
  29. #define sz(x) (int)(x).size()
  30. #define pcnt __builtin_popcount
  31. #define snuke srand((unsigned)clock()+(unsigned)time(NULL));
  32. #define df(x) int x = in()
  33. using namespace std;
  34. typedef long long int ll;
  35. typedef pair<int,int> P;
  36. typedef vector<int> vi;
  37. typedef vector<vi> vvi;
  38. inline int in() { int x; scanf("%d",&x); return x;}
  39. inline void priv(vi a) { rep(i,sz(a)) printf("%d%c",a[i],i==sz(a)-1?'\n':' ');}
  40.  
  41. const int MX = 100005, INF = 1000010000;
  42. const ll LINF = 1000000000000000000ll;
  43. const double eps = 1e-10;
  44.  
  45. // Mod int
  46. int mod;
  47. struct mint{
  48.   ll x;
  49.   mint():x(0){}
  50.   mint(ll x):x((x%mod+mod)%mod){}
  51.   mint operator+=(const mint& a){ if((x+=a.x)>=mod) x-=mod; return *this;}
  52.   mint operator-=(const mint& a){ if((x+=mod-a.x)>=mod) x-=mod; return *this;}
  53.   mint operator*=(const mint& a){ (x*=a.x)%=mod; return *this;}
  54.   mint operator+(const mint& a)const{ return mint(*this) += a;}
  55.   mint operator-(const mint& a)const{ return mint(*this) -= a;}
  56.   mint operator*(const mint& a)const{ return mint(*this) *= a;}
  57.   bool operator==(const mint& a)const{ return x == a.x;}
  58. };
  59. //
  60.  
  61. map<vi,int> mp;
  62. vvi pm;
  63. vvi to;
  64.  
  65. void genst() {
  66.   vi a(4);
  67.   rep(i,4) a[i] = i;
  68.   queue<vi> q;
  69.   mp[a] = 0;
  70.   pm = vvi(15);
  71.   pm[0] = a;
  72.   to = vvi(15,vi(1<<4));
  73.   q.push(a);
  74.   while(sz(q)) {
  75.     a = q.front(); q.pop();
  76.     // priv(a);
  77.     int v = mp[a];
  78.     rep(i,1<<4) {
  79.       vi b(4);
  80.       rep(j,4) b[j] = j;
  81.       rep(j,4)rep(k,j) if ((i>>j&1) && (i>>k&1)) {
  82.         int xj = a[j];
  83.         int xk = a[k];
  84.         if (xj > xk) swap(xj,xk);
  85.         // b[xk] = xj;
  86.         mins(b[xk],xj);
  87.       }
  88.       vi c = a;
  89.       rep(j,4) c[j] = b[c[j]];
  90.       rep(j,4) b[j] = -1;
  91.       int cnt = 0;
  92.       rep(j,4) {
  93.         if (b[c[j]] != -1) continue;
  94.         b[c[j]] = cnt++;
  95.       }
  96.       rep(j,4) c[j] = b[c[j]];
  97.       int u = 0;
  98.       if (mp.count(c)) {
  99.         u = mp[c];
  100.       } else {
  101.         u = sz(mp);
  102.         mp[c] = u;
  103.         pm[u] = c;
  104.         q.push(c);
  105.       }
  106.       to[v][i] = u;
  107.     }
  108.   }
  109. }
  110.  
  111. mint dp[11][15][1<<4][5][90][1<<4];
  112.  
  113. int main() {
  114.   int n;
  115.   scanf("%d%d",&n,&mod);
  116.   genst();
  117.   // cout<<sz(mp)<<endl;
  118.   dp[0][0][0][0][0][0] = 1;
  119.   rep(i,10)rep(j,15)rep(k,1<<4)rep(l,3)rep(h,77)rep(u,1<<4) {
  120.     mint x = dp[i][j][k][l][h][u];
  121.     if (x.x == 0) continue;
  122.     int ni = i+1;
  123.     rep(f,1<<4)rep(g,1<<4) {
  124.       if (i == 0 && g != f) continue;
  125.       if ((g&f) != g) continue;
  126.       mint p = 1;
  127.       if (i) rep(r,4) if(g>>r&1) p *= 2;
  128.       int nj = to[j][f];
  129.       int nk = k^g;
  130.       int nl = l+pcnt(g)%2;
  131.       int nh = h+pcnt(f)*2-pcnt(g);
  132.       int nu = u|f;
  133.       dp[ni][nj][nk][nl][nh][nu] += x*p;
  134.       // cout<<i<<" "<<j<<" "<<k<<" "<<l<<" "<<h<<" "<<u<<" "<<f<<" "<<g<<endl;
  135.       // cout<<ni<<" "<<nj<<" "<<nk<<" "<<nl<<" "<<nh<<" "<<nu<<" "<<x.x<<" "<<p.x<<endl;
  136.     }
  137.   }
  138.   mint ans = 0;
  139.   rep(j,15)rep(k,1<<4)rep(l,3)rep(u,1<<4) {
  140.     if (pcnt(k)+l > 2) continue;
  141.     vi a = pm[j];
  142.     set<int> s;
  143.     rep(i,4) if (u>>i&1) s.insert(a[i]);
  144.     if (sz(s) == 1) ans += dp[10][j][k][l][n][u];
  145.   }
  146.   cout<<ans.x<<endl;
  147.   return 0;
  148. }
  149.  
  150.  
  151.  
  152.  
  153.  
  154.  
Success #stdin #stdout 0.73s 152000KB
comments (?)
stdin
copy 
19 1000000007
stdout
copy 
759357575
https://ideone.com/4GvFEU
language:
C++14 (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!