結果

問題 No.2838 Diagonals
ユーザー 👑 ygussany
提出日時 2024-08-03 10:55:17
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 1,635 bytes
コンパイル時間 595 ms
コンパイル使用メモリ 32,512 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-08-03 10:55:19
合計ジャッジ時間 2,115 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <stdio.h>
const int Mod = 998244353;
long long div_mod(long long x, long long y, long long z)
{
    if (x % y == 0) return x / y;
    else return (div_mod((1 + x / y) * y - x, (z % y), y) * z + x) / y;
}
long long pow_mod(int n, long long k)
{
    long long N, ans = 1;
    for (N = n; k > 0; k >>= 1, N = N * N % Mod) if (k & 1) ans = ans * N % Mod;
    return ans;
}
int main()
{
    int i, N, M;
    char S[502][502] = {};
    scanf("%d %d", &N, &M);
    for (i = 1; i <= N; i++) scanf("%s", &(S[i][1]));
    
    int j, n = 0, m = 0;
    for (i = 1; i <= N; i++) {
        for (j = 1; j <= M; j++) {
            if (S[i][j] != '#') continue;
            n++;
            if (S[i][j+1] == '#') m++;
            if (S[i+1][j] == '#') m++;
        }
    }
    
    int ii, jj, k = 0, flag[502][502] = {}, q[250001][2], head, tail;
    for (ii = 1; ii <= N; ii++) {
        for (jj = 1; jj <= M; jj++) {
            if (S[ii][jj] != '#' || flag[ii][jj] != 0) continue;
            flag[ii][jj] = ++k;
            q[0][0] = ii;
            q[0][1] = jj;
            for (head = 0, tail = 1; head < tail; head++) {
                i = q[head][0];
                j = q[head][1];
                if (S[i-1][j] == '#' && flag[i-1][j] == 0) {
                    flag[i-1][j] = k;
                    q[tail][0] = i - 1;
                    q[tail++][1] = j;
                }
                if (S[i+1][j] == '#' && flag[i+1][j] == 0) {
                    flag[i+1][j] = k;
                    q[tail][0] = i + 1;
                    q[tail++][1] = j;
                }
                if (S[i][j-1] == '#' && flag[i][j-1] == 0) {
                    flag[i][j-1] = k;
                    q[tail][0] = i;
                    q[tail++][1] = j - 1;
                }
                if (S[i][j+1] == '#' && flag[i][j+1] == 0) {
                    flag[i][j+1] = k;
                    q[tail][0] = i;
                    q[tail++][1] = j + 1;
                }
            }
        }
    }
    printf("%lld\n", div_mod(pow_mod(4, n), pow_mod(2, m + k - n), Mod));
    fflush(stdout);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0