結果

問題 No.3175 転移迷宮 (Easy)
ユーザー t98slider
提出日時 2025-02-18 02:13:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 143 ms / 3,000 ms
コード長 1,567 bytes
コンパイル時間 4,618 ms
コンパイル使用メモリ 253,348 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2025-02-20 21:00:59
合計ジャッジ時間 9,643 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using mint = atcoder::modint998244353;

void solve(){
    // 入力を受け取る
    int N, K;
    cin >> N >> K;

    // 行列を生成 (拡大係数行列として扱うために N x (N+1) にしています)
    vector A(N, valarray<mint>(N + 1));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if(abs(i - j) <= K) A[i][j] = (i == j ? 2 * K : -1);
        }
    }
    // 右辺の値を代入
    for(int i = 0; i < N; i++) A[i][N] = 2 * K + 1;

    // ガウスの消去法の実行
    int rank = 0;
    for (int j = 0; j < N; j++) {
#if 1 // 一応いれていますが、今回の問題に限って言えばpivotの処理は不要です。
        int pivot = -1;
        for (int i = rank; i < N; i++) {
            if(A[i][j] != 0){
                pivot = i;
                break;
            }
        }
        if (pivot == -1) continue;
        swap(A[pivot], A[rank]);
#endif
        // A[rank][j] を 1 にする処理
        mint div = A[rank][j].inv();
        A[rank] *= div;

        // A[i][j] が非ゼロの成分を消去しにいく
        for (int i = 0; i < N; i++) {
            if (i == rank) continue;
            if (A[i][j] != 0) A[i] -= A[i][j] * A[rank];
        }
        rank++;
    }
    // 答えを出力
    for(int i = 0; i < N; i++){
        cout << A[i][N].val() << (i + 1 == N ? '\n' : ' ');
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) solve();
}
0