fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int maxi = 5000;
  4. const int MaskMax = 1<<9;
  5. int dp[MaskMax];
  6. int dx[] = {1 , -1 , 0 , 0};
  7. int dy[] = {0 , 0 , 1 , -1};
  8. int mod = 10007;
  9. int onefloar(int mask)
  10. {
  11.     if(mask == MaskMax - 1)
  12.         return 1;
  13.     if(dp[mask] != -1) return dp[mask];
  14.     int i = 0;
  15.     while(mask & (1<<i)) i++;
  16.     int  x = i/3 , y = i%3;
  17.     int ans = 0;
  18.     for(int j = 0 ; j<4 ; j++)
  19.     {
  20.       if(x+ dx[j] < 3 && x + dx[j] >=0 && y+dy[j]< 3 && y+dy[j] >=0 )
  21.       {
  22.           int pos = (x+dx[j])*3 + (y+dy[j]);
  23.           if(!(mask & (1<<pos)))
  24.           {
  25.              ans+=onefloar(mask | (1<<i) | (1<<pos));
  26.              ans%=mod;
  27.           }
  28.       }
  29.     }
  30.     return dp[mask] = ans;
  31. }
  32. int ans[maxi][MaskMax];
  33. void solve()
  34. {
  35.     memset(dp , -1 ,sizeof dp);
  36.     ans[0][0] = 1;
  37.     for(int a = 1 ; a<=maxi ; a++)
  38.     {
  39.         for(int i = 0 ; i<MaskMax ; i++)
  40.         for(int j = 0 ; j<MaskMax ; j++)
  41.     {
  42.         if(i&j || (a%2&&j==0) ) continue;
  43.         ans[a][j]+=(ans[a-1][i] * onefloar(i|j));
  44.         ans[a][j]%=mod;
  45.     }
  46.     }
  47. }
  48.  
  49. int main() {
  50.     int t,n;
  51.     cin>>t;
  52.     solve();
  53.     while(t--)
  54.     {
  55.       scanf("%d", &n);
  56.       printf("%d\n" , ans[n][0]);
  57.     }
  58. 	return 0;
  59. }
  60.  
Runtime error #stdin #stdout 0.92s 13472KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/h7sUxN
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!