Advertisement
ismaeil

Counting Tilling

Jan 24th, 2022
945
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. const ll MOD = 1e9 + 7;
  7. const int M = 1111;
  8. const int N = 11;
  9.  
  10. ll dp[N][M][1 << N];
  11. int n ,m;
  12.  
  13. ll calc(int i ,int j ,int mask)
  14. {
  15.     if( i == n ) return calc(0 ,j + 1 ,mask);
  16.     if( j == m ) return !mask;
  17.  
  18.     ll &re = dp[i][j][mask];
  19.     if( re + 1 ) return re;
  20.  
  21.     re = calc(i + 1 ,j ,mask ^ (1 << i));
  22.     re %= MOD;
  23.  
  24.     int T = mask & (1 << i);
  25.     if( T == 0 && i <= n - 2 )
  26.     {
  27.         T = mask & (1 << (i + 1));
  28.         if( T == 0 )
  29.         {
  30.             re += calc(i + 2 ,j ,mask);
  31.             re %= MOD;
  32.         }
  33.     }
  34.  
  35.     return re;
  36. }
  37.  
  38. int main()
  39. {
  40.     scanf("%d%d" ,&n ,&m);
  41.  
  42.     memset(dp ,-1 ,sizeof dp);
  43.  
  44.     printf("%lld" ,calc(0 ,0 ,0));
  45.  
  46.     return 0;
  47. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement