fork download
copy 
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <list>
  4. #include <map>
  5. #include <set>
  6. #include <deque>
  7. #include <queue>
  8. #include <stack>
  9. #include <bitset>
  10. #include <algorithm>
  11. #include <functional>
  12. #include <numeric>
  13. #include <utility>
  14. #include <sstream>
  15. #include <iostream>
  16. #include <iomanip>
  17. #include <cstdio>
  18. #include <cmath>
  19. #include <cstdlib>
  20. #include <cctype>
  21. #include <string>
  22. #include <cstring>
  23. #include <cstdio>
  24. #include <cmath>
  25. #include <cstdlib>
  26. #include <ctime>
  27. #include <string.h>
  28. #include <fstream>
  29. #include <cassert>
  30. #include <ext/pb_ds/assoc_container.hpp>
  31. #include <ext/pb_ds/tree_policy.hpp>
  32. //#include <sys/resource.h>
  33.  
  34. using namespace std;
  35. using namespace __gnu_pbds;
  36.  
  37. #ifdef loc
  38.  
  39. template<class T, class U> ostream &operator<<
  40.   (ostream &out,
  41.    const pair<T, U> &a) {
  42.   out << "[" << a.first << " " << a.second << "]";
  43.   return out;
  44. }
  45.  
  46. template<class T>
  47.   ostream &operator<<(ostream &out,
  48.                       const vector<T> &a) {
  49.   out << "[ ";
  50.   for(auto &it : a) {
  51.     out << it << " ";
  52.   }
  53.   out << "]";
  54.   return out;
  55. }
  56.  
  57. template<class T> ostream &operator<<(ostream &out, const set<T> &a) {
  58.     out << "[ ";
  59.     for(auto &it : a) {
  60.       out << it << " ";
  61.     }
  62.     out << "]";
  63.     return out;
  64.   }
  65.  
  66. template<class T>
  67.   ostream &operator<<(ostream &out,
  68.                       const multiset<T> &a) {
  69.   out << "[ ";
  70.   for(auto &it : a) {
  71.     out << it << " ";
  72.   }
  73.   out << "]";
  74.   return out;
  75. }
  76.  
  77. template<class T, class U>
  78.   ostream &operator<<(ostream &out,
  79.                       const map<T, U> &a) {
  80.   for(auto &it : a) {
  81.     out << it.first << " -> " << it.second << " | ";
  82.   }
  83.   return out;
  84. }
  85.  
  86. template<class T, class U>
  87.   ostream &operator<<(ostream &out,
  88.                       const multimap<T, U> &a) {
  89.   for(auto &it : a) {
  90.     out << it.first << " -> " << it.second << " | ";
  91.   }
  92.   return out;
  93. }
  94.  
  95. #define pra(a, n) cerr << #a << " : "; for(int i = 0; i <= n; ++i) cerr << a[i] << " "; cerr << endl;
  96.  
  97. #define praa(a, n, m) cerr << #a << " : " << endl; for(int i = 0; i <= n; ++i) { for(int j = 0;j <= m; ++j) cerr << a[i][j] << " "; cerr << endl; }
  98.  
  99. #define pr(...) __f(#__VA_ARGS__, __VA_ARGS__)
  100.  
  101. #define prl() cerr << __LINE__ << ": " << __PRETTY_FUNCTION__ << endl;
  102.  
  103. template <typename Arg1>
  104. void __f(const char *name, Arg1 &&arg1) {
  105.   cerr << name << " : " << arg1 << std::endl;
  106. }
  107.  
  108. template <typename Arg1, typename... Args>
  109. void __f(const char *names, Arg1 &&arg1,
  110.          Args &&... args) {
  111.   const char *comma = strchr(names + 1, ',');
  112.   cerr.write(names,
  113.              comma - names) << " : " << arg1 << " | ";
  114.   __f(comma + 1, args...);
  115. }
  116.  
  117. #define gc getchar
  118.  
  119. #else
  120.  
  121. #define pr(...)
  122. #define pra(a, n)
  123. #define praa(a, n, m)
  124. #define prl()
  125. #define gc getchar
  126.  
  127. #endif
  128.  
  129. #define mod 10007
  130.  
  131. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
  132. ordered_set;
  133. typedef long long ll;
  134. typedef vector<int> vi;
  135. typedef vector<vector<int>> vvi;
  136. typedef pair<int, int> pii;
  137. typedef vector<pair<int, int>> vpii;
  138. typedef vector<vector<pair<int, int>>> vvpii;
  139. typedef vector<ll> vl;
  140. typedef vector<vector<ll>>vvl;
  141. typedef pair<ll, ll> pll;
  142. typedef vector<pair<ll, ll>> vpll;
  143. typedef vector<vector<pair<ll, ll>>> vvpll;
  144.  
  145. template<typename T, typename U> static void amin(
  146.   T &x, U y) {
  147.   if(y < x) {
  148.     x = y;
  149.   }
  150. }
  151.  
  152. template<typename T, typename U> static void amax(
  153.   T &x, U y) {
  154.   if(x < y) {
  155.     x = y;
  156.   }
  157. }
  158.  
  159. ll po(ll a, ll b, ll m = mod) {
  160.   ll res = 1;
  161.   a %= m;
  162.   //assert(b >= 0);
  163.   for(; b; b >>= 1) {
  164.     if(b & 1) {
  165.       res = (res * a) % m;
  166.     }
  167.     a = (a * a) % m;
  168.   }
  169.   return res;
  170. }
  171.  
  172. #define inc_stack_limit const rlim_t kStackSize = 64 * 1024 * 1024; struct rlimit rl; rl.rlim_cur = kStackSize; setrlimit(RLIMIT_STACK, &rl);
  173. #define sz(a) int((a).size())
  174. #define all(a) (a).begin(),(a).end()
  175. #define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  176. #define pb push_back
  177. #define eb emplace_back
  178. #define mp make_pair
  179. #define F first
  180. #define S second
  181. #define rep(i, s, n)  for(int i = s; i <= (n); ++i)
  182. #define rev(i, n, s)  for(int i = (n); i >= s; --i)
  183. #define fore(x, a) for(auto &&x : a)
  184. #define fill(a, x) memset((a), (x), sizeof(a))
  185. const double eps = 1e-6;
  186. #define tcase int __T; cin >> __T; rep(Tc, 1, __T)
  187. #define ass(n, l, r) assert(n >= l and n <= r)
  188. #define endl '\n'
  189.  
  190. inline int add(int a, int b, int m = mod) {
  191.   a += b;
  192.   if(a >= m) {
  193.     a -= m;
  194.   }
  195.   return a;
  196. }
  197.  
  198. inline int mul(int a, int b, int m = mod) {
  199.   return (int)(((ll)a * (ll)b) % m);
  200. }
  201.  
  202. inline int ri() {
  203.   int c = gc();
  204.   int ret = 0;
  205.   while(c < '0' || c > '9') {
  206.     c = gc();
  207.   }
  208.   while(c >= '0' && c <= '9') {
  209.     ret = 10 * ret + c - 48;
  210.     c = gc();
  211.   }
  212.   return ret;
  213. }
  214.  
  215.  
  216. #define N 100005
  217.  
  218. int dp[5005][1 << 9];
  219. int mm[1 << 9];
  220. int dp2[10][511];
  221. int a[9][9];
  222. int f[9];
  223.  
  224.  
  225. int main() {
  226.   rep(i, 0, 511) {
  227.     fill(a, 0);
  228.     int c1 = 0, c2 = 0;
  229.     vi d, e;
  230.     d.push_back(-1);
  231.     rep(i1, 0, 2) {
  232.       rep(j1, 0, 2) {
  233.         if((i >> (i1 * 3 + j1)) & 1) {
  234.           if(!((i1 + j1) & 1)) {
  235.             c1++;
  236.             d.push_back(i1 * 3 + j1);
  237.           } else {
  238.             c2++;
  239.             e.push_back(i1 * 3 + j1);
  240.           }
  241.         }
  242.       }
  243.     }
  244.     //pr(i);
  245.     //pr(d, e);
  246.     if(c1 == c2) {
  247.       rep(i1, 0, 2) {
  248.         rep(j1, 0, 2) {
  249.           rep(i2, 0, 2) {
  250.             rep(j2, 0, 2) {
  251.               if(((i >> (i1 * 3 + j1)) & 1) && ((i >> (i2 * 3 + j2)) & 1) &&
  252.                  (abs(i1 - i2) + abs(j1 - j2) == 1) && (!((i1 + j1) & 1))) {
  253.                 a[i1 * 3 + j1][i2 * 3 + j2] = 1;
  254.               }
  255.             }
  256.           }
  257.         }
  258.       }
  259.       int c = c1;
  260.       rep(i1, 0, c - 1) {
  261.         f[e[i1]] = i1;
  262.       }
  263.       fill(dp2, 0);
  264.       dp2[0][0] = 1;
  265.       rep(i1, 1, c) {
  266.         dp2[i1][0] = 1;
  267.         rep(j, 1, (1 << c) - 1) {
  268.           dp2[i1][j] = dp2[i1 - 1][j];
  269.           rep(k, 0, c - 1) {
  270.             if(a[d[i1]][e[k]] && ((j >> k) & 1)) {
  271.               dp2[i1][j] += dp2[i1 - 1][j ^ (1 << k)];
  272.             }
  273.           }
  274.         }
  275.       }
  276.       mm[i] = dp2[c][(1 << c) - 1];
  277.     }
  278.     //pr(i, mm[i]);
  279.   }
  280.   boost;
  281.   dp[0][0] = 1;
  282.   rep(i, 1, 5002) {
  283.     rep(j, 0, 511) { //prev was j.
  284.       //for each remaining ..
  285.       int x = 511 ^ j;
  286.       for(int k = x; ; k = (k - 1)&x) {
  287.         dp[i][k] += mm[511 ^ (j | k)] * dp[i - 1][j];
  288.         if(dp[i][k] >= mod) {
  289.           dp[i][k] -= mod;
  290.         }
  291.         if(k == 0) {
  292.           break;
  293.         }
  294.       }
  295.     }
  296.   }
  297.   tcase {
  298.     int n;
  299.     cin >> n;
  300.     cout << dp[n][0] << endl;
  301.   }
  302.   return 0;
  303. }
Runtime error #stdin #stdout 0.15s 13504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UT395f
language:
C++14 (gcc 8.3)
created:
8 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!