結果

問題 No.2807 Have Another Go (Easy)
ユーザー tobisatistobisatis
提出日時 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/

ソースコード

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

namespace AtCoder;
#nullable enable
using 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();
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0