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;
}










