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; namespace YukicoderContest273.Questions { public class QuestionC : AtCoderQuestionBase { public override IEnumerable Solve(TextReader inputStream) { var (operations, maxBoxes) = inputStream.ReadValue(); 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) { if (operations % 2 == 0) { yield return new ModInt(operations / 2) * new ModInt(operations / 2); } else { yield return new ModInt(operations / 2) * new ModInt(operations / 2 + 1); } } 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 /// /// コンパイル時に決定する mod を表します。 /// /// /// /// public readonly struct Mod1000000009 : IStaticMod /// { /// public uint Mod => 1000000009; /// public bool IsPrime => true; /// } /// /// public interface IStaticMod { /// /// mod を取得します。 /// uint Mod { get; } /// /// mod が素数であるか識別します。 /// 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; } /// /// 実行時に決定する mod の ID を表します。 /// /// /// /// public readonly struct ModID123 : IDynamicModID { } /// /// public interface IDynamicModID { } public readonly struct ModID0 : IDynamicModID { } public readonly struct ModID1 : IDynamicModID { } public readonly struct ModID2 : IDynamicModID { } /// /// 四則演算時に自動で mod を取る整数型。mod の値はコンパイル時に決定している必要があります。 /// /// 定数 mod を表す構造体 /// /// /// using ModInt = AtCoder.StaticModInt<AtCoder.Mod1000000007>; /// /// void SomeMethod() /// { /// var m = new ModInt(1); /// m -= 2; /// Console.WriteLine(m); // 1000000006 /// } /// /// public readonly struct StaticModInt : IEquatable> where T : struct, IStaticMod { private readonly uint _v; /// /// 格納されている値を返します。 /// public int Value => (int)_v; /// /// mod を返します。 /// public static int Mod => (int)default(T).Mod; public static StaticModInt Zero => new StaticModInt(); public static StaticModInt One => new StaticModInt(1u); /// /// に対して mod を取らずに StaticModInt<> 型のインスタンスを生成します。 /// /// /// 定数倍高速化のための関数です。 に 0 未満または mod 以上の値を入れた場合の挙動は未定義です。 /// 制約: 0≤||<mod /// [MethodImpl(MethodImplOptions.AggressiveInlining)] public static StaticModInt Raw(int v) { var u = unchecked((uint)v); Debug.Assert(u < Mod); return new StaticModInt(u); } /// /// StaticModInt<> 型のインスタンスを生成します。 /// /// /// が 0 未満、もしくは mod 以上の場合、自動で mod を取ります。 /// 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 operator ++(StaticModInt value) { var v = value._v + 1; if (v == default(T).Mod) { v = 0; } return new StaticModInt(v); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static StaticModInt operator --(StaticModInt value) { var v = value._v; if (v == 0) { v = default(T).Mod; } return new StaticModInt(v - 1); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static StaticModInt operator +(StaticModInt lhs, StaticModInt rhs) { var v = lhs._v + rhs._v; if (v >= default(T).Mod) { v -= default(T).Mod; } return new StaticModInt(v); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static StaticModInt operator -(StaticModInt lhs, StaticModInt rhs) { unchecked { var v = lhs._v - rhs._v; if (v >= default(T).Mod) { v += default(T).Mod; } return new StaticModInt(v); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static StaticModInt operator *(StaticModInt lhs, StaticModInt rhs) { return new StaticModInt((uint)((ulong)lhs._v * rhs._v % default(T).Mod)); } /// /// 除算を行います。 /// /// /// - 制約: に乗法の逆元が存在する。(gcd(, mod) = 1) /// - 計算量: O(log(mod)) /// public static StaticModInt operator /(StaticModInt lhs, StaticModInt rhs) => lhs * rhs.Inverse(); public static StaticModInt operator +(StaticModInt value) => value; public static StaticModInt operator -(StaticModInt value) => new StaticModInt() - value; public static bool operator ==(StaticModInt lhs, StaticModInt rhs) => lhs._v == rhs._v; public static bool operator !=(StaticModInt lhs, StaticModInt rhs) => lhs._v != rhs._v; public static implicit operator StaticModInt(int value) => new StaticModInt(value); public static implicit operator StaticModInt(long value) => new StaticModInt(value); /// /// 自身を x として、x^ を返します。 /// /// /// 制約: 0≤|| /// 計算量: O(log()) /// public StaticModInt 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; } /// /// 自身を x として、 xy≡1 なる y を返します。 /// /// /// 制約: gcd(x, mod) = 1 /// [MethodImpl(MethodImplOptions.AggressiveInlining)] public StaticModInt Inverse() { return Pow(default(T).Mod - 2); } public override string ToString() => _v.ToString(); public override bool Equals(object obj) => obj is StaticModInt && Equals((StaticModInt)obj); public bool Equals(StaticModInt other) => Value == other.Value; public override int GetHashCode() => _v.GetHashCode(); } public class ModCombination where T : struct, IStaticMod { readonly StaticModInt[] _factorials; readonly StaticModInt[] _invFactorials; public ModCombination(int max = 1000000) { if (max >= default(T).Mod) { ThrowArgumentOutOfRangeException(); } _factorials = new StaticModInt[max + 1]; _invFactorials = new StaticModInt[max + 1]; _factorials[0] = _factorials[1] = StaticModInt.Raw(1); _invFactorials[0] = _invFactorials[1] = StaticModInt.Raw(1); for (int i = 2; i < _factorials.Length; i++) { _factorials[i] = _factorials[i - 1] * StaticModInt.Raw(i); } _invFactorials[^1] = _factorials[^1].Inverse(); for (int i = _invFactorials.Length - 2; i >= 0; i--) { _invFactorials[i] = _invFactorials[i + 1] * StaticModInt.Raw(i + 1); } } public StaticModInt Factorial(int n) => _factorials[n]; public StaticModInt Permutation(int n, int k) => _factorials[n] * _invFactorials[n - k]; public StaticModInt Combination(int n, int k) => _factorials[n] * _invFactorials[k] * _invFactorials[n - k]; public StaticModInt 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 Solve(string input); IEnumerable Solve(TextReader inputStream); } public abstract class AtCoderQuestionBase : IAtCoderQuestion { public IEnumerable Solve(string input) { var stream = new MemoryStream(Encoding.Unicode.GetBytes(input)); var reader = new StreamReader(stream, Encoding.Unicode); return Solve(reader); } public abstract IEnumerable Solve(TextReader inputStream); } } #endregion #region Extensions namespace YukicoderContest273.Extensions { public static class StringExtensions { public static string Join(this IEnumerable source) => string.Concat(source); public static string Join(this IEnumerable source, char separator) => string.Join(separator, source); public static string Join(this IEnumerable 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(this TextReader reader) => (T1)Convert.ChangeType(reader.ReadLine(), typeof(T1)); public static (T1, T2) ReadValue(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(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(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(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(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(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(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 where TEdge : IEdge { List this[int node] { get; } int NodeCount { get; } } public interface IWeightedGraph : IGraph 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 { private readonly List> _edges; public List this[int node] => _edges[node]; public int NodeCount => _edges.Count; public WeightedGraph(int nodeCount) { _edges = new List>(nodeCount); for (int i = 0; i < nodeCount; i++) { _edges.Add(new List()); } } public void AddEdge(int from, int to, long weight) => _edges[from].Add(new WeightedEdge(to, weight)); public void AddNode() => _edges.Add(new List()); } public class PriorityQueue : IEnumerable where T : IComparable { private List _heap = new List(); 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 collection) { _reverseFactor = descending ? 1 : -1; _heap = new List(); 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 GetEnumerator() { var copy = new List(_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(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 { 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); } } } }