結果
問題 | No.3006 ベイカーの問題 |
ユーザー |
|
提出日時 | 2025-01-17 22:54:31 |
言語 | C# (.NET 8.0.404) |
結果 |
AC
|
実行時間 | 63 ms / 2,000 ms |
コード長 | 4,099 bytes |
コンパイル時間 | 17,969 ms |
コンパイル使用メモリ | 173,384 KB |
実行使用メモリ | 196,764 KB |
最終ジャッジ日時 | 2025-01-17 22:55:03 |
合計ジャッジ時間 | 16,731 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (112 ミリ秒)。 /home/judge/data/code/Main.cs(31,5): warning CS8321: ローカル関数 'Int' は宣言されていますが、一度も使用されていません [/home/judge/data/code/main.csproj] main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
#nullable enableusing System.Numerics;void Solve(){var a = long.Parse(String());var b = long.Parse(String());var n = long.Parse(String());var ma = new[,]{{ a, -5 * b, 0, 0, 0, },{ b, a, 0, 0, 0, },{ 1, 0, 1, 0, 0, },{ 0, 1, 0, 1, 0, },{ 0, 0, 0, 0, 1, },};var v = new[,]{ {a}, {b}, {0}, {0}, {1} };var p = new Matrix(ma).Power(n) * v;Out(p[2, 0] + " " + p[3, 0]);}#regionAtCoderIO _io_;var _backend_ = new StandardIOBackend();_io_ = new(){ Backend = _backend_ };Solve();_backend_.Flush();string String() => _io_.Next();int Int() => int.Parse(String());void Out(object? x, string? sep = null) => _io_.Out(x, sep ?? Environment.NewLine);class AtCoderIO{public required StandardIOBackend Backend { get; init; }Memory<string> _input = Array.Empty<string>();int _iter = 0;public string Next(){while (_iter >= _input.Length) (_input, _iter) = (Backend.ReadLine().Split(' '), 0);return _input.Span[_iter++];}public void Out(object? x, string separator){if (x is System.Collections.IEnumerable obj and not string)x = string.Join(separator, obj.Cast<object>());Backend.WriteLine(x);}}class StandardIOBackend{readonly StreamReader _sr = new(Console.OpenStandardInput());readonly StreamWriter _sw = new(Console.OpenStandardOutput()) { AutoFlush = false };public string ReadLine() => _sr.ReadLine()!;public void WriteLine(object? value) => _sw.WriteLine(value);public void Flush() => _sw.Flush();}#endregionstatic class Extensions{public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();}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(long[,] 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(long[,] 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;}}