結果

問題 No.3600 Moving Queen Many Times
コンテスト
ユーザー tobisatis
提出日時 2026-07-25 00:00:31
言語 C#
(.NET 10.0.201)
コンパイル:
dotnet_c
実行:
/usr/bin/dotnet_wrap
結果
TLE  
実行時間 -
コード長 3,174 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,847 ms
コンパイル使用メモリ 174,388 KB
実行使用メモリ 549,424 KB
最終ジャッジ日時 2026-07-25 00:00:53
合計ジャッジ時間 19,011 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other -- * 75
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (87 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

diff #
raw source code 

#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 lp = 0; lp < m; lp++)
        {
            var naz = new long[b, m];
            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;
                    naz[i.WithFlag(t, true), t] += az[o, i, j];
                }
            }
            for (var i = 0; i < b; i++) for (var j = 0; j < m; j++) az[o, i, j] = naz[i, j] % Mod;
        }
    }
    for (var i = 0; i < m; i++) for (var j = 0; j < m; j++) gaz[i, j] = az[i, b - 1, j];
}

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));
}
0