// Задача о числе замощения доски n*m домино 1*2 // Динамика по изломанному профилю #include #include using namespace std; int main() { int n, m; cin >> n >> m; if (n > m) swap(n, m); int dp[n * m + 1][1 << n]; for (int i = 0; i <= n * m; ++i) memset(dp[i], 0, (1 << n) * sizeof(int)); dp[0][0] = 1; // параметры - количество покрытых клеток, маска покрытия следующих n клеток for (int i = 0; i < n * m; ++i) for (int mask = 0 ; mask < (1 << n); ++mask) { if (mask & 1) { dp[i + 1][mask >> 1] += dp[i][mask]; // текущая клетка покрыта, пропускаем её } else { // иначе надо покрыть dp[i + 1][(mask | (1 << n)) >> 1] += dp[i][mask]; // пробуем покрыть вертикальной, это всегда возможно if (!(mask & 2) && (i + 1) % n) dp[i + 1][(mask | 2) >> 1] += dp[i][mask]; // пробуем покрыть горизонтальной, должна быть свободна } // следующая и клетка должна быть не последней в столбце } cout << dp[n * m][0] << endl; // пробежали все клетки, маска пустая, иначе что-то вылезло }