leetcode

0 class Solution {

1 typedef array<array<int, 16>, 16> cache_t;

2 static inline constexpr const cache_t cache = []() constexpr -> cache_t {

3 cache_t cache = {{0}};

4 for (int i = 1; i <= 15; i++) {

5 cache[i].fill(INT_MAX);

6 int count = 0;

7 for (int j = 1; j <= 15; j++) {

8 if (i % j == 0 || j % i == 0) cache[i][count++] = j;

9 }

10 }

11 return cache;

12 }();

13

14 int dp[16][65536];

15

16 public:

17 Solution() { memset(dp, 0xFF, sizeof(dp)); }

18

19 int countArrangement(int n, int crnt = 1, uint16_t mask = 0) {

20 if (crnt > n) return 1;

21 if (dp[crnt][mask] != -1) return dp[crnt][mask];

22

23 int res = 0;

24 for (int num : cache[crnt]) {

25 if (num > n) break;

26 if (mask & (1 << num)) continue;

27 res += countArrangement(n, crnt + 1, mask | (1 << num));

28 }

29

30 return dp[crnt][mask] = res;

31 }

32 };