Advertisement
TimxAG

Untitled

Dec 17th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.15 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n, m;
  4. vector < vector<long long> > d;
  5.  
  6. void calc (int x = 0, int y = 0, int mask = 0, int next_mask = 0)
  7. {
  8. if (x == n)
  9. return;
  10. if (y >= m)
  11. d[x+1][next_mask] += d[x][mask];
  12. else
  13. {
  14. int my_mask = 1 << y;
  15. if (mask & my_mask)
  16. calc (x, y+1, mask, next_mask);
  17. else
  18. {
  19. calc (x, y+1, mask, next_mask | my_mask);
  20. if (y+1 < m && ! (mask & my_mask) && ! (mask & (my_mask << 1)))
  21. calc (x, y+2, mask, next_mask);
  22. }
  23. }
  24. }
  25. int main()
  26.  
  27. { int sum = 0,i;
  28. cin >> n >> m;
  29. d.resize (n+1, vector<long long> (1<<m));
  30. d[0][0] = 1;
  31. for (int x=0; x<n; ++x)
  32. for (int mask=0; mask<(1<<m); ++mask)
  33. calc (x, 0, mask, 0);
  34. for (i=1;i<=n-1;i++) sum +=d[i][0] * pow(2,(n*m/2))-sum;
  35. cout << d[n][0] * pow(2,(n*m/2)) - sum << " " << sum;
  36. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement