#1173493 (C#) No.3600 Moving Queen Many Times

• 問題: No.3600 Moving Queen Many Times
• ユーザー: tobisatis
• 提出日時: 2026-07-25 00:10:21
• 言語: C# (.NET 10.0.201)
• 結果: AC
• 実行時間: 2,301 ms / 7,000 ms
• コード長: 2,942 bytes
• コンパイル時間: 8,406 ms
• コンパイル使用メモリ: 173,108 KB
• 実行使用メモリ: 204,288 KB
• 最終ジャッジ日時: 2026-07-25 00:10:52
• 合計ジャッジ時間: 28,662 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 75

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (98 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

#nullable enable

#region
var (_input, _iter) = (Array.Empty<string>(), 0);
T I<T>() where T : IParsable<T>
{
    while (_iter >= _input.Length) (_input, _iter) = (Console.ReadLine()!.Trim().Split(' '), 0);
    return T.Parse(_input[_iter++], null);
}
#endregion

const int Mod = 998244353;
static bool R(int x1, int y1, int x2, int y2)
{
    if (x1 == x2 || y1 == y2) return true;
    if (x1 - y1 == x2 - y2) return true;
    if (x1 + y1 == x2 + y2) return true;
    return false;
}

var h = I<int>();
var w = I<int>();
(int, int) D(int z) => int.DivRem(z, w);
int E(int x, int y) => x * w + y;
var s = E(I<int>() - 1, I<int>() - 1);
var g = E(I<int>() - 1, I<int>() - 1);
var k = I<long>();
var m = h * w;
var b = m.ToFlag();

var gaz = new long[m, m];
{
    var az = new long[m, b, m];
    for (var o = 0; o < m; o++)
    {
        az[o, 0, o] = 1;
        for (var i = 0; i < b; i++) for (var j = 0; j < m; j++)
        {
            var (sx, sy) = D(j);
            for (var t = 0; t < m; t++)
            {
                if (j == t || i.OfFlag(t)) continue;
                var (tx, ty) = D(t);
                if (!R(sx, sy, tx, ty)) continue;
                az[o, i.WithFlag(t, true), t] += az[o, i, j];
            }
        }
    }
    for (var i = 0; i < m; i++) for (var j = 0; j < m; j++) gaz[i, j] = az[i, b - 1, j] % Mod;
}

var (kp, kq) = long.DivRem(k, m);
var mns = new long[b, m];
mns[0, s] = 1;
while (kp > 0)
{
    if (kp % 2 != 0)
    {
        var nmns0 = new long[m];
        for (var i = 0; i < m; i++) for (var j = 0; j < m; j++)
        {
            nmns0[j] = (nmns0[j] + mns[0, i] * gaz[i, j]) % Mod;
        }
        for (var i = 0; i < m; i++) mns[0, i] = nmns0[i];
    }
    var ngaz = new long[m, m];
    for (var i = 0; i < m; i++) for (var t = 0; t < m; t++) for (var j = 0; j < m; j++)
    {
        ngaz[i, j] = (ngaz[i, j] + gaz[i, t] * gaz[t, j]) % Mod;
    }
    gaz = ngaz;
    kp >>= 1;
}
for (var lp = 0; lp < kq; lp++)
{
    var nmns = new long[b, m];
    for (var i = 0; i < b; i++) for (var j = 0; j < m; j++)
    {
        if (mns[i, j] == 0) continue;
        var (sx, sy) = D(j);
        for (var t = 0; t < m; t++)
        {
            if (j == t || i.OfFlag(t)) continue;
            var (tx, ty) = D(t);
            if (!R(sx, sy, tx, ty)) continue;
            nmns[i.WithFlag(t, true), t] += mns[i, j];
        }
    }
    for (var i = 0; i < b; i++) for (var j = 0; j < m; j++) nmns[i, j] %= Mod;
    mns = nmns;
}
var ans = 0L;
for (var i = 0; i < b; i++) ans += mns[i, g];
ans %= Mod;
Console.WriteLine(ans);

static class BitExtensions
{
    public static int ToFlag(this int i)
    {
        if (i < 0 || 31 <= i) throw new IndexOutOfRangeException();
        return 1 << i;
    }
    public static bool OfFlag(this int value, int i) => (value & ToFlag(i)) > 0;
    public static int WithFlag(this int value, int i, bool f) => f ? (value | ToFlag(i)) : (value & ~ToFlag(i));
}