結果
問題 | No.2807 Have Another Go (Easy) |
ユーザー |
|
提出日時 | 2024-07-12 23:09:13 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 2,522 ms / 3,000 ms |
コード長 | 4,741 bytes |
コンパイル時間 | 12,236 ms |
コンパイル使用メモリ | 169,720 KB |
実行使用メモリ | 211,444 KB |
最終ジャッジ日時 | 2024-07-12 23:10:38 |
合計ジャッジ時間 | 83,322 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 46 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (91 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
namespace AtCoder;#nullable enableusing System.Numerics;readonly struct Matrix : IAdditionOperators<Matrix, Matrix, Matrix>, IMultiplyOperators<Matrix, Matrix, 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);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;}}static class Extensions{public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();}class AtCoder{const int Mod = 998244353;object? Solve(){var n = Int();var m = Int();var k = Int();var cz = k.Repeat(Int);var vl = new int[6, 1];vl[0, 0] = 1;var ma = new int[6, 6];for (var i = 0; i < 6; i++){ma[i, 0] = 1;if (i + 1 < 6) ma[i, i + 1] = 1;}var matrix = new Matrix(ma);var vr = new int[6, 1];for (var i = 0; i < 6; i++) vr[i, 0] = 6 - i;var ans = new List<long>();var e = n * m - 1;var mv = (matrix.Power(n) * vl)[0, 0];foreach (var c in cz){var ll = (matrix.Power(c) * vl)[0, 0];var lr = (matrix.Power(e - c) * vr)[0, 0];var rl = (matrix.Power(c + n) * vl)[0, 0];var rr = (matrix.Power(e - (c + n)) * vr)[0, 0];var kns = (ll * lr + rl * rr) % Mod;kns = (kns + Mod - ll * rr % Mod * mv % Mod) % Mod;ans.Add(kns);}Out(ans);return null;}public static void Main() => new AtCoder().Run();public void Run(){var res = Solve();if (res != null){if (res is bool yes) res = yes ? "Yes" : "No";sw.WriteLine(res);}sw.Flush();}string[] input = Array.Empty<string>();int iter = 0;readonly StreamWriter sw = new(Console.OpenStandardOutput()) { AutoFlush = false };string String(){while (iter >= input.Length) (input, iter) = (Console.ReadLine()!.Split(' '), 0);return input[iter++];}T Input<T>() where T : IParsable<T> => T.Parse(String(), null);int Int() => Input<int>();void Out(object? x, string? separator = null){separator ??= Environment.NewLine;if (x is System.Collections.IEnumerable obj and not string){var firstLine = true;foreach (var item in obj){if (!firstLine) sw.Write(separator);firstLine = false;sw.Write(item);}}else sw.Write(x);sw.WriteLine();}}