提出 #19470579

---

ソースコード 拡げる

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

lint h, w, k;
const lint mod = 998244353;
lint two_third;

// a^n mod pを計算　O(log n)
long long pow_mod(long long a, long long n, long long p) {
    if (n == 0) return 1;
    if (n & 1) return pow_mod(a, n - 1, p) * a % p;
    long long temp = pow_mod(a, n / 2, p);
    return temp * temp % p;
}
// Z_pでのaの逆元を計算 O(log p)
// depend:pow_mod
long long inv_mod(long long a, long long p) {
    return pow_mod(a, p - 2, p);
}

bool is_ok(lint x, lint y) {
    return x >= 0 && x < h && y >= 0 && y < w;
}

int main() {
    cin >> h >> w >> k;
    vector<string> s(h, string(w, 'A'));
    for (int i = 0; i < k; i++) {
        lint x, y;
        char c;
        cin >> x >> y >> c;
        x--, y--;
        s[x][y] = c;
    }
    lint two_third = 2 * inv_mod(3, mod);
    vector<vector<lint>> dp(h, vector<lint>(w, 0));
    dp[0][0] = pow_mod(3, h * w - k, mod);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (s[i][j] == 'A') {
                if (is_ok(i + 1, j)) {
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * two_third) % mod;
                }
                if (is_ok(i, j + 1)) {
                    dp[i][j + 1] = (dp[i][j + 1] + dp[i][j] * two_third) % mod;
                }
            }
            if (s[i][j] == 'X' || s[i][j] == 'D') {
                if (is_ok(i + 1, j)) {
                    dp[i + 1][j] = (dp[i + 1][j] + dp[i][j]) % mod;
                }
            }
            if (s[i][j] == 'X' || s[i][j] == 'R') {
                if (is_ok(i, j + 1)) {
                    dp[i][j + 1] = (dp[i][j + 1] + dp[i][j]) % mod;
                }
            }
        }
    }
    cout << dp[h - 1][w - 1] << endl;
}

提出情報

ジャッジ結果