fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // BEGIN template
  5. #define FASTIO  std::ios::sync_with_stdio(false)
  6. #define SHOW(X) (cout << ">>>>> " << #X << ": " << (X) << endl), fflush(stdout)
  7. #define  rp(ITER,BEG,END) for (int ITER = BEG, ENDD = END; ITER <= ENDD; ITER++)
  8. #define rpd(ITER,BEG,END) for (int ITER = BEG, ENDD = END; ITER >= ENDD; ITER--)
  9. #define LSOne(X)  ((X)&(-(X)))
  10.  
  11. #define MAXN      5005
  12. #define MAXLOGN   18
  13. #define MOD       10007
  14. #define oo        0x3f3f3f3f
  15. #define OO        0x3f3f3f3f3f3f3f3fL
  16. #define MAX_PRIME 1000000
  17. #define TOT_PRIME 100000
  18.  
  19. #define ff first
  20. #define ss second
  21. #define pb push_back
  22. #define eb emplace_back
  23.  
  24. enum {WHITE=0,GRAY,BLACK};
  25. enum {UNVISITED=-1};
  26.  
  27. typedef long long ll;
  28. typedef pair<int,int> ii;
  29. typedef pair<ll,int> lli;
  30. typedef vector<int> vi;
  31.  
  32. int pass = 1;
  33. // END template
  34.  
  35. const int all = 0x1ff;
  36. inline int gmask(int u) {
  37.   return 1<<(u-1);
  38. }
  39. inline int has(int mask, int u) {
  40.   return (mask&gmask(u))>>(u-1);
  41. }
  42. inline int rem(int mask, int u) {
  43.   return mask&(~gmask(u));
  44. }
  45. int nei[][4] = {
  46.   {0,0,0,0},
  47.   {2,4,0,0},
  48.   {1,3,5,0},
  49.   {2,6,0,0},
  50.   {1,5,7,0},
  51.   {2,4,6,8},
  52.   {3,5,9,0},
  53.   {4,8,0,0},
  54.   {5,7,9,0},
  55.   {6,8,0,0}
  56. };
  57.  
  58. short dp[MAXN][3][3][3][3][3][3][3][3][3];
  59. short f(int i, int m1, int m2) {
  60.   short& ans = dp[i][has(m2,1)?2:has(m1,1)][has(m2,2)?2:has(m1,2)][has(m2,3)?2:has(m1,3)][has(m2,4)?2:has(m1,4)][has(m2,5)?2:has(m1,5)][has(m2,6)?2:has(m1,6)][has(m2,7)?2:has(m1,7)][has(m2,8)?2:has(m1,8)][has(m2,9)?2:has(m1,9)];
  61.   if (ans >= 0) return ans;
  62.   if (!m1) {
  63.     if (i == 1) return ans = (m2 ? 0 : 1);
  64.     return ans = f(i-1,all&~m2,0);
  65.   }
  66.   ans = 0;
  67.   for (int j = 1; j <= 9; j++) if (has(m1,j)) {
  68.     m1 = rem(m1,j);
  69.     ans = (ans+f(i,m1,m2|gmask(j)))%MOD;
  70.     for (int k = 0; k < 4 && nei[j][k]; k++) if (has(m1,nei[j][k])) {
  71.       ans = (ans+f(i,rem(m1,nei[j][k]),m2))%MOD;
  72.     }
  73.     return ans;
  74.   }
  75. }
  76.  
  77. int main() {
  78.   memset(dp,-1,sizeof dp);
  79.   int T;
  80.   cin >> T;
  81.   while (T--) {
  82.     int N;
  83.     cin >> N;
  84.     cout << (N==0 ? 1 : (N&1 ? 0 : f(N,all,0))) << endl;
  85.   }
  86.   return 0;
  87. }
Success #stdin #stdout 0.23s 197120KB
comments (?)
stdin 
5
2
4
1576
2680
5000
stdout 
229
7728
229
7728
3421
https://ideone.com/2dxXNW
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!