結果
| 問題 | No.1073 無限すごろく |
| ユーザー |
 fairy_lettuce
|
| 提出日時 | 2020-06-05 23:02:18 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 6,803 bytes |
| コンパイル時間 | 2,478 ms |
| コンパイル使用メモリ | 117,128 KB |
| 実行使用メモリ | 667,680 KB |
| 最終ジャッジ日時 | 2024-12-17 17:29:25 |
| 合計ジャッジ時間 | 33,567 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 MLE * 1 |
| other | AC * 12 TLE * 9 MLE * 9 |
コンパイルメッセージ
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.Linq;using System.Text;using System.Threading.Tasks;namespace AtCoder.Contest.D{static class Program{public static void Main(string[] args){var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };Console.SetOut(sw);var cin = new Scanner();long n = cin.NextLong();var p = new List<ModInt>();p.Add(1);ModInt inv = ModInt.Inverse(6);var vec = new Matrix(6, 1);var t = new Matrix(6, 6);vec[0, 0] = 1;vec[1, 0] = 166666668;vec[2, 0] = 194444446;vec[3, 0] = 893518525;vec[4, 0] = 209104940;vec[5, 0] = 577289099;for (int i = 0; i < 6; i++){for (int j = 0; j < 6; j++){if(i != 5){if (i == j - 1) t[i, j] = 1;else t[i, j] = 0;}else{t[i, j] = inv;}}}if (n < 6) Console.WriteLine(vec[(int)n, 0]);else{var ans = Matrix.Pow(t, n - 5) * vec;Console.WriteLine(ans[5, 0]);}var aa = new List<ModInt>();for (int i = 0; i < 6; i++){aa.Add(vec[i, 0]);}for (int i = 6; i <= n; i++){aa.Add((aa[i - 1] + aa[i - 2] + aa[i - 3] + aa[i - 4] + aa[i - 5] + aa[i - 6]) * inv);}Console.Out.Flush();}}public class Matrix{int row, col;public ModInt[] mat;/// <summary>/// <paramref name="r"/> 行 <paramref name="c"/> 列目の要素へのアクセスを提供します。/// </summary>/// <param name="r">行の番号</param>/// <param name="c">列の番号</param>public ModInt this[int r, int c]{get { return mat[r * col + c]; }set { mat[r * col + c] = value; }}public Matrix(int r, int c){row = r; col = c;mat = new ModInt[row * col];}public static Matrix operator *(Matrix l, Matrix r){System.Diagnostics.Debug.Assert(l.col == r.row);var ret = new Matrix(l.row, r.col);for (int i = 0; i < l.row; i++)for (int k = 0; k < l.col; k++)for (int j = 0; j < r.col; j++)ret.mat[i * r.col + j] = (ret.mat[i * r.col + j] + l.mat[i * l.col + k] * r.mat[k * r.col + j]);return ret;}/// <summary>/// <paramref name="m"/>^<paramref name="n"/> を O(<paramref name="m"/>^3 log <paramref name="n"/>) で計算します。/// </summary>public static Matrix Pow(Matrix m, long n){var ret = new Matrix(m.row, m.col);for (int i = 0; i < m.row; i++)ret.mat[i * m.col + i] = 1;for (; n > 0; m *= m, n >>= 1)if ((n & 1) == 1)ret = ret * m;return ret;}public ModInt[][] Items{get{var a = new ModInt[row][];for (int i = 0; i < row; i++){a[i] = new ModInt[col];for (int j = 0; j < col; j++)a[i][j] = mat[i * col + j];}return a;}}}public struct ModInt : IComparable<ModInt>, IEquatable<ModInt>{public static long MOD = 1000000007;private readonly long num;public ModInt(long n) { num = n; }public override string ToString() => num.ToString();public static ModInt operator +(ModInt l, ModInt r){long x = l.num + r.num;if (x >= MOD) x -= MOD;return new ModInt(x);}public static ModInt operator -(ModInt l, ModInt r){long x = l.num - r.num;if (x < 0) x += MOD;return new ModInt(x);}public static ModInt operator *(ModInt l, ModInt r) => new ModInt((l.num * r.num) % MOD);public static ModInt operator /(ModInt l, ModInt r) => l * r.Inverse();public static ModInt operator ++(ModInt x){var tmp = x + new ModInt(1);return tmp;}public static ModInt operator --(ModInt x){var tmp = x - new ModInt(1);return tmp;}public static bool operator >(ModInt l, ModInt r) => l.CompareTo(r) > 0;public static bool operator <(ModInt l, ModInt r) => l.CompareTo(r) < 0;public static bool operator >=(ModInt l, ModInt r) => l.CompareTo(r) >= 0;public static bool operator <=(ModInt l, ModInt r) => l.CompareTo(r) <= 0;public static bool operator ==(ModInt l, ModInt r) => l.Equals(r);public static bool operator !=(ModInt l, ModInt r) => !l.Equals(r);public static implicit operator long(ModInt x) => x.num;public static implicit operator ModInt(long n){n %= MOD;if (n < 0) n += MOD;return new ModInt(n);}public ModInt Inverse() => Inverse(this, MOD);public static ModInt Inverse(ModInt x) => Inverse(x.num, MOD);public static long Inverse(long x, long m){if (x % m == 0) throw new DivideByZeroException();long a = x, b = m, u = 1, v = 0;while (b > 0){long t = a / b;a -= t * b;long p = a; a = b; b = p; // swap(a, b);u -= t * v;p = u; u = v; v = p; // swap(u, v);}u %= m;if (u < 0) u += m;return u;}public static ModInt Pow(ModInt x, long n) => Pow(x.num, n);public static ModInt Pow(long x, long n){if (n == 0) return x;long now = 1;for (n %= MOD - 1; n > 0; n /= 2, x = x * x % MOD){if (n % 2 == 1) now = now * x % MOD;}return new ModInt(now);}public int CompareTo(ModInt x){if (num == x.num) return 0;if (num > x.num) return 1;return -1;}public bool Equals(ModInt x) => num == x.num;public override bool Equals(object obj) => obj is ModInt m && num == m.num;public override int GetHashCode(){return HashCode.Combine(num);}}class Scanner{string[] s;int i;char[] cs = new char[] { ' ' };public Scanner(){s = new string[0];i = 0;}public string Next(){if (i < s.Length) return s[i++];string st = Console.ReadLine();while (st == "") st = Console.ReadLine();s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);if (s.Length == 0) return Next();i = 0;return s[i++];}public int NextInt(){return int.Parse(Next());}public int[] ArrayInt(int N, int add = 0){int[] Array = new int[N];for (int i = 0; i < N; i++){Array[i] = NextInt() + add;}return Array;}public long NextLong(){return long.Parse(Next());}public long[] ArrayLong(int N, long add = 0){long[] Array = new long[N];for (int i = 0; i < N; i++){Array[i] = NextLong() + add;}return Array;}public double NextDouble(){return double.Parse(Next());}public double[] ArrayDouble(int N, double add = 0){double[] Array = new double[N];for (int i = 0; i < N; i++){Array[i] = NextDouble() + add;}return Array;}}}