fork download 
  1. #include <algorithm>
  2. #include <ctime>
  3. #include <cmath>
  4. #include <set>
  5. #include <map>
  6. #include <stack>
  7. #include <vector>
  8. #include <string>
  9. #include <cstdio>
  10. #include <climits>
  11. #include <cstring>
  12. #include <cstdlib>
  13. #include <iostream>
  14.  
  15. using namespace std;
  16.  
  17. #define sci stack <int>
  18. #define vci vector <int>
  19. #define vcs vector <string>
  20. #define vcd vector <double>
  21. #define vci64 vector <long long>
  22.  
  23. const int maxn = 9 + 5;
  24. const int maxk = 9 * 9 + 5;
  25.  
  26. typedef unsigned int uint;
  27. typedef long long int64;
  28. typedef unsigned long long uint64;
  29.  
  30. template <class T> inline T Sqr(const T & x) { return x * x; }
  31. template <class T> inline T Abs(const T & x) { return x > 0 ? x : -x; }
  32. template <class T> inline T Min(const T & a, const T & b) { return a < b ? a : b; }
  33. template <class T> inline T Max(const T & a, const T & b) { return a > b ? a : b; }
  34. template <class T> inline T Ksm(const T & a, const T & b, const T & m) { T _ = 1; for (; b; b >>= 1, a = a * a % m) (b & 1) ? _ = _ * a % m : 0; return _ % m; }
  35. template <class T> inline void Swap(T & a, T & b) { T _; _ = a; a = b; b = _; }
  36.  
  37. int n, k, cn[1 << 9 + 1], cnt, state[1 << 9 + 1];
  38. int64 f[maxn][maxk][1 << 9 + 1], ans;
  39.  
  40. void dfs(int wid, int sta)
  41. {
  42.    if (wid == n) return state[++cnt] = sta, (void) 0;
  43.    if (dfs(wid + 1, sta << 1), !(sta & 1)) dfs(wid + 1, sta << 1 | 1);
  44. }
  45.  
  46. bool check(int a, int b) { return !(a & b) && !((a << 1) & b) && !((a >> 1) & b); }
  47.  
  48. int main()
  49. {
  50.  
  51.    scanf("%d%d", &n, &k), dfs(0, 0);
  52.    for (int i = 1; i <= (1 << n) - 1; ++i)
  53.       cn[i] = cn[i / 2] + (i & 1);
  54.    f[0][0][1] = 1;
  55.    for (int i = 1; i <= n; ++i)
  56.       for (int j = 0; j <= k; ++j)
  57.          for (int li = 1; li <= cnt; ++li)
  58.             for (int ru = 1; ru <= cnt; ++ru)
  59.                if ((j >= cn[state[ru]]) && (check(state[li], state[ru])))
  60.                   f[i][j][ru] += f[i - 1][j - cn[state[ru]]][li];
  61.    for (int i = 1; i <= cnt; ++i) ans += f[n][k][i];
  62.    printf("%lld", ans);
  63.  
  64.    return 0;
  65. }
  66.  
Success #stdin #stdout 0.02s 12328KB
comments (?)
stdin 
3 2
stdout 
16
https://ideone.com/XAjBgR
language:
C++ (gcc 8.3)
created:
13 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!