結果
| 問題 |
No.1281 Cigarette Distribution
|
| コンテスト | |
| ユーザー |
👑  terry_u16
|
| 提出日時 | 2020-11-06 22:55:09 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 24,724 bytes |
| コンパイル時間 | 2,583 ms |
| コンパイル使用メモリ | 117,120 KB |
| 実行使用メモリ | 22,272 KB |
| 最終ジャッジ日時 | 2024-07-22 13:29:56 |
| 合計ジャッジ時間 | 4,660 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 4 WA * 19 |
コンパイルメッセージ
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 YukicoderContest273.Extensions;
using YukicoderContest273.Questions;
using System.Diagnostics;
using ModInt = YukicoderContest273.Questions.StaticModInt<YukicoderContest273.Questions.Mod1000000007>;
namespace YukicoderContest273.Questions
{
public class QuestionC : AtCoderQuestionBase
{
public override IEnumerable<object> Solve(TextReader inputStream)
{
var (operations, maxBoxes) = inputStream.ReadValue<int, int>();
for (int boxes = 1; boxes <= maxBoxes; boxes++)
{
if (boxes == 1)
{
yield return operations;
}
else if (operations < 2 * boxes - 1)
{
yield return 0;
}
else if (boxes == 2)
{
yield return new ModInt(operations - 2) * new ModInt(2);
}
else
{
var less = (operations - 1) / (boxes - 1);
var more = less + 1;
var moreCount = (operations - 1) - less * (boxes - 1);
var lessCount = (boxes - 1) - moreCount;
yield return new ModInt(more).Pow(moreCount) * new ModInt(less).Pow(lessCount);
}
}
}
}
#region ModInt
/// <summary>
/// コンパイル時に決定する mod を表します。
/// </summary>
/// <example>
/// <code>
/// public readonly struct Mod1000000009 : IStaticMod
/// {
/// public uint Mod => 1000000009;
/// public bool IsPrime => true;
/// }
/// </code>
/// </example>
public interface IStaticMod
{
/// <summary>
/// mod を取得します。
/// </summary>
uint Mod { get; }
/// <summary>
/// mod が素数であるか識別します。
/// </summary>
bool IsPrime { get; }
}
public readonly struct Mod1000000007 : IStaticMod
{
public uint Mod => 1000000007;
public bool IsPrime => true;
}
public readonly struct Mod998244353 : IStaticMod
{
public uint Mod => 998244353;
public bool IsPrime => true;
}
/// <summary>
/// 実行時に決定する mod の ID を表します。
/// </summary>
/// <example>
/// <code>
/// public readonly struct ModID123 : IDynamicModID { }
/// </code>
/// </example>
public interface IDynamicModID { }
public readonly struct ModID0 : IDynamicModID { }
public readonly struct ModID1 : IDynamicModID { }
public readonly struct ModID2 : IDynamicModID { }
/// <summary>
/// 四則演算時に自動で mod を取る整数型。mod の値はコンパイル時に決定している必要があります。
/// </summary>
/// <typeparam name="T">定数 mod を表す構造体</typeparam>
/// <example>
/// <code>
/// using ModInt = AtCoder.StaticModInt<AtCoder.Mod1000000007>;
///
/// void SomeMethod()
/// {
/// var m = new ModInt(1);
/// m -= 2;
/// Console.WriteLine(m); // 1000000006
/// }
/// </code>
/// </example>
public readonly struct StaticModInt<T> : IEquatable<StaticModInt<T>> where T : struct, IStaticMod
{
private readonly uint _v;
/// <summary>
/// 格納されている値を返します。
/// </summary>
public int Value => (int)_v;
/// <summary>
/// mod を返します。
/// </summary>
public static int Mod => (int)default(T).Mod;
public static StaticModInt<T> Zero => new StaticModInt<T>();
public static StaticModInt<T> One => new StaticModInt<T>(1u);
/// <summary>
/// <paramref name="v"/> に対して mod を取らずに StaticModInt<<typeparamref name="T"/>> 型のインスタンスを生成します。
/// </summary>
/// <remarks>
/// <para>定数倍高速化のための関数です。 <paramref name="v"/> に 0 未満または mod 以上の値を入れた場合の挙動は未定義です。</para>
/// <para>制約: 0≤|<paramref name="v"/>|<mod</para>
/// </remarks>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static StaticModInt<T> Raw(int v)
{
var u = unchecked((uint)v);
Debug.Assert(u < Mod);
return new StaticModInt<T>(u);
}
/// <summary>
/// StaticModInt<<typeparamref name="T"/>> 型のインスタンスを生成します。
/// </summary>
/// <remarks>
/// <paramref name="v"/>が 0 未満、もしくは mod 以上の場合、自動で mod を取ります。
/// </remarks>
public StaticModInt(long v) : this(Round(v)) { }
private StaticModInt(uint v) => _v = v;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static uint Round(long v)
{
var x = v % default(T).Mod;
if (x < 0)
{
x += default(T).Mod;
}
return (uint)x;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static StaticModInt<T> operator ++(StaticModInt<T> value)
{
var v = value._v + 1;
if (v == default(T).Mod)
{
v = 0;
}
return new StaticModInt<T>(v);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static StaticModInt<T> operator --(StaticModInt<T> value)
{
var v = value._v;
if (v == 0)
{
v = default(T).Mod;
}
return new StaticModInt<T>(v - 1);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static StaticModInt<T> operator +(StaticModInt<T> lhs, StaticModInt<T> rhs)
{
var v = lhs._v + rhs._v;
if (v >= default(T).Mod)
{
v -= default(T).Mod;
}
return new StaticModInt<T>(v);
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static StaticModInt<T> operator -(StaticModInt<T> lhs, StaticModInt<T> rhs)
{
unchecked
{
var v = lhs._v - rhs._v;
if (v >= default(T).Mod)
{
v += default(T).Mod;
}
return new StaticModInt<T>(v);
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static StaticModInt<T> operator *(StaticModInt<T> lhs, StaticModInt<T> rhs)
{
return new StaticModInt<T>((uint)((ulong)lhs._v * rhs._v % default(T).Mod));
}
/// <summary>
/// 除算を行います。
/// </summary>
/// <remarks>
/// <para>- 制約: <paramref name="rhs"/> に乗法の逆元が存在する。（gcd(<paramref name="rhs"/>, mod) = 1）</para>
/// <para>- 計算量: O(log(mod))</para>
/// </remarks>
public static StaticModInt<T> operator /(StaticModInt<T> lhs, StaticModInt<T> rhs) => lhs * rhs.Inverse();
public static StaticModInt<T> operator +(StaticModInt<T> value) => value;
public static StaticModInt<T> operator -(StaticModInt<T> value) => new StaticModInt<T>() - value;
public static bool operator ==(StaticModInt<T> lhs, StaticModInt<T> rhs) => lhs._v == rhs._v;
public static bool operator !=(StaticModInt<T> lhs, StaticModInt<T> rhs) => lhs._v != rhs._v;
public static implicit operator StaticModInt<T>(int value) => new StaticModInt<T>(value);
public static implicit operator StaticModInt<T>(long value) => new StaticModInt<T>(value);
/// <summary>
/// 自身を x として、x^<paramref name="n"/> を返します。
/// </summary>
/// <remarks>
/// <para>制約: 0≤|<paramref name="n"/>|</para>
/// <para>計算量: O(log(<paramref name="n"/>))</para>
/// </remarks>
public StaticModInt<T> Pow(long n)
{
Debug.Assert(0 <= n);
var x = this;
var r = Raw(1);
while (n > 0)
{
if ((n & 1) > 0)
{
r *= x;
}
x *= x;
n >>= 1;
}
return r;
}
/// <summary>
/// 自身を x として、 xy≡1 なる y を返します。
/// </summary>
/// <remarks>
/// <para>制約: gcd(x, mod) = 1</para>
/// </remarks>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public StaticModInt<T> Inverse()
{
return Pow(default(T).Mod - 2);
}
public override string ToString() => _v.ToString();
public override bool Equals(object obj) => obj is StaticModInt<T> && Equals((StaticModInt<T>)obj);
public bool Equals(StaticModInt<T> other) => Value == other.Value;
public override int GetHashCode() => _v.GetHashCode();
}
public class ModCombination<T> where T : struct, IStaticMod
{
readonly StaticModInt<T>[] _factorials;
readonly StaticModInt<T>[] _invFactorials;
public ModCombination(int max = 1000000)
{
if (max >= default(T).Mod)
{
ThrowArgumentOutOfRangeException();
}
_factorials = new StaticModInt<T>[max + 1];
_invFactorials = new StaticModInt<T>[max + 1];
_factorials[0] = _factorials[1] = StaticModInt<T>.Raw(1);
_invFactorials[0] = _invFactorials[1] = StaticModInt<T>.Raw(1);
for (int i = 2; i < _factorials.Length; i++)
{
_factorials[i] = _factorials[i - 1] * StaticModInt<T>.Raw(i);
}
_invFactorials[^1] = _factorials[^1].Inverse();
for (int i = _invFactorials.Length - 2; i >= 0; i--)
{
_invFactorials[i] = _invFactorials[i + 1] * StaticModInt<T>.Raw(i + 1);
}
}
public StaticModInt<T> Factorial(int n) => _factorials[n];
public StaticModInt<T> Permutation(int n, int k) => _factorials[n] * _invFactorials[n - k];
public StaticModInt<T> Combination(int n, int k) => _factorials[n] * _invFactorials[k] * _invFactorials[n - k];
public StaticModInt<T> CombinationWithRepetition(int n, int k) => Combination(n + k - 1, k);
public void ThrowArgumentOutOfRangeException() => throw new ArgumentOutOfRangeException();
}
#endregion
}
namespace YukicoderContest273
{
class Program
{
static void Main(string[] args)
{
IAtCoderQuestion question = new QuestionC();
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 YukicoderContest273.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 Extensions
namespace YukicoderContest273.Extensions
{
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);
}
public static (T1, T2, T3, T4, T5, T6, T7, T8) ReadValue<T1, T2, T3, T4, T5, T6, T7, T8>(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));
var v8 = (T8)Convert.ChangeType(inputs[7], typeof(T8));
return (v1, v2, v3, v4, v5, v6, v7, v8);
}
}
}
#endregion
namespace YukicoderContest273.Graphs
{
public interface IEdge
{
int To { get; }
}
public interface IWeightedEdge : IEdge
{
long Weight { get; }
}
public interface IGraph<TEdge> where TEdge : IEdge
{
List<TEdge> this[int node] { get; }
int NodeCount { get; }
}
public interface IWeightedGraph<TEdge> : IGraph<TEdge> where TEdge : IWeightedEdge { }
public readonly struct BasicEdge : IEdge
{
public int To { get; }
public BasicEdge(int to)
{
To = to;
}
public override string ToString() => To.ToString();
public static implicit operator BasicEdge(int edge) => new BasicEdge(edge);
public static implicit operator int(BasicEdge edge) => edge.To;
}
[StructLayout(LayoutKind.Auto)]
public readonly struct WeightedEdge : IWeightedEdge
{
public int To { get; }
public long Weight { get; }
public WeightedEdge(int to) : this(to, 1) { }
public WeightedEdge(int to, long weight)
{
To = to;
Weight = weight;
}
public override string ToString() => $"[{Weight}]-->{To}";
public void Deconstruct(out int to, out long weight) => (to, weight) = (To, Weight);
}
public class WeightedGraph : IGraph<WeightedEdge>
{
private readonly List<List<WeightedEdge>> _edges;
public List<WeightedEdge> this[int node] => _edges[node];
public int NodeCount => _edges.Count;
public WeightedGraph(int nodeCount)
{
_edges = new List<List<WeightedEdge>>(nodeCount);
for (int i = 0; i < nodeCount; i++)
{
_edges.Add(new List<WeightedEdge>());
}
}
public void AddEdge(int from, int to, long weight) => _edges[from].Add(new WeightedEdge(to, weight));
public void AddNode() => _edges.Add(new List<WeightedEdge>());
}
public class PriorityQueue<T> : IEnumerable<T> where T : IComparable<T>
{
private List<T> _heap = new List<T>();
private readonly int _reverseFactor;
public int Count => _heap.Count;
public bool IsDescending => _reverseFactor == 1;
public PriorityQueue(bool descending) : this(descending, null) { }
public PriorityQueue(bool descending, IEnumerable<T> collection)
{
_reverseFactor = descending ? 1 : -1;
_heap = new List<T>();
if (collection != null)
{
foreach (var item in collection)
{
Enqueue(item);
}
}
}
public void Enqueue(T item)
{
_heap.Add(item);
UpHeap();
}
public T Dequeue()
{
var item = _heap[0];
DownHeap();
return item;
}
public T Peek() => _heap[0];
private void UpHeap()
{
var child = Count - 1;
while (child > 0)
{
int parent = (child - 1) / 2;
if (Compare(_heap[child], _heap[parent]) > 0)
{
SwapAt(child, parent);
child = parent;
}
else
{
break;
}
}
}
private void DownHeap()
{
_heap[0] = _heap[Count - 1];
_heap.RemoveAt(Count - 1);
var parent = 0;
while (true)
{
var leftChild = 2 * parent + 1;
if (leftChild > Count - 1)
{
break;
}
var target = (leftChild < Count - 1) && (Compare(_heap[leftChild], _heap[leftChild + 1]) < 0) ? leftChild + 1 : leftChild;
if (Compare(_heap[parent], _heap[target]) < 0)
{
SwapAt(parent, target);
}
else
{
break;
}
parent = target;
}
}
private int Compare(T a, T b) => _reverseFactor * a.CompareTo(b);
private void SwapAt(int n, int m) => (_heap[n], _heap[m]) = (_heap[m], _heap[n]);
public IEnumerator<T> GetEnumerator()
{
var copy = new List<T>(_heap);
try
{
while (Count > 0)
{
yield return Dequeue();
}
}
finally
{
_heap = copy;
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() => GetEnumerator();
}
namespace Algorithms
{
public class Dijkstra
{
private readonly WeightedGraph _graph;
public Dijkstra(WeightedGraph graph)
{
_graph = graph;
}
public long[] GetDistancesFrom(int startNode)
{
const long Inf = 1L << 60;
var distances = Enumerable.Repeat(Inf, _graph.NodeCount).ToArray();
distances[startNode] = 0;
var todo = new PriorityQueue<State>(false);
todo.Enqueue(new State(startNode, 0));
while (todo.Count > 0)
{
var current = todo.Dequeue();
if (current.Distance > distances[current.Node])
{
continue;
}
for (int i = 0; i < _graph[current.Node].Count; i++)
{
var edge = _graph[current.Node][i];
var nextDistance = current.Distance + edge.Weight;
if (distances[edge.To] > nextDistance)
{
distances[edge.To] = nextDistance;
todo.Enqueue(new State(edge.To, nextDistance));
}
}
}
return distances;
}
private readonly struct State : IComparable<State>
{
public int Node { get; }
public long Distance { get; }
public State(int node, long distance)
{
Node = node;
Distance = distance;
}
public int CompareTo(State other) => Distance.CompareTo(other.Distance);
public void Deconstruct(out int node, out long distance) => (node, distance) = (Node, Distance);
}
}
}
}