結果

問題 No.3006 ベイカーの問題
ユーザー tobisatistobisatis
提出日時 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/

ソースコード

diff #
プレゼンテーションモードにする

#nullable enable
using 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]);
}
#region
AtCoderIO _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();
}
#endregion
static 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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0