結果
| 問題 |
No.1111 コード進行
|
| コンテスト | |
| ユーザー |
👑  terry_u16
|
| 提出日時 | 2020-07-10 22:05:38 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 615 ms / 2,000 ms |
| コード長 | 26,139 bytes |
| コンパイル時間 | 2,621 ms |
| コンパイル使用メモリ | 126,164 KB |
| 実行使用メモリ | 155,520 KB |
| 最終ジャッジ日時 | 2024-10-11 09:19:18 |
| 合計ジャッジ時間 | 9,307 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 48 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using YukicoderContest256.Extensions;
using YukicoderContest256.Questions;
using YukicoderContest256.Graphs;
namespace YukicoderContest256.Questions
{
public class QuestionE : AtCoderQuestionBase
{
WeightedGraph graph;
Modular[,,] memo;
bool[,,] memorized;
int lastMeasure, chordVariety, maxComplexity;
public override IEnumerable<object> Solve(TextReader inputStream)
{
(lastMeasure, chordVariety, maxComplexity) = inputStream.ReadValue<int, int, int>();
graph = new WeightedGraph(300);
for (int i = 0; i < chordVariety; i++)
{
var (from, to, complexity) = inputStream.ReadValue<int, int, int>();
from--;
to--;
graph.AddEdge(new WeightedEdge(from, to, complexity));
}
memo = new Modular[301, 301, 301];
memorized = new bool[301, 301, 301];
var count = Modular.Zero;
for (int firstChord = 0; firstChord < 300; firstChord++)
{
count += Dfs(firstChord, 1, 0);
}
yield return count;
}
Modular Dfs(int chord, int measure, long complexity)
{
if (measure == lastMeasure)
{
if (complexity == maxComplexity)
{
return Modular.One;
}
else
{
return Modular.Zero;
}
}
else if (complexity > maxComplexity)
{
return Modular.Zero;
}
else if (memorized[chord, measure, complexity])
{
return memo[chord, measure, complexity];
}
else
{
var count = Modular.Zero;
foreach (var chordProgression in graph[chord])
{
count += Dfs(chordProgression.To.Index, measure + 1, complexity + chordProgression.Weight);
}
memorized[chord, measure, complexity] = true;
return memo[chord, measure, complexity] = count;
}
}
public readonly struct Modular : IEquatable<Modular>, IComparable<Modular>
{
private const int DefaultMod = 1000000007;
public int Value { get; }
public static int Mod { get; set; } = DefaultMod;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public Modular(long value)
{
if (unchecked((ulong)value) < unchecked((ulong)Mod))
{
Value = (int)value;
}
else
{
Value = (int)(value % Mod);
if (Value < 0)
{
Value += Mod;
}
}
}
private Modular(int value) => Value = value;
public static Modular Zero => new Modular(0);
public static Modular One => new Modular(1);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static Modular operator +(Modular a, Modular b)
{
var result = a.Value + b.Value;
if (result >= Mod)
{
result -= Mod; // 剰余演算を避ける
}
return new Modular(result);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static Modular operator -(Modular a, Modular b)
{
var result = a.Value - b.Value;
if (result < 0)
{
result += Mod; // 剰余演算を避ける
}
return new Modular(result);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static Modular operator *(Modular a, Modular b) => new Modular((long)a.Value * b.Value);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static Modular operator /(Modular a, Modular b) => a * Pow(b.Value, Mod - 2);
// 需要は不明だけど一応
public static bool operator ==(Modular left, Modular right) => left.Equals(right);
public static bool operator !=(Modular left, Modular right) => !(left == right);
public static bool operator <(Modular left, Modular right) => left.CompareTo(right) < 0;
public static bool operator <=(Modular left, Modular right) => left.CompareTo(right) <= 0;
public static bool operator >(Modular left, Modular right) => left.CompareTo(right) > 0;
public static bool operator >=(Modular left, Modular right) => left.CompareTo(right) >= 0;
public static implicit operator Modular(long a) => new Modular(a);
public static explicit operator int(Modular a) => a.Value;
public static explicit operator long(Modular a) => a.Value;
public static Modular Pow(int a, int n)
{
switch (n)
{
case 0:
return Modular.One;
case 1:
return a;
case int m when m >= 0: // ジャンプテーブル化はできなくなる
var p = Pow(a, m >> 1); // m / 2
return p * p * Pow(a, m & 0x01); // m % 2
default:
throw new ArgumentOutOfRangeException(nameof(n), $"べき指数{nameof(n)}は0以上の整数でなければなりません。");
}
}
private static List<int> _factorialCache;
private static List<int> FactorialCache => _factorialCache ??= new List<int>() { 1 };
private static int[] FactorialInverseCache { get; set; }
const int defaultMaxFactorial = 1000000;
public static Modular Factorial(int n)
{
if (n < 0)
{
throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は0以上の整数でなければなりません。");
}
for (int i = FactorialCache.Count; i <= n; i++) // Countが1（0!までキャッシュ済み）のとき1!～n!まで計算
{
FactorialCache.Add((int)((long)FactorialCache[i - 1] * i % Mod));
}
return new Modular(FactorialCache[n]);
}
public static Modular Permutation(int n, int r)
{
CheckNR(n, r);
return Factorial(n) / Factorial(n - r);
}
public static Modular Combination(int n, int r)
{
CheckNR(n, r);
r = Math.Min(r, n - r);
try
{
return new Modular(FactorialCache[n]) * new Modular(FactorialInverseCache[r]) * new Modular(FactorialInverseCache[n - r]);
}
catch (Exception ex) when (ex is NullReferenceException || ex is ArgumentOutOfRangeException)
{
throw new InvalidOperationException($"{nameof(Combination)}を呼び出す前に{nameof(InitializeCombinationTable)}により前計算を行う必要があります。", ex);
}
}
public static void InitializeCombinationTable(int max = defaultMaxFactorial)
{
Factorial(max);
FactorialInverseCache = new int[max + 1];
var fInv = (Modular.One / Factorial(max)).Value;
FactorialInverseCache[max] = fInv;
for (int i = max - 1; i >= 0; i--)
{
fInv = (int)((long)fInv * (i + 1) % Mod);
FactorialInverseCache[i] = fInv;
}
}
public static Modular CombinationWithRepetition(int n, int r) => Combination(n + r - 1, r);
private static void CheckNR(int n, int r)
{
if (n < 0)
{
throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は0以上の整数でなければなりません。");
}
if (r < 0)
{
throw new ArgumentOutOfRangeException(nameof(r), $"{nameof(r)}は0以上の整数でなければなりません。");
}
if (n < r)
{
throw new ArgumentOutOfRangeException($"{nameof(n)},{nameof(r)}", $"{nameof(r)}は{nameof(n)}以下でなければなりません。");
}
}
public override string ToString() => Value.ToString();
public override bool Equals(object obj) => obj is Modular m ? Equals(m) : false;
public bool Equals([System.Diagnostics.CodeAnalysis.AllowNull] Modular other) => Value == other.Value;
public int CompareTo([System.Diagnostics.CodeAnalysis.AllowNull] Modular other) => Value.CompareTo(other.Value);
public override int GetHashCode() => Value.GetHashCode();
}
}
}
namespace YukicoderContest256
{
class Program
{
static void Main(string[] args)
{
IAtCoderQuestion question = new QuestionE();
var answers = question.Solve(Console.In);
var writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(writer);
foreach (var answer in answers)
{
Console.WriteLine(answer);
}
Console.Out.Flush();
}
}
}
#region Base Class
namespace YukicoderContest256.Questions
{
public interface IAtCoderQuestion
{
IEnumerable<object> Solve(string input);
IEnumerable<object> Solve(TextReader inputStream);
}
public abstract class AtCoderQuestionBase : IAtCoderQuestion
{
public IEnumerable<object> Solve(string input)
{
var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));
var reader = new StreamReader(stream, Encoding.Unicode);
return Solve(reader);
}
public abstract IEnumerable<object> Solve(TextReader inputStream);
}
}
#endregion
#region Graphs
namespace YukicoderContest256.Graphs
{
public interface INode
{
public int Index { get; }
}
public interface IEdge<TNode> where TNode : INode
{
TNode From { get; }
TNode To { get; }
}
public interface IWeightedEdge<TNode> : IEdge<TNode> where TNode : INode
{
long Weight { get; }
}
public interface IGraph<TNode, TEdge> where TEdge : IEdge<TNode> where TNode : INode
{
IEnumerable<TEdge> this[TNode node] { get; }
IEnumerable<TEdge> Edges { get; }
IEnumerable<TNode> Nodes { get; }
int NodeCount { get; }
}
public interface IWeightedGraph<TNode, TEdge> : IGraph<TNode, TEdge> where TEdge : IWeightedEdge<TNode> where TNode : INode { }
[StructLayout(LayoutKind.Auto)]
public readonly struct BasicNode : INode, IEquatable<BasicNode>
{
public int Index { get; }
public BasicNode(int index)
{
Index = index;
}
public override string ToString() => Index.ToString();
public override bool Equals(object obj) => obj is BasicNode node && Equals(node);
public bool Equals(BasicNode other) => Index == other.Index;
public override int GetHashCode() => HashCode.Combine(Index);
public static bool operator ==(BasicNode left, BasicNode right) => left.Equals(right);
public static bool operator !=(BasicNode left, BasicNode right) => !(left == right);
public static implicit operator BasicNode(int value) => new BasicNode(value);
}
[StructLayout(LayoutKind.Auto)]
public readonly struct BasicEdge : IEdge<BasicNode>
{
public BasicNode From { get; }
public BasicNode To { get; }
public BasicEdge(int from, int to)
{
From = from;
To = to;
}
public override string ToString() => $"{From}-->{To}";
}
[StructLayout(LayoutKind.Auto)]
public readonly struct WeightedEdge : IWeightedEdge<BasicNode>
{
public BasicNode From { get; }
public BasicNode To { get; }
public long Weight { get; }
public WeightedEdge(int from, int to) : this(from, to, 1) { }
public WeightedEdge(int from, int to, long weight)
{
From = from;
To = to;
Weight = weight;
}
public override string ToString() => $"{From}--[{Weight}]-->{To}";
}
[StructLayout(LayoutKind.Auto)]
public readonly struct GridNode : INode, IEquatable<GridNode>
{
public int Row { get; }
public int Column { get; }
public int Index { get; }
public GridNode(int row, int column, int width)
{
Row = row;
Column = column;
Index = row * width + column;
}
public override string ToString() => $"({Row}, {Column})";
public override int GetHashCode() => HashCode.Combine(Row, Column, Index);
public override bool Equals(object obj) => obj is GridNode node && Equals(node);
public bool Equals(GridNode other) => Row == other.Row && Column == other.Column && Index == other.Index;
public void Deconstruct(out int row, out int column) { row = Row; column = Column; }
public static bool operator ==(GridNode left, GridNode right) => left.Equals(right);
public static bool operator !=(GridNode left, GridNode right) => !(left == right);
}
[StructLayout(LayoutKind.Auto)]
public readonly struct GridEdge : IEdge<GridNode>
{
public GridNode From { get; }
public GridNode To { get; }
public GridEdge(GridNode from, GridNode to)
{
From = from;
To = to;
}
public override string ToString() => $"({From.Row}, {From.Column})-->({To.Row}, {To.Column})";
}
public class BasicGraph : IGraph<BasicNode, BasicEdge>
{
private readonly List<BasicEdge>[] _edges;
public IEnumerable<BasicEdge> this[BasicNode node] => _edges[node.Index];
public IEnumerable<BasicEdge> Edges => Nodes.SelectMany(node => this[node]);
public IEnumerable<BasicNode> Nodes => Enumerable.Range(0, NodeCount).Select(i => new BasicNode(i));
public int NodeCount { get; }
public BasicGraph(int nodeCount) : this(nodeCount, Enumerable.Empty<BasicEdge>()) { }
public BasicGraph(int nodeCount, IEnumerable<BasicEdge> edges)
{
_edges = Enumerable.Repeat(0, nodeCount).Select(_ => new List<BasicEdge>()).ToArray();
NodeCount = nodeCount;
foreach (var edge in edges)
{
AddEdge(edge);
}
}
public BasicGraph(int nodeCount, IEnumerable<IEnumerable<int>> distances)
{
_edges = new List<BasicEdge>[nodeCount];
int i = 0;
foreach (var row in distances)
{
_edges[i] = new List<BasicEdge>(nodeCount);
int j = 0;
foreach (var distance in row)
{
if (distance == 1)
{
_edges[i].Add(new BasicEdge(i, j++));
}
}
i++;
}
}
public void AddEdge(BasicEdge edge) => _edges[edge.From.Index].Add(edge);
}
public class WeightedGraph : IGraph<BasicNode, WeightedEdge>
{
private readonly List<WeightedEdge>[] _edges;
public IEnumerable<WeightedEdge> this[BasicNode node] => _edges[node.Index];
public IEnumerable<WeightedEdge> Edges => Nodes.SelectMany(node => this[node]);
public IEnumerable<BasicNode> Nodes => Enumerable.Range(0, NodeCount).Select(i => new BasicNode(i));
public int NodeCount { get; }
public WeightedGraph(int nodeCount) : this(nodeCount, Enumerable.Empty<WeightedEdge>()) { }
public WeightedGraph(int nodeCount, IEnumerable<WeightedEdge> edges)
{
_edges = Enumerable.Repeat(0, nodeCount).Select(_ => new List<WeightedEdge>()).ToArray();
NodeCount = nodeCount;
foreach (var edge in edges)
{
AddEdge(edge);
}
}
public WeightedGraph(int nodeCount, IEnumerable<IEnumerable<int>> distances)
{
_edges = new List<WeightedEdge>[nodeCount];
int i = 0;
foreach (var row in distances)
{
_edges[i] = new List<WeightedEdge>(nodeCount);
int j = 0;
foreach (var distance in row)
{
_edges[i].Add(new WeightedEdge(i, j++, distance));
}
i++;
}
}
public void AddEdge(WeightedEdge edge) => _edges[edge.From.Index].Add(edge);
}
}
#endregion
#region Extensions
namespace YukicoderContest256.Extensions
{
public static class SearchExtensions
{
class LowerBoundComparer<T> : IComparer<T> where T : IComparable<T>
{
public int Compare(T x, T y) => 0 <= x.CompareTo(y) ? 1 : -1;
}
class UpperBoundComparer<T> : IComparer<T> where T : IComparable<T>
{
public int Compare(T x, T y) => 0 < x.CompareTo(y) ? 1 : -1;
}
// https://trsing.hatenablog.com/entry/2019/08/27/211038
public static int GetGreaterEqualIndex<T>(this ReadOnlySpan<T> span, T inclusiveMin) where T : IComparable<T> => ~span.BinarySearch(inclusiveMin, new UpperBoundComparer<T>());
public static int GetGreaterThanIndex<T>(this ReadOnlySpan<T> span, T exclusiveMin) where T : IComparable<T> => ~span.BinarySearch(exclusiveMin, new LowerBoundComparer<T>());
public static int GetLessEqualIndex<T>(this ReadOnlySpan<T> span, T inclusiveMax) where T : IComparable<T> => ~span.BinarySearch(inclusiveMax, new LowerBoundComparer<T>()) - 1;
public static int GetLessThanIndex<T>(this ReadOnlySpan<T> span, T exclusiveMax) where T : IComparable<T> => ~span.BinarySearch(exclusiveMax, new UpperBoundComparer<T>()) - 1;
public static int GetGreaterEqualIndex<T>(this Span<T> span, T inclusiveMin) where T : IComparable<T> => ((ReadOnlySpan<T>)span).GetGreaterEqualIndex(inclusiveMin);
public static int GetGreaterThanIndex<T>(this Span<T> span, T exclusiveMin) where T : IComparable<T> => ((ReadOnlySpan<T>)span).GetGreaterThanIndex(exclusiveMin);
public static int GetLessEqualIndex<T>(this Span<T> span, T inclusiveMax) where T : IComparable<T> => ((ReadOnlySpan<T>)span).GetLessEqualIndex(inclusiveMax);
public static int GetLessThanIndex<T>(this Span<T> span, T exclusiveMax) where T : IComparable<T> => ((ReadOnlySpan<T>)span).GetLessThanIndex(exclusiveMax);
public static int BoundaryBinarySearch(Predicate<int> predicate, int ok, int ng)
{
// めぐる式二分探索
while (Math.Abs(ok - ng) > 1)
{
int mid = (ok + ng) / 2;
if (predicate(mid))
{
ok = mid;
}
else
{
ng = mid;
}
}
return ok;
}
public static long BoundaryBinarySearch(Predicate<long> predicate, long ok, long ng)
{
while (Math.Abs(ok - ng) > 1)
{
long mid = (ok + ng) / 2;
if (predicate(mid))
{
ok = mid;
}
else
{
ng = mid;
}
}
return ok;
}
public static double Bisection(Func<double, double> f, double a, double b, double eps = 1e-9)
{
if (f(a) * f(b) >= 0)
{
throw new ArgumentException("f(a)とf(b)は異符号である必要があります。");
}
const int maxLoop = 100;
double mid = (a + b) / 2;
for (int i = 0; i < maxLoop; i++)
{
if (f(a) * f(mid) < 0)
{
b = mid;
}
else
{
a = mid;
}
mid = (a + b) / 2;
if (Math.Abs(b - a) < eps)
{
break;
}
}
return mid;
}
}
public static class StringExtensions
{
public static string Join<T>(this IEnumerable<T> source) => string.Concat(source);
public static string Join<T>(this IEnumerable<T> source, char separator) => string.Join(separator, source);
public static string Join<T>(this IEnumerable<T> source, string separator) => string.Join(separator, source);
}
public static class TextReaderExtensions
{
public static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));
public static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));
public static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));
public static string ReadString(this TextReader reader) => reader.ReadLine();
public static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();
public static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();
public static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();
public static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);
// Supports primitive type only.
public static T1 ReadValue<T1>(this TextReader reader) => (T1)Convert.ChangeType(reader.ReadLine(), typeof(T1));
public static (T1, T2) ReadValue<T1, T2>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
return (v1, v2);
}
public static (T1, T2, T3) ReadValue<T1, T2, T3>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
return (v1, v2, v3);
}
public static (T1, T2, T3, T4) ReadValue<T1, T2, T3, T4>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
return (v1, v2, v3, v4);
}
public static (T1, T2, T3, T4, T5) ReadValue<T1, T2, T3, T4, T5>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
return (v1, v2, v3, v4, v5);
}
public static (T1, T2, T3, T4, T5, T6) ReadValue<T1, T2, T3, T4, T5, T6>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));
return (v1, v2, v3, v4, v5, v6);
}
public static (T1, T2, T3, T4, T5, T6, T7) ReadValue<T1, T2, T3, T4, T5, T6, T7>(this TextReader reader, char separator = ' ')
{
var inputs = ReadStringArray(reader, separator);
var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1));
var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2));
var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3));
var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4));
var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5));
var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6));
var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7));
return (v1, v2, v3, v4, v5, v6, v7);
}
}
}
#endregion