結果
問題 | No.840 ほむほむほむら |
ユーザー |
![]() |
提出日時 | 2019-03-29 04:25:56 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,110 bytes |
コンパイル時間 | 977 ms |
コンパイル使用メモリ | 113,876 KB |
実行使用メモリ | 30,812 KB |
最終ジャッジ日時 | 2024-11-06 08:24:33 |
合計ジャッジ時間 | 11,778 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 8 WA * 17 |
コンパイルメッセージ
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.Linq; using System.Collections; using System.Collections.Generic; using System.Text; using System.Numerics; using System.Threading.Tasks; using System.Text.RegularExpressions; using static System.Math; using Debug = System.Diagnostics.Debug; using LayoutKind = System.Runtime.InteropServices.LayoutKind; static class P { static void Main() { //matrix[i,j]:vector[i]の要素が1であればi行目のj要素に乗算が行われ、そこに遷移する var nk = Console.ReadLine().Split().Select(int.Parse).ToArray(); int n = nk[0]; int k = nk[1]; ModMatrix matrix = new ModMatrix(k * k * k, k * k * k); //k=2の時 // a : 01010101 // ab : 00110011 //abc : 00001111 for (int i = 0; i < matrix.Height; i++) { int val = i; int aCount = val % k; val /= k; int abCount = val % k; val /= k; int abcCount = val % k; int newACount, newABCount, newABCCount; //aが追加された時 newACount = (aCount + 1) % k; newABCount = abCount; newABCCount = abcCount; matrix[i, (newABCCount * k + newABCount) * k + newACount] += 1; //bが追加された時 newACount = aCount; newABCount = (abCount + aCount) % k; newABCCount = abcCount; matrix[i, (newABCCount * k + newABCount) * k + newACount] += 1; //cが追加された時 newACount = aCount; newABCount = abCount; newABCCount = (abcCount + abCount) % k; matrix[i, (newABCCount * k + newABCount) * k + newACount] += 1; } ModMatrix res = new ModMatrix(1, k * k * k); res[0, 0] = 1; long pow = n; while (n > 0) { if ((n & 1) == 1) res *= matrix; matrix *= matrix; n >>= 1; } long resSum = 0; for (int i = 0; i < k * k; i++) resSum += res[0, i]; Console.WriteLine(resSum % 1000000007); } } class ModMatrix { const int MOD = 1000000007; public int Height { get; private set; } public int Width { get; private set; } long[,] data; public ModMatrix(int height, int width) { data = new long[height, width]; Height = height; Width = width; } public long this[int i, int j] { get => data[i, j]; set => data[i, j] = value; } public static ModMatrix Multiple(ModMatrix a, ModMatrix b) { Debug.Assert(a.Width == b.Height); var res = new ModMatrix(a.Height, b.Width); for (int i = 0; i < a.Height; i++) for (int j = 0; j < b.Width; j++) for (int k = 0; k < a.Width; k++) { res[i, j] += a[i, k] * b[k, j]; res[i, j] %= MOD; } return res; } public static ModMatrix operator *(ModMatrix a, ModMatrix b) => Multiple(a, b); }