#1178207 (C#) No.3635 Probability trip

• 問題: No.3635 Probability trip
• ユーザー: tobisatis
• 提出日時: 2026-08-21 22:28:01
• 言語: C# (.NET 10.0.201)
• 結果: AC
• 実行時間: 140 ms / 2,000 ms
• コード長: 3,564 bytes
• コンパイル時間: 13,739 ms
• コンパイル使用メモリ: 173,436 KB
• 実行使用メモリ: 199,052 KB
• 最終ジャッジ日時: 2026-08-21 22:28:22
• 合計ジャッジ時間: 19,260 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (102 ミリ秒)。
  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

var n = I<int>();
var m = I<int>();
var g = Enumerable.Range(0, n).Select(_ => new List<int>()).ToArray();
for (var i = 0; i < m; i++)
{
    var u = I<int>() - 1;
    var v = I<int>() - 1;
    g[u].Add(v);
    g[v].Add(u);
}
var s = I<long>();
var t = I<long>();
var a = I<int>() - 1;
var b = I<int>() - 1;

var invz = new long[n + 1];
for (var i = 1; i <= n; i++) invz[i] = Power(i, Matrix.p - 2);
var matrix = new Matrix(new int[n, n]);
for (var i = 0; i < n; i++)
{
    var q = invz[g[i].Count];
    foreach (var j in g[i]) matrix[i, j] = q;
}
long F(long tl, int vl, long tr, int vr)
{
    var v = new Matrix(new int[1, n]);
    v[0, vl] = 1;
    v *= matrix.Power(tr - tl);
    return v[0, vr];
}
var ap = F(1, 0, t, b) * F(t, b, s, a) % Matrix.p;
var aq = F(1, 0, s, a);
var ans = ap * Power(aq, Matrix.p - 2) % Matrix.p;
Console.WriteLine(ans);

static long Power(long v, long p)
{
    var (res, k) = (1L, v);
    while (p > 0)
    {
        if ((p & 1) > 0) res = res * k % Matrix.p;
        k = k * k % Matrix.p;
        p >>= 1;
    }
    return res;
}
readonly struct Matrix
{
    long[,] V { get; init; }
    public long this[int i, int j] { get => V[i, j]; set { V[i, j] = Mod(value); } }
    public int X => V.GetLength(0);
    public int Y => V.GetLength(1);

    public const int p = 998244353;
    static long Mod(long v)
    {
        var res = v % p;
        if (res < 0) res += p;
        return res;
    }

    public Matrix(int[,] matrix)
    {
        var (x, y) = (matrix.GetLength(0), matrix.GetLength(1));
        var v = new long[x, y];
        for (var i = 0; i < x; i++) for (var j = 0; j < y; j++) v[i, j] = Mod(matrix[i, j]);
        V = v;
    }
    public static implicit operator Matrix(int[,] matrix) => new(matrix);
    static Matrix With(long[,] matrix) => new(){ V = matrix };

    public static Matrix IdentityMatrix(int size)
    {
        var v = new long[size, size];
        for (var i = 0; i < size; i++) v[i, i] = 1;
        return With(v);
    }

    public static Matrix operator +(Matrix a, Matrix b)
    {
        var (v, va, vb, x, y) = (new long[a.X, a.Y], a.V, b.V, a.X, a.Y);
        for (var i = 0; i < x; i++) for (var j = 0; j < y; j++)
        {
            var sum = va[i, j] + vb[i, j];
            if (sum > p) sum -= p;
            v[i, j] = sum;
        }
        return With(v);
    }

    public static Matrix operator *(Matrix a, Matrix b)
    {
        var (v, va, vb, x, y, z) = (new long[a.X, b.Y], a.V, b.V, a.X, b.Y, a.Y);
        for (var i = 0; i < x; i++) for (var k = 0; k < z; k++)
        {
            var c = va[i, k];
            if (c != 0) for (var j = 0; j < y; j++) v[i, j] += vb[k, j] * c % p;
        }
        for (var i = 0; i < x; i++) for (var j = 0; j < y; j++) v[i, j] = Mod(v[i, j]);
        return With(v);
    }

    public static Matrix operator *(Matrix a, long k)
    {
        var (v, va, x, y) = (new long[a.X, a.Y], a.V, a.X, a.Y);
        for (var i = 0; i < x; i++) for (var j = 0; j < y; j++) v[i, j] = va[i, j] * k % p;
        return With(v);
    }

    public Matrix Power(long k)
    {
        var c = IdentityMatrix(X);
        var c2 = this;
        while (k > 0)
        {
            if ((k & 1) > 0) c *= c2;
            c2 *= c2;
            k >>= 1;
        }
        return c;
    }
}