結果
問題 | No.840 ほむほむほむら |
ユーザー | EmKjp |
提出日時 | 2019-06-15 15:47:17 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,655 ms / 4,000 ms |
コード長 | 7,746 bytes |
コンパイル時間 | 5,063 ms |
コンパイル使用メモリ | 113,192 KB |
実行使用メモリ | 28,740 KB |
最終ジャッジ日時 | 2023-08-12 01:02:15 |
合計ジャッジ時間 | 15,855 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 58 ms
20,880 KB |
testcase_01 | AC | 60 ms
20,776 KB |
testcase_02 | AC | 88 ms
20,624 KB |
testcase_03 | AC | 243 ms
21,616 KB |
testcase_04 | AC | 60 ms
22,764 KB |
testcase_05 | AC | 57 ms
20,940 KB |
testcase_06 | AC | 63 ms
18,712 KB |
testcase_07 | AC | 114 ms
20,844 KB |
testcase_08 | AC | 398 ms
22,088 KB |
testcase_09 | AC | 63 ms
20,768 KB |
testcase_10 | AC | 59 ms
22,780 KB |
testcase_11 | AC | 68 ms
20,784 KB |
testcase_12 | AC | 156 ms
21,132 KB |
testcase_13 | AC | 936 ms
24,428 KB |
testcase_14 | AC | 170 ms
21,552 KB |
testcase_15 | AC | 58 ms
22,888 KB |
testcase_16 | AC | 71 ms
20,740 KB |
testcase_17 | AC | 266 ms
22,076 KB |
testcase_18 | AC | 1,189 ms
27,432 KB |
testcase_19 | AC | 1,561 ms
28,740 KB |
testcase_20 | AC | 57 ms
20,772 KB |
testcase_21 | AC | 58 ms
22,748 KB |
testcase_22 | AC | 72 ms
20,732 KB |
testcase_23 | AC | 1,655 ms
25,100 KB |
testcase_24 | AC | 72 ms
20,764 KB |
testcase_25 | AC | 57 ms
20,928 KB |
testcase_26 | AC | 79 ms
20,644 KB |
testcase_27 | AC | 1,404 ms
26,088 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.IO; using System.Collections.Generic; using System.Globalization; using System.Linq; using System.Text; using E = System.Linq.Enumerable; partial class Solver { public void Run() { var N = ni(); var K = ni(); long ans = 0; const int mod = 998244353; var size = K * K * K; var M = new ModMatrix(size, size, mod); Func<int, int, int, int> toInt = (p1, p2, p3) => (p1 % K) * K * K + (p2 % K) * K + (p3 % K); for (int i = 0; i < K; i++) { for (int j = 0; j < K; j++) { for (int k = 0; k < K; k++) { // ほ M[toInt(i + 1, j, k), toInt(i, j, k)]++; // む M[toInt(i, i + j, k), toInt(i, j, k)]++; // ら M[toInt(i, j, j + k), toInt(i, j, k)]++; } } } var B = new ModMatrix(size, 1, mod); B[0, 0] = 1; var R = ModMatrix.Pow(M, N) * B; for (int i = 0; i < K; i++) for (int j = 0; j < K; j++) ans = (ans + R[toInt(i, j, 0), 0]) % mod; cout.WriteLine(ans); } } public class ModMatrix { public int Row { get; private set; } public int Col { get; private set; } public int Mod { get; private set; } private long[] Data; public ModMatrix(int row, int col, int mod) { this.Row = row; this.Col = col; this.Data = new long[Row * Col]; this.Mod = mod; } public ModMatrix(long[,] array, int mod) : this(array.GetLength(0), array.GetLength(1), mod) { int index = 0; for (int i = 0; i < Row; i++) { for (int j = 0; j < Col; j++) { Data[index++] = array[i, j] % mod; } } } public long this[int row, int col] { set { Data[row * Col + col] = value; } get { return Data[row * Col + col]; } } static public ModMatrix UnitMatrix(int n, int mod) { var matrix = new ModMatrix(n, n, mod); for (int i = 0; i < n; i++) { matrix[i, i] = 1; } return matrix; } static public ModMatrix operator +(ModMatrix A, ModMatrix B) { if (A.Mod != B.Mod) throw new InvalidOperationException("A.Mod must be equal to B.Mod"); var C = new ModMatrix(A.Row, A.Col, A.Mod); for (int i = 0; i < C.Data.Length; i++) { C.Data[i] = (A.Data[i] + B.Data[i] + A.Mod) % A.Mod; } return C; } static public ModMatrix operator -(ModMatrix A, ModMatrix B) { if (A.Mod != B.Mod) throw new InvalidOperationException("A.Mod must be equal to B.Mod"); var C = new ModMatrix(A.Row, A.Col, A.Mod); for (int i = 0; i < C.Data.Length; i++) { C.Data[i] = (A.Data[i] - B.Data[i] + A.Mod) % A.Mod; } return C; } static public ModMatrix operator *(ModMatrix A, ModMatrix B) { if (A.Mod != B.Mod) throw new InvalidOperationException("A.Mod must be equal to B.Mod"); var C = new ModMatrix(A.Row, B.Col, A.Mod); for (int i = 0; i < A.Row; i++) { for (int j = 0; j < B.Col; j++) { var val = C[i, j]; for (int k = 0; k < A.Col; k++) val = (val + A[i, k] * B[k, j]) % A.Mod; if (val < 0) val += A.Mod; C[i, j] = val; } } return C; } static public ModMatrix Pow(ModMatrix A, long n) { if (n == 0) return UnitMatrix(A.Row, A.Mod); if (n == 1) return A; ModMatrix result = A.Clone(), t = A.Clone(); n--; while (n > 0) { if ((n & 1) != 0) { result = result * t; } t = t * t; n >>= 1; } return result; } public ModMatrix Clone() { return new ModMatrix(Row, Col, Mod) { Data = Data.Clone() as long[] }; } } // PREWRITEN CODE BEGINS FROM HERE partial class Solver : Scanner { public static void Main(string[] args) { #if LOCAL new Solver(Console.In, Console.Out).Run(); #else Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); new Solver(Console.In, Console.Out).Run(); Console.Out.Flush(); #endif } #pragma warning disable IDE0052 private readonly TextReader cin; private readonly TextWriter cout; #pragma warning restore IDE0052 public Solver(TextReader reader, TextWriter writer) : base(reader) { this.cin = reader; this.cout = writer; } public Solver(string input, TextWriter writer) : this(new StringReader(input), writer) { } #pragma warning disable IDE1006 #pragma warning disable IDE0051 private int ni() { return NextInt(); } private int[] ni(int n) { return NextIntArray(n); } private long nl() { return NextLong(); } private long[] nl(int n) { return NextLongArray(n); } private double nd() { return NextDouble(); } private double[] nd(int n) { return NextDoubleArray(n); } private string ns() { return Next(); } private string[] ns(int n) { return NextArray(n); } #pragma warning restore IDE1006 #pragma warning restore IDE0051 } public static class LinqPadExtension { static public T Dump<T>(this T obj) { #if LOCAL return LINQPad.Extensions.Dump(obj); #else return obj; #endif } } public class Scanner { private readonly TextReader Reader; private readonly Queue<string> TokenQueue = new Queue<string>(); private readonly CultureInfo ci = CultureInfo.InvariantCulture; public Scanner() : this(Console.In) { } public Scanner(TextReader reader) { this.Reader = reader; } public int NextInt() { return int.Parse(Next(), ci); } public long NextLong() { return long.Parse(Next(), ci); } public double NextDouble() { return double.Parse(Next(), ci); } public string[] NextArray(int size) { var array = new string[size]; for (int i = 0; i < size; i++) array[i] = Next(); return array; } public int[] NextIntArray(int size) { var array = new int[size]; for (int i = 0; i < size; i++) array[i] = NextInt(); return array; } public long[] NextLongArray(int size) { var array = new long[size]; for (int i = 0; i < size; i++) array[i] = NextLong(); return array; } public double[] NextDoubleArray(int size) { var array = new double[size]; for (int i = 0; i < size; i++) array[i] = NextDouble(); return array; } public string Next() { if (TokenQueue.Count == 0) { if (!StockTokens()) throw new InvalidOperationException(); } return TokenQueue.Dequeue(); } public bool HasNext() { if (TokenQueue.Count > 0) return true; return StockTokens(); } static readonly char[] _separator = new[] { ' ' }; private bool StockTokens() { while (true) { var line = Reader.ReadLine(); if (line == null) return false; var tokens = line.Split(_separator, StringSplitOptions.RemoveEmptyEntries); if (tokens.Length == 0) continue; foreach (var token in tokens) TokenQueue.Enqueue(token); return true; } } }