A1379 [NOIP2018 提高组 T5] 填数游戏

#include <bits/stdc++.h>
using namespace std;

// NOIP2018 提高组 T5 填数游戏（A1379）
//
// 记 a[r][c] 为格子里的数。
// 性质 1：每条左下到右上的反对角线上的数单调（右上 <= 左下）。
// 性质 2：若某个格子的左边与上面两个格子填的数相同，
//         那么以它为左上角的子矩形里，每条反对角线上的数都相同。
// 枚举每条反对角线的「分界点」，逐条检查这两条性质，累加合法方案数。
const long long MOD = 1000000007LL;

int n, m;
vector<vector<int>> a;

long long powmod(long long b, long long e) {
    long long r = 1;
    while (e > 0) {
        if (e & 1) r = r * b % MOD;
        b = b * b % MOD;
        e >>= 1;
    }
    return r;
}

// 性质 2：若 a[i][j-1] == a[i-1][j]，则子矩形 [i..n-1][j..m-1] 的每条斜线都相同
bool okAll() {
    for (int i = 1; i < n; i++) {
        for (int j = 1; j < m; j++) {
            if (a[i][j - 1] != a[i - 1][j]) continue; // 没有触发
            for (int k = i + j; k <= n + m - 2; k++) {
                int v = -1;
                for (int r = i; r < n; r++) {
                    int c = k - r;
                    if (c < j || c >= m) continue;
                    if (v < 0) v = a[r][c];
                    else if (v != a[r][c]) return false;
                }
            }
        }
    }
    return true;
}

// 枚举第 k 条反对角线的分界点：前 cut 个格子填 0，其余填 1
long long dfs(int k) {
    if (k == n + m - 1) return okAll() ? 1 : 0;
    int r0 = max(0, k - m + 1), r1 = min(k, n - 1);
    int len = r1 - r0 + 1;
    long long res = 0;
    for (int c = 0; c <= len; c++) {
        for (int r = r0; r <= r1; r++) a[r][k - r] = (r - r0 < c) ? 0 : 1;
        res += dfs(k + 1);
    }
    return res % MOD;
}

// 统计 N × M 的合法方案数（枚举所有分界点组合）
long long countWays(int N, int M) {
    n = N;
    m = M;
    a.assign(n, vector<int>(m, 0));
    return dfs(0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    if (N > M) swap(N, M); // 对称性：f(n,m) = f(m,n)

    if (N == 1) { // 只有一条路径，任意填法都合法
        cout << powmod(2, M) << "\n";
        return 0;
    }

    long long ans;
    if (M >= N + 2) {
        // 性质：m >= n+2 时 f(n,m) = 3^(m-n-1) · f(n,n+1)
        ans = countWays(N, N + 1) * powmod(3, M - N - 1) % MOD;
    } else {
        ans = countWays(N, M);
    }
    cout << ans % MOD << "\n";
    return 0;
}