E 小红的gcd

我们只需要分开考虑 'g', 'c', 'd' 的全部排列就行

路径总长度 L = 2n - 1, 每个字符出现总次数为 L / 3

由于只能向下 或者 向右走 那么实际上我所需要的每个格子的字符是唯一确定的

也就是我走到 (i, j) 时 我对应的字符的位置就是 i + j - 2 (此处为1-index)

那么使用一维滚动数组即可

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

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

using i128 = __int128;
using u128 = unsigned __int128;

using point_t = long double;
mt19937_64 rng(random_device{}());
constexpr i64 inf = 1E18;
constexpr int N = (1 << 21) + 100, mod = 998244353;

i64 ceil(i64 a, i64 b) {
    if (a >= 0) return (a + b - 1) / b;
    else return a / b;
}

i64 floor(i64 a, i64 b) {
    if (a >= 0) return a / b;
    else return (a + b - 1) / b;
}

#define multitests

string s[1001];

void solve() {
    int n;cin >> n;
    for (int i = 0;i < n; ++ i) cin >> s[i];
    vector<char> let = {'g', 'c', 'd'};
    sort(let.begin(), let.end());
    int k = (2 * n - 1) / 3; // 每位字符出现总次数
    i64 ans = 0;

    do {
        vector<i64> dp(n + 1);
        for (int i = 1;i <= n; ++ i) 
            for (int j = 1;j <= n; ++ j) {
                int id = i + j - 2; // 0-index
                char c;
                // 当前位置满足条件的字符
                if (id < k) c = let[0];
                else if (id < 2 * k) c = let[1];
                else c = let[2]; 
                if (i == 1 and j == 1) {
                    if (s[0][0] == c) dp[1] = 1;
                    continue;
                }
                if (s[i - 1][j - 1] != c) dp[j] = 0;
                else dp[j] = (dp[j] + dp[j - 1]) % mod;
            }
        ans = (ans + dp[n]) % mod;
    } while (next_permutation(let.begin(), let.end()));
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cout << fixed << setprecision(12);
    // freopen("./in.txt","r",stdin);
    // freopen("./out.txt","w",stdout);
    int T = 1;
    #ifdef multitests
        cin >> T;
    #endif
    while (T--)
        solve();
    return 0;
}