题解

时间内存击败所有人

#include <iostream>
#include <vector>

using namespace std;

const long long MOD = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<vector<bool>> grid(n, vector<bool>(n));
    for (int y = 0; y < n; y++) {
        string line;
        cin >> line;
        for (int x = 0; x < n; x++) {
            grid[y][x] = line[x] == 'G';
        }
    }
    long long answer = 0;
    vector<vector<vector<vector<long long>>>> dpPrev(2,
        vector<vector<vector<long long>>>(2, vector<vector<long long>>(n, vector<long long>(n))));
    for (int y = 0; y < n; y++) {
        vector<vector<vector<vector<long long>>>> sums1(2,
            vector<vector<vector<long long>>>(2, vector<vector<long long>>(n, vector<long long>(n))));
        for (int x2 = 0; x2 < n; x2++) {
            for (int x1 = x2; x1 >= 0; x1--) {
                for (int b = 0; b < 2; b++) {
                    sums1[0][b][x1][x2] = dpPrev[0][b][x1][x2];
                    if (x1 < x2) {
                        sums1[0][b][x1][x2] += sums1[0][b][x1 + 1][x2];
                        sums1[0][b][x1][x2] %= MOD;
                    }
                }
            }
            for (int x1 = 0; x1 <= x2; x1++) {
                for (int b = 0; b < 2; b++) {
                    sums1[1][b][x1][x2] = dpPrev[1][b][x1][x2];
                    if (x1 > 0) {
                        sums1[1][b][x1][x2] += sums1[1][b][x1 - 1][x2] + dpPrev[0][b][x1 - 1][x2];
                        sums1[1][b][x1][x2] %= MOD;
                    }
                }
            }
        }
        vector<vector<vector<vector<long long>>>> sums2(2,
            vector<vector<vector<long long>>>(2, vector<vector<long long>>(n, vector<long long>(n))));
        for (int x1 = 0; x1 < n; x1++) {
            for (int x2 = x1; x2 < n; x2++) {
                for (int a = 0; a < 2; a++) {
                    sums2[a][0][x1][x2] = sums1[a][0][x1][x2];
                    if (x2 > x1) {
                        sums2[a][0][x1][x2] += sums2[a][0][x1][x2 - 1];
                        sums2[a][0][x1][x2] %= MOD;
                    }
                }
            }
            for (int x2 = n - 1; x2 >= x1; x2--) {
                for (int a = 0; a < 2; a++) {
                    sums2[a][1][x1][x2] = sums1[a][1][x1][x2];
                    if (x2 < n - 1) {
                        sums2[a][1][x1][x2] += sums2[a][1][x1][x2 + 1] + sums1[a][0][x1][x2 + 1];
                        sums2[a][1][x1][x2] %= MOD;
                    }
                }
            }
        }
        vector<vector<vector<vector<long long>>>> dpNext(2,
            vector<vector<vector<long long>>>(2, vector<vector<long long>>(n, vector<long long>(n))));
        for (int x1 = 0; x1 < n; x1++) {
            bool valid = true;
            for (int x2 = x1; x2 < n; x2++) {
                valid = valid && grid[y][x2];
                if (valid) {
                    dpNext[0][0][x1][x2] = (sums2[0][0][x1][x2] + 1LL) % MOD;
                    dpNext[0][1][x1][x2] = (sums2[0][1][x1][x2] - (x2 == n - 1 ? 0LL : (sums2[0][1][x2 + 1][x2 + 1] + dpPrev[0][0][x2 + 1][x2 + 1])) + (2LL * MOD)) % MOD;
                    dpNext[1][0][x1][x2] = sums2[1][0][x1][x2];
                    dpNext[1][1][x1][x2] = sums2[1][1][x1][x2];
                } else {
                    for (int a = 0; a < 2; a++) {
                        for (int b = 0; b < 2; b++) {
                            dpNext[a][b][x1][x2] = 0;
                        }
                    }
                }
                for (int a = 0; a < 2; a++) {
                    for (int b = 0; b < 2; b++) {
                        answer += dpNext[a][b][x1][x2];
                        answer %= MOD;
                    }
                }
            }
        }
        dpPrev = dpNext;
    }
    cout << answer << endl;
    return 0;
}