#include<iostream> using namespace std; int dp[14*14][1<<15] = { 0, }; int n, m; int search(int num, int bitma){ if(dp[num][bitma]){ if(dp[num][bitma] == -1){ return 0; } return dp[num][bitma]; } if(num == n * m - 1){ if(bitma){ return bitma; } dp[num][bitma] = -1; return 0; } if(bitma & 1){ dp[num][bitma] = search(num + 1, bitma >> 1) % 9901; if(dp[num][bitma]){ return dp[num][bitma]; } dp[num][bitma] = -1; return 0; } if( num % m != m - 1 && !((bitma >> 1) & 1)){ dp[num][bitma] = search(num + 1, (bitma >> 1) + 1) % 9901; } if( num < (n-1) * m){ dp[num][bitma] = (dp[num][bitma] + search(num + 1, (bitma >> 1) + (1<<(m-1)))) % 9901; } if(dp[num][bitma]){ return dp[num][bitma]; } dp[num][bitma] = -1; return 0; } int main(){ cin>> n >> m; cout << search(0, 0); }
#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; }