3.2. 박인서 ¶
#include <iostream> #include <cstring> int d[14 * 14][1 << 14]; int n, m; int go(int t, int s) { if (t >= n*m) { if(t == n*m && s == 0) return 1; return 0; } if (d[t][s] >= 0) return d[t][s] % 9901; int& res = d[t][s]; if (s % 2 == 1) res=go(t + 1, s >> 1); else { res = go(t + 1, (s >> 1) | (1 << m - 1)); if (s % 4 == 0 && t%m != (m - 1)) res+=go(t + 2, s >> 2); } return res % 9901; } int main() { std::cin >> n >> m; memset(d, -1, sizeof(d)); std::cout << go(0, 0); return 0; }