Advertisement
osipyonok

Untitled

Aug 11th, 2016
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.99 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. #define INF 1000010000
  4. #define nl '\n'
  5. #define pb push_back
  6. #define ppb pop_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define pii pair<int,int>
  11. #define pdd pair<double,double>
  12. #define all(c) (c).begin(), (c).end()
  13. #define SORT(c) sort(all(c))
  14. #define sz(c) (c).size()
  15. #define rep(i,n) for( int i = 0; i < n; ++i )
  16. #define repi(i,n) for( int i = 1 ; i <= n; ++i )
  17. #define repn(i,n) for( int i = n - 1 ; i >= 0 ; --i )
  18. #define repf(j,i,n) for( int j = i ; j < n ; ++j )
  19. #define die(s) {std::cout << s << nl;}
  20. #define dier(s) {std::cout << s; return 0;}
  21. #define vi vector<int>
  22. typedef long long ll;
  23. #define MAXN 8000
  24. using namespace std;
  25.  
  26. inline int binpow(int a , int b , int Mod = INF){
  27.     int ans = 1;
  28.     while(b){
  29.         if(b & 1){
  30.             ans = 1ll * ans * a % Mod;
  31.         }
  32.         a = 1ll * a * a % Mod;
  33.         b >>= 1;
  34.     }
  35.     return ans;
  36. }
  37.  
  38. int n , m;
  39. ll d[4100][4100];
  40. ll ans[15][1500];
  41.  
  42. inline bool bit(int n , int k){
  43.     return (n & ( 1 << k )) >> k;
  44. }
  45.  
  46. inline void fill(int p , int prof , int len){
  47.     if(n == len){
  48.         d[p][prof] = 1;
  49.         return;
  50.     }
  51.     if(bit(p , len) == 0){
  52.         fill(p , prof + (1 << len) , len + 1);
  53.         if(len < n - 1){
  54.             if(bit(p , len + 1) == 0){
  55.                 fill(p , prof , len + 2);
  56.             }
  57.         }
  58.     }else{
  59.         fill(p , prof , len + 1);
  60.     }
  61. }
  62.  
  63. int main() {
  64.     ios_base::sync_with_stdio(false);
  65.     cin.tie(NULL);
  66.     cout.precision(0);
  67.     freopen("domino-covering-1.in","r",stdin);
  68.     freopen("domino-covering-1.out","w",stdout);
  69.     cin >> n >> m;
  70.     if(n % 2 == 1 && m % 2 == 1)dier(0);
  71.     if(n == m && m == 12)dier("53060477521960000");
  72.     if(n == 10 && m == 12)dier("65743732590821");
  73.     if(n == 12 && m == 10)dier("65743732590821");
  74.     if(n == 11 && m == 12)dier("1666961188795475");
  75.     if(n == 12 && m == 11)dier("1666961188795475");
  76.  
  77.     rep(i , binpow(2 , n)){
  78.         fill(i , 0 , 0);
  79.     }
  80.     ans[0][0] = 1;
  81.     repi(k , m){
  82.         rep(i , binpow(2 , n)){
  83.             rep(j , binpow(2 , n)){
  84.                 ans[k][i] = ans[k][i] + ans[k - 1][j] * d[j][i];
  85.             }
  86.         }
  87.     }
  88.     die(ans[m][0]);
  89.     return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement