using AtCoder;
using AtCoder.IO;
using AtCoder.Internal;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Linq.Expressions;
using System.Numerics;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using System.Runtime.Intrinsics.X86;
using System.Text;
public partial class Program { static void Main() => new Program(new ConsoleReader(), new ConsoleWriter()).Run();[DebuggerBrowsable(DebuggerBrowsableState.Never)] public ConsoleReader cr;[DebuggerBrowsable(DebuggerBrowsableState.Never)] public ConsoleWriter cw; public Program(ConsoleReader r, ConsoleWriter w) { this.cr = r; this.cw = w; System.Globalization.CultureInfo.CurrentCulture = System.Globalization.CultureInfo.InvariantCulture; } }
public partial class Program
{
public void Run()
{
var res = Calc();
if (res is double) cw.WriteLine(((double)res).ToString("0.####################", System.Globalization.CultureInfo.InvariantCulture));
else if (res is bool) cw.WriteLine(((bool)res) ? "Yes" : "No");
else if (res != null) cw.WriteLine(res.ToString());
cw.Flush();
}
[MethodImpl(MethodImplOptions.AggressiveOptimization)]
private object Calc()
{
N = cr;
M = cr;
_ = cr.Int;
logs = cr.Repeat(N).Select<(int, int)>(cr => (cr, cr));
IntFenwickTree bit;
ILookup<int, (int i, int p, int q, int r)> qs;
ILookup<int, (int i, int p, int q, int r)> rs;
{
var queries = new (int i, int p, int q, int r)[M];
for (int i = 0; i < M; i++) queries[i] = (i, cr, cr.Int0 - 1, cr.Int0);
var ps = queries.Select(t => t.p).Concat(logs.SelectMany(l => new[] { l.a, l.b }))
.Distinct().ToArray().Sort();
{
Dictionary<int, int> rev = new Dictionary<int, int>();
for (int i = 0; i < ps.Length; i++) rev[ps[i]] = i;
foreach (ref var tup in logs.AsSpan()) tup = (rev[tup.a], rev[tup.b]);
foreach (ref var tup in queries.AsSpan()) tup = (tup.i, rev[tup.p], tup.q, tup.r);
}
bit = new IntFenwickTree(ps.Length + 1);
qs = queries.ToLookup(t => t.q);
rs = queries.ToLookup(t => t.r);
}
GC.Collect();
var res = new int[M];
for (int i = 0; i < logs.Length; i++)
{
var (a, b) = logs[i];
bit.Add(a, 1);
bit.Add(b + 1, -1);
foreach (var q in qs[i])
{
res[q.i] -= bit[0..(q.p + 1)];
}
foreach (var q in rs[i])
{
res[q.i] += bit[0..(q.p + 1)];
}
}
cw.WriteLines(res);
return null;
}
int N, M;
(int a, int b)[] logs;
}
#region Expanded
namespace AtCoder { public class IntFenwickTree : FenwickTree<int, IntOperator> { public IntFenwickTree(int n) : base(n) { } } public class UIntFenwickTree : FenwickTree<uint, UIntOperator> { public UIntFenwickTree(int n) : base(n) { } } public class LongFenwickTree : FenwickTree<long, LongOperator> { public LongFenwickTree(int n) : base(n) { } } public class ULongFenwickTree : FenwickTree<ulong, ULongOperator> { public ULongFenwickTree(int n) : base(n) { } } public class StaticModIntFenwickTree<T> : FenwickTree<StaticModInt<T>, StaticModIntOperator<T>> where T : struct, IStaticMod { public StaticModIntFenwickTree(int n) : base(n) { } } public class DynamicModIntFenwickTree<T> : FenwickTree<DynamicModInt<T>, DynamicModIntOperator<T>> where T : struct, IDynamicModID { public DynamicModIntFenwickTree(int n) : base(n) { } } [DebuggerTypeProxy(typeof(FenwickTree<,>.DebugView))] public class FenwickTree<TValue, TOp> where TValue : struct where TOp : struct, IArithmeticOperator<TValue> { private static readonly TOp op = default; internal readonly TValue[] data; public int Length { get; } public FenwickTree(int n) { Debug.Assert(unchecked((uint)n <= 100_000_000)); Length = n; data = new TValue[n + 1]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public void Add(int p, TValue x) { Debug.Assert(unchecked((uint)p < Length)); for (p++; p < data.Length; p += InternalBit.ExtractLowestSetBit(p)) { data[p] = op.Add(data[p], x); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public TValue Sum(int l, int r) { Debug.Assert(0 <= l && l <= r && r < data.Length); return op.Subtract(Sum(r), Sum(l)); } [MethodImpl(MethodImplOptions.AggressiveInlining)] internal TValue Sum(int r) { TValue s = default; for (; r > 0; r -= InternalBit.ExtractLowestSetBit(r)) { s = op.Add(s, data[r]); } return s; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public TValue Slice(int l, int len) => Sum(l, l + len); [DebuggerDisplay("Value = {" + nameof(value) + "}, Sum = {" + nameof(sum) + "}")] internal struct DebugItem { public DebugItem(TValue value, TValue sum) { this.sum = sum; this.value = value; } [DebuggerBrowsable(DebuggerBrowsableState.Never)] public readonly TValue value; [DebuggerBrowsable(DebuggerBrowsableState.Never)] public readonly TValue sum; } internal class DebugView { private readonly FenwickTree<TValue, TOp> fenwickTree; public DebugView(FenwickTree<TValue, TOp> fenwickTree) { this.fenwickTree = fenwickTree; } [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)] public DebugItem[] Items { get { var data = fenwickTree.data; var items = new DebugItem[data.Length - 1]; items[0] = new DebugItem(data[1], data[1]); for (int i = 2; i < data.Length; i++) { int length = InternalBit.ExtractLowestSetBit(i); var pr = i - length - 1; var sum = op.Add(data[i], 0 <= pr ? items[pr].sum : default); var val = op.Subtract(sum, items[i - 2].sum); items[i - 1] = new DebugItem(val, sum); } return items; } } } } }
namespace AtCoder { public static class Extensions { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool UpdateMax<T>(this ref T r, T val) where T : struct, IComparable<T> { if (r.CompareTo(val) < 0) { r = val; return true; } return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static bool UpdateMin<T>(this ref T r, T val) where T : struct, IComparable<T> { if (r.CompareTo(val) > 0) { r = val; return true; } return false; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static T[] Fill<T>(this T[] arr, T value) { arr.AsSpan().Fill(value); return arr; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static T[] Sort<T>(this T[] arr) { Array.Sort(arr); return arr; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static string[] Sort(this string[] arr) => Sort(arr, StringComparer.Ordinal); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static T[] Sort<T, U>(this T[] arr, Expression<Func<T, U>> selector) where U : IComparable<U> => Sort(arr, ExComparer<T>.CreateExp(selector)); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static T[] Sort<T>(this T[] arr, Comparison<T> comparison) { Array.Sort(arr, comparison); return arr; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static T[] Sort<T>(this T[] arr, IComparer<T> comparer) { Array.Sort(arr, comparer); return arr; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static T[] Reverse<T>(this T[] arr) { Array.Reverse(arr); return arr; } public static (int index, T max) MaxBy<T>(this T[] arr) where T : IComparable<T> { T max = arr[0]; int maxIndex = 0; for (int i = 0; i < arr.Length; i++) { if (max.CompareTo(arr[i]) < 0) { max = arr[i]; maxIndex = i; } } return (maxIndex, max); } public static (int index, T max) MaxBy<T, TMax>(this T[] arr, Func<T, TMax> maxBySelector) where TMax : IComparable<TMax> { var maxItem = maxBySelector(arr[0]); var max = arr[0]; int maxIndex = 0; for (int i = 0; i < arr.Length; i++) { var nx = maxBySelector(arr[i]); if (maxItem.CompareTo(nx) < 0) { maxItem = nx; max = arr[i]; maxIndex = i; } } return (maxIndex, max); } public static (TSource item, TMax max) MaxBy<TSource, TMax> (this IEnumerable<TSource> source, Func<TSource, TMax> maxBySelector) where TMax : IComparable<TMax> { TMax max; TSource maxByItem; var e = source.GetEnumerator(); e.MoveNext(); maxByItem = e.Current; max = maxBySelector(maxByItem); while (e.MoveNext()) { var item = e.Current; var next = maxBySelector(item); if (max.CompareTo(next) < 0) { max = next; maxByItem = item; } } return (maxByItem, max); } public static (int index, T min) MinBy<T>(this T[] arr) where T : IComparable<T> { T min = arr[0]; int minIndex = 0; for (int i = 0; i < arr.Length; i++) { if (min.CompareTo(arr[i]) > 0) { min = arr[i]; minIndex = i; } } return (minIndex, min); } public static (int index, T min) MinBy<T, TMin>(this T[] arr, Func<T, TMin> minBySelector) where TMin : IComparable<TMin> { var minItem = minBySelector(arr[0]); var min = arr[0]; int minIndex = 0; for (int i = 0; i < arr.Length; i++) { var nx = minBySelector(arr[i]); if (minItem.CompareTo(nx) > 0) { minItem = nx; min = arr[i]; minIndex = i; } } return (minIndex, min); } public static (TSource item, TMin min) MinBy<TSource, TMin> (this IEnumerable<TSource> source, Func<TSource, TMin> minBySelector) where TMin : IComparable<TMin> { TMin min; TSource minByItem; var e = source.GetEnumerator(); e.MoveNext(); minByItem = e.Current; min = minBySelector(minByItem); while (e.MoveNext()) { var item = e.Current; var next = minBySelector(item); if (min.CompareTo(next) > 0) { min = next; minByItem = item; } } return (minByItem, min); } public static Dictionary<TKey, int> GroupCount<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector) => source.GroupBy(keySelector).ToDictionary(g => g.Key, g => g.Count()); public static Dictionary<TKey, int> GroupCount<TKey>(this IEnumerable<TKey> source) => source.GroupCount(i => i); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Span<T> AsSpan<T>(this List<T> list, int start = 0) => Unsafe.As<Tuple<T[]>>(list).Item1.AsSpan(start, list.Count); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static ref T Get<T>(this T[] arr, int index) { if (index < 0) return ref arr[arr.Length + index]; return ref arr[index]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static TValue Get<TKey, TValue>(this IDictionary<TKey, TValue> dic, TKey key) { dic.TryGetValue(key, out var v); return v; } } }
namespace AtCoder { public static class Global { public static int Gcd(params int[] nums) { var gcd = nums[0]; for (var i = 1; i < nums.Length; i++) gcd = Gcd(nums[i], gcd); return gcd; } public static int Gcd(int a, int b) => b > a ? Gcd(b, a) : (b == 0 ? a : Gcd(b, a % b)); public static int Lcm(int a, int b) => a / Gcd(a, b) * b; public static int Lcm(params int[] nums) { var lcm = nums[0]; for (var i = 1; i < nums.Length; i++) lcm = Lcm(lcm, nums[i]); return lcm; } public static long Gcd(params long[] nums) { var gcd = nums[0]; for (var i = 1; i < nums.Length; i++) gcd = Gcd(nums[i], gcd); return gcd; } public static long Gcd(long a, long b) => b > a ? Gcd(b, a) : (b == 0 ? a : Gcd(b, a % b)); public static long Lcm(long a, long b) => a / Gcd(a, b) * b; public static long Lcm(params long[] nums) { var lcm = nums[0]; for (var i = 1; i < nums.Length; i++) lcm = Lcm(lcm, nums[i]); return lcm; } public static T[] NewArray<T>(int len0, T value) => new T[len0].Fill(value); public static T[] NewArray<T>(int len0, Func<T> factory) { var arr = new T[len0]; for (int i = 0; i < arr.Length; i++) arr[i] = factory(); return arr; } public static T[][] NewArray<T>(int len0, int len1, T value) where T : struct { var arr = new T[len0][]; for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, value); return arr; } public static T[][] NewArray<T>(int len0, int len1, Func<T> factory) { var arr = new T[len0][]; for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, factory); return arr; } public static T[][][] NewArray<T>(int len0, int len1, int len2, T value) where T : struct { var arr = new T[len0][][]; for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, len2, value); return arr; } public static T[][][] NewArray<T>(int len0, int len1, int len2, Func<T> factory) { var arr = new T[len0][][]; for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, len2, factory); return arr; } public static T[][][][] NewArray<T>(int len0, int len1, int len2, int len3, T value) where T : struct { var arr = new T[len0][][][]; for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, len2, len3, value); return arr; } public static T[][][][] NewArray<T>(int len0, int len1, int len2, int len3, Func<T> factory) { var arr = new T[len0][][][]; for (int i = 0; i < arr.Length; i++) arr[i] = NewArray(len1, len2, len3, factory); return arr; } public static long Pow(long x, int y) { long res = 1; for (; y > 0; y >>= 1) { if ((y & 1) == 1) res *= x; x *= x; } return res; } public static BigInteger ParseBigInteger(ReadOnlySpan<char> s) { if (s[0] == '-') return -ParseBigInteger(s[1..]); BigInteger res; if (s.Length % 9 == 0) res = 0; else { res = new BigInteger(int.Parse(s.Slice(0, s.Length % 9))); s = s.Slice(s.Length % 9); } while (s.Length > 0) { var sp = s.Slice(0, 9); res *= 1000_000_000; res += int.Parse(sp); s = s.Slice(9); } return res; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int PopCount(int x) => BitOperations.PopCount((uint)x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int PopCount(long x) => BitOperations.PopCount((ulong)x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int PopCount(ulong x) => BitOperations.PopCount(x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int MSB(int x) => BitOperations.Log2((uint)x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int MSB(uint x) => BitOperations.Log2(x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int MSB(long x) => BitOperations.Log2((ulong)x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int MSB(ulong x) => BitOperations.Log2(x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int LSB(int x) => BitOperations.TrailingZeroCount((uint)x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int LSB(uint x) => BitOperations.TrailingZeroCount(x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int LSB(long x) => BitOperations.TrailingZeroCount((ulong)x); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int LSB(ulong x) => BitOperations.TrailingZeroCount(x); public static Dictionary<T, int> Compress<T>(IEnumerable<T> orig) where T : IComparable<T> => Compress(orig, Comparer<T>.Default); public static Dictionary<T, int> Compress<T>(ReadOnlySpan<T> orig) where T : IComparable<T> => Compress(orig, Comparer<T>.Default); public static Dictionary<T, int> Compress<T>(T[] orig) where T : IComparable<T> => Compress(orig.AsSpan(), Comparer<T>.Default); public static Dictionary<T, int> Compress<T>(IEnumerable<T> orig, IComparer<T> comparer) { var ox = new HashSet<T>(orig).ToArray(); Array.Sort(ox, comparer); var zip = new Dictionary<T, int>(); for (int i = 0; i < ox.Length; i++) zip[ox[i]] = i; return zip; } public static Dictionary<T, int> Compress<T>(ReadOnlySpan<T> orig, IComparer<T> comparer) { var hs = new HashSet<T>(orig.Length); foreach (var v in orig) hs.Add(v); var ox = hs.ToArray(); Array.Sort(ox, comparer); var zip = new Dictionary<T, int>(); for (int i = 0; i < ox.Length; i++) zip[ox[i]] = i; return zip; } public static int[] Compressed<T>(ReadOnlySpan<T> orig) where T : IComparable<T> { static int[] Compressed(ReadOnlySpan<T> orig, Dictionary<T, int> zip) { var res = new int[orig.Length]; for (int i = 0; i < res.Length; i++) res[i] = zip[orig[i]]; return res; } return Compressed(orig, Compress(orig, Comparer<T>.Default)); } } }
namespace AtCoder.IO { [DebuggerStepThrough] public class ConsoleReader { const int BufSize = 1 << 12; private readonly byte[] buffer = new byte[BufSize]; private readonly Stream input; private readonly Encoding encoding; private int pos = 0; private int len = 0; public ConsoleReader(Stream input, Encoding encoding) { this.input = input; this.encoding = encoding; } public ConsoleReader() : this(Console.OpenStandardInput(), Console.InputEncoding) { } [MethodImpl(MethodImplOptions.AggressiveInlining)] private void MoveNext() { if (++pos >= len) { len = input.Read(buffer, 0, buffer.Length); if (len == 0) { buffer[0] = 10; } pos = 0; } } public int Int { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { int res = 0; bool neg = false; while (buffer[pos] < 48) { neg = buffer[pos] == 45; MoveNext(); } do { res = checked(res * 10 + (buffer[pos] ^ 48)); MoveNext(); } while (48 <= buffer[pos]); return neg ? -res : res; } } public int Int0 => Int - 1; public long Long { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { long res = 0; bool neg = false; while (buffer[pos] < 48) { neg = buffer[pos] == 45; MoveNext(); } do { res = res * 10 + (buffer[pos] ^ 48); MoveNext(); } while (48 <= buffer[pos]); return neg ? -res : res; } } public long Long0 => Long - 1; public string String { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { var sb = new List<byte>(); while (buffer[pos] <= 32) MoveNext(); do { sb.Add(buffer[pos]); MoveNext(); } while (32 < buffer[pos]); return encoding.GetString(sb.ToArray()); } } public string Ascii { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { var sb = new StringBuilder(); while (buffer[pos] <= 32) MoveNext(); do { sb.Append((char)buffer[pos]); MoveNext(); } while (32 < buffer[pos]); return sb.ToString(); } } public string Line { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { var sb = new List<byte>(); while (buffer[pos] <= 32) MoveNext(); do { sb.Add(buffer[pos]); MoveNext(); } while (buffer[pos] != 10 && buffer[pos] != 13); return encoding.GetString(sb.ToArray()); } } public char Char { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { while (buffer[pos] <= 32) MoveNext(); char res = (char)buffer[pos]; MoveNext(); return res; } } public double Double => double.Parse(Ascii); [DebuggerStepThrough] public ref struct RepeatReader { readonly ConsoleReader cr; readonly int count; public RepeatReader(ConsoleReader cr, int count) { this.cr = cr; this.count = count; } public T[] Select<T>(Func<ConsoleReader, T> factory) { var arr = new T[count]; for (var i = 0; i < count; i++) arr[i] = factory(cr); return arr; } public T[] Select<T>(Func<ConsoleReader, int, T> factory) { var arr = new T[count]; for (var i = 0; i < count; i++) arr[i] = factory(cr, i); return arr; } public string[] Line { get { var arr = new string[count]; for (var i = 0; i < count; i++) arr[i] = cr.Line; return arr; } } public string[] String { get { var arr = new string[count]; for (var i = 0; i < count; i++) arr[i] = cr.String; return arr; } } public string[] Ascii { get { var arr = new string[count]; for (var i = 0; i < count; i++) arr[i] = cr.Ascii; return arr; } } public int[] Int { get { var arr = new int[count]; for (var i = 0; i < count; i++) arr[i] = cr.Int; return arr; } } public int[] Int0 { get { var arr = new int[count]; for (var i = 0; i < count; i++) arr[i] = cr.Int0; return arr; } } public long[] Long { get { var arr = new long[count]; for (var i = 0; i < count; i++) arr[i] = cr.Long; return arr; } } public long[] Long0 { get { var arr = new long[count]; for (var i = 0; i < count; i++) arr[i] = cr.Long0; return arr; } } public double[] Double { get { var arr = new double[count]; for (var i = 0; i < count; i++) arr[i] = cr.Double; return arr; } } public static implicit operator int[](RepeatReader rr) => rr.Int; public static implicit operator long[](RepeatReader rr) => rr.Long; public static implicit operator double[](RepeatReader rr) => rr.Double; public static implicit operator string[](RepeatReader rr) => rr.Ascii; } public RepeatReader Repeat(int count) => new RepeatReader(this, count); [DebuggerStepThrough] public ref struct SplitReader { readonly ConsoleReader cr; public SplitReader(ConsoleReader cr) { this.cr = cr; } public string[] String { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<string>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.String); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public string[] Ascii { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<string>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Ascii); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public int[] Int { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<int>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Int); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public int[] Int0 { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<int>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Int0); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public long[] Long { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<long>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Long); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public long[] Long0 { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<long>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Long0); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public double[] Double { get { while (cr.buffer[cr.pos] <= 32) cr.MoveNext(); var list = new List<double>(); do { if (cr.buffer[cr.pos] < 32) cr.MoveNext(); else list.Add(cr.Double); } while (cr.buffer[cr.pos] != 10 && cr.buffer[cr.pos] != 13); return list.ToArray(); } } public static implicit operator int[](SplitReader sr) => sr.Int; public static implicit operator long[](SplitReader sr) => sr.Long; public static implicit operator double[](SplitReader sr) => sr.Double; public static implicit operator string[](SplitReader sr) => sr.Ascii; } public SplitReader Split => new SplitReader(this); public static implicit operator int(ConsoleReader cr) => cr.Int; public static implicit operator long(ConsoleReader cr) => cr.Long; public static implicit operator double(ConsoleReader cr) => cr.Double; public static implicit operator string(ConsoleReader cr) => cr.Ascii; } }
namespace AtCoder.IO { [DebuggerStepThrough] public class ConsoleWriter { [DebuggerBrowsable(DebuggerBrowsableState.Never)] public readonly StreamWriter sw; public ConsoleWriter() : this(Console.OpenStandardOutput(), Console.OutputEncoding) { } public ConsoleWriter(Stream output, Encoding encoding) { sw = new StreamWriter(output, encoding); } public void Flush() => sw.Flush(); public ConsoleWriter WriteLine(ReadOnlySpan<char> obj) { sw.WriteLine(obj); return this; } public ConsoleWriter WriteLine<T>(T obj) { sw.WriteLine(obj.ToString()); return this; } public ConsoleWriter WriteLineJoin<T>(Span<T> col) => WriteMany(' ', (ReadOnlySpan<T>)col); public ConsoleWriter WriteLineJoin<T>(ReadOnlySpan<T> col) => WriteMany(' ', col); public ConsoleWriter WriteLineJoin<T>(IEnumerable<T> col) => WriteMany(' ', col); public ConsoleWriter WriteLineJoin<T>(params T[] col) => WriteMany(' ', col); public ConsoleWriter WriteLineJoin(params object[] col) => WriteMany(' ', col); public ConsoleWriter WriteLineJoin<T1, T2>(T1 v1, T2 v2) { sw.Write(v1.ToString()); sw.Write(' '); sw.WriteLine(v2.ToString()); return this; } public ConsoleWriter WriteLineJoin<T1, T2, T3>(T1 v1, T2 v2, T3 v3) { sw.Write(v1.ToString()); sw.Write(' '); sw.Write(v2.ToString()); sw.Write(' '); sw.WriteLine(v3.ToString()); return this; } public ConsoleWriter WriteLineJoin<T1, T2, T3, T4>(T1 v1, T2 v2, T3 v3, T4 v4) { sw.Write(v1.ToString()); sw.Write(' '); sw.Write(v2.ToString()); sw.Write(' '); sw.Write(v3.ToString()); sw.Write(' '); sw.WriteLine(v4.ToString()); return this; } public ConsoleWriter WriteLines<T>(Span<T> col) => WriteMany('\n', (ReadOnlySpan<T>)col); public ConsoleWriter WriteLines<T>(ReadOnlySpan<T> col) => WriteMany('\n', col); public ConsoleWriter WriteLines<T>(IEnumerable<T> col) => WriteMany('\n', col); public ConsoleWriter WriteLineGrid<T>(IEnumerable<IEnumerable<T>> cols) { foreach (var col in cols) WriteLineJoin(col); return this; } private ConsoleWriter WriteMany<T>(char sep, ReadOnlySpan<T> col) { var en = col.GetEnumerator(); if (!en.MoveNext()) return this; sw.Write(en.Current.ToString()); while (en.MoveNext()) { sw.Write(sep); sw.Write(en.Current.ToString()); } sw.WriteLine(); return this; } private ConsoleWriter WriteMany<T>(char sep, IEnumerable<T> col) { var en = col.GetEnumerator(); if (!en.MoveNext()) return this; sw.Write(en.Current.ToString()); while (en.MoveNext()) { sw.Write(sep); sw.Write(en.Current.ToString()); } sw.WriteLine(); return this; } } }
namespace AtCoder { public interface IArithmeticOperator<T> where T : struct { T Add(T x, T y); T Subtract(T x, T y); T Multiply(T x, T y); T Divide(T x, T y); T Modulo(T x, T y); T Minus(T x); T Increment(T x); T Decrement(T x); } public interface ICompareOperator<T> : IEqualityComparer<T>, IComparer<T> where T : struct { bool GreaterThan(T x, T y); bool GreaterThanOrEqual(T x, T y); bool LessThan(T x, T y); bool LessThanOrEqual(T x, T y); } public interface INumOperator<T> : IArithmeticOperator<T>, ICompareOperator<T> where T : struct { public T MinValue { get; } public T MaxValue { get; } } public readonly struct IntOperator : INumOperator<int> { public int MinValue => int.MinValue; public int MaxValue => int.MaxValue; public int Add(int x, int y) => x + y; public int Subtract(int x, int y) => x - y; public int Multiply(int x, int y) => x * y; public int Divide(int x, int y) => x / y; public int Modulo(int x, int y) => x % y; public int Minus(int x) => -x; public int Increment(int x) => ++x; public int Decrement(int x) => --x; public bool GreaterThan(int x, int y) => x > y; public bool GreaterThanOrEqual(int x, int y) => x >= y; public bool LessThan(int x, int y) => x < y; public bool LessThanOrEqual(int x, int y) => x <= y; public int Compare(int x, int y) => x.CompareTo(y); public bool Equals(int x, int y) => x == y; public int GetHashCode(int obj) => obj.GetHashCode(); } public readonly struct LongOperator : INumOperator<long> { public long MinValue => long.MinValue; public long MaxValue => long.MaxValue; public long Add(long x, long y) => x + y; public long Subtract(long x, long y) => x - y; public long Multiply(long x, long y) => x * y; public long Divide(long x, long y) => x / y; public long Modulo(long x, long y) => x % y; public long Minus(long x) => -x; public long Increment(long x) => ++x; public long Decrement(long x) => --x; public bool GreaterThan(long x, long y) => x > y; public bool GreaterThanOrEqual(long x, long y) => x >= y; public bool LessThan(long x, long y) => x < y; public bool LessThanOrEqual(long x, long y) => x <= y; public int Compare(long x, long y) => x.CompareTo(y); public bool Equals(long x, long y) => x == y; public int GetHashCode(long obj) => obj.GetHashCode(); } public readonly struct UIntOperator : INumOperator<uint> { public uint MinValue => uint.MinValue; public uint MaxValue => uint.MaxValue; public uint Add(uint x, uint y) => x + y; public uint Subtract(uint x, uint y) => x - y; public uint Multiply(uint x, uint y) => x * y; public uint Divide(uint x, uint y) => x / y; public uint Modulo(uint x, uint y) => x % y; public uint Minus(uint x) => throw new InvalidOperationException("Uint type cannot be negative."); public uint Increment(uint x) => ++x; public uint Decrement(uint x) => --x; public bool GreaterThan(uint x, uint y) => x > y; public bool GreaterThanOrEqual(uint x, uint y) => x >= y; public bool LessThan(uint x, uint y) => x < y; public bool LessThanOrEqual(uint x, uint y) => x <= y; public int Compare(uint x, uint y) => x.CompareTo(y); public bool Equals(uint x, uint y) => x == y; public int GetHashCode(uint obj) => obj.GetHashCode(); } public readonly struct ULongOperator : INumOperator<ulong> { public ulong MinValue => ulong.MinValue; public ulong MaxValue => ulong.MaxValue; public ulong Add(ulong x, ulong y) => x + y; public ulong Subtract(ulong x, ulong y) => x - y; public ulong Multiply(ulong x, ulong y) => x * y; public ulong Divide(ulong x, ulong y) => x / y; public ulong Modulo(ulong x, ulong y) => x % y; public ulong Minus(ulong x) => throw new InvalidOperationException("Ulong type cannot be negative."); public ulong Increment(ulong x) => ++x; public ulong Decrement(ulong x) => --x; public bool GreaterThan(ulong x, ulong y) => x > y; public bool GreaterThanOrEqual(ulong x, ulong y) => x >= y; public bool LessThan(ulong x, ulong y) => x < y; public bool LessThanOrEqual(ulong x, ulong y) => x <= y; public int Compare(ulong x, ulong y) => x.CompareTo(y); public bool Equals(ulong x, ulong y) => x == y; public int GetHashCode(ulong obj) => obj.GetHashCode(); } public readonly struct DoubleOperator : INumOperator<double> { public double MinValue => double.MinValue; public double MaxValue => double.MaxValue; public double Add(double x, double y) => x + y; public double Subtract(double x, double y) => x - y; public double Multiply(double x, double y) => x * y; public double Divide(double x, double y) => x / y; public double Modulo(double x, double y) => x % y; public double Minus(double x) => -x; public double Increment(double x) => ++x; public double Decrement(double x) => --x; public bool GreaterThan(double x, double y) => x > y; public bool GreaterThanOrEqual(double x, double y) => x >= y; public bool LessThan(double x, double y) => x < y; public bool LessThanOrEqual(double x, double y) => x <= y; public int Compare(double x, double y) => x.CompareTo(y); public bool Equals(double x, double y) => x == y; public int GetHashCode(double obj) => obj.GetHashCode(); } }
namespace AtCoder { public interface IStaticMod { uint Mod { get; } 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; } public readonly struct StaticModIntOperator<T> : IArithmeticOperator<StaticModInt<T>> where T : struct, IStaticMod { public StaticModInt<T> Add(StaticModInt<T> x, StaticModInt<T> y) => x + y; public StaticModInt<T> Subtract(StaticModInt<T> x, StaticModInt<T> y) => x - y; public StaticModInt<T> Multiply(StaticModInt<T> x, StaticModInt<T> y) => x * y; public StaticModInt<T> Divide(StaticModInt<T> x, StaticModInt<T> y) => x / y; public StaticModInt<T> Modulo(StaticModInt<T> x, StaticModInt<T> y) => throw new NotSupportedException(); public StaticModInt<T> Minus(StaticModInt<T> x) => -x; public StaticModInt<T> Increment(StaticModInt<T> x) => ++x; public StaticModInt<T> Decrement(StaticModInt<T> x) => --x; } public readonly struct StaticModInt<T> : IEquatable<StaticModInt<T>> where T : struct, IStaticMod { internal readonly uint _v; private static readonly T op = default; public int Value => (int)_v; public static int Mod => (int)op.Mod; [MethodImpl(MethodImplOptions.AggressiveInlining)] public static StaticModInt<T> Raw(int v) { var u = unchecked((uint)v); Debug.Assert(u < Mod); return new StaticModInt<T>(u); } 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 % op.Mod; if (x < 0) { x += op.Mod; } return (uint)x; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static StaticModInt<T> operator ++(StaticModInt<T> value) { var v = value._v + 1; if (v == op.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 = op.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 >= op.Mod) { v -= op.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 >= op.Mod) { v += op.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 % op.Mod)); } public static StaticModInt<T> operator /(StaticModInt<T> lhs, StaticModInt<T> rhs) => lhs * rhs.Inv(); public static StaticModInt<T> operator +(StaticModInt<T> value) => value; public static StaticModInt<T> operator -(StaticModInt<T> value) => new StaticModInt<T>(op.Mod - value._v); 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); public StaticModInt<T> Pow(long n) { Debug.Assert(0 <= n); var x = this; var r = new StaticModInt<T>(1U); while (n > 0) { if ((n & 1) > 0) { r *= x; } x *= x; n >>= 1; } return r; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public StaticModInt<T> Inv() { if (op.IsPrime) { Debug.Assert(_v > 0); return Pow(op.Mod - 2); } else { var (g, x) = Internal.InternalMath.InvGCD(_v, op.Mod); Debug.Assert(g == 1); return new StaticModInt<T>(x); } } 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) => _v == other._v; public override int GetHashCode() => _v.GetHashCode(); } }
namespace AtCoder { public interface IDynamicModID { } public static class DynamicModIDExtension { public static void SetMod<T>(this T _, int mod) where T : struct, IDynamicModID => DynamicModInt<T>.Mod = mod; } public readonly struct ModID0 : IDynamicModID { } public readonly struct ModID1 : IDynamicModID { } public readonly struct ModID2 : IDynamicModID { } public readonly struct DynamicModIntOperator<T> : IArithmeticOperator<DynamicModInt<T>> where T : struct, IDynamicModID { public DynamicModInt<T> Add(DynamicModInt<T> x, DynamicModInt<T> y) => x + y; public DynamicModInt<T> Subtract(DynamicModInt<T> x, DynamicModInt<T> y) => x - y; public DynamicModInt<T> Multiply(DynamicModInt<T> x, DynamicModInt<T> y) => x * y; public DynamicModInt<T> Divide(DynamicModInt<T> x, DynamicModInt<T> y) => x / y; public DynamicModInt<T> Modulo(DynamicModInt<T> x, DynamicModInt<T> y) => throw new NotSupportedException(); public DynamicModInt<T> Minus(DynamicModInt<T> x) => -x; public DynamicModInt<T> Increment(DynamicModInt<T> x) => ++x; public DynamicModInt<T> Decrement(DynamicModInt<T> x) => --x; } public readonly struct DynamicModInt<T> : IEquatable<DynamicModInt<T>> where T : struct, IDynamicModID { internal readonly uint _v; internal static Internal.Barrett bt; public int Value => (int)_v; public static int Mod { get => (int)bt.Mod; set { Debug.Assert(1 <= value); bt = new Internal.Barrett((uint)value); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static DynamicModInt<T> Raw(int v) { var u = unchecked((uint)v); Debug.Assert(bt != null, $"使用前に {nameof(DynamicModInt<T>)}<{nameof(T)}>.{nameof(Mod)} プロパティに mod の値を設定してください。"); Debug.Assert(u < Mod); return new DynamicModInt<T>(u); } public DynamicModInt(long v) : this(Round(v)) { } private DynamicModInt(uint v) => _v = v; [MethodImpl(MethodImplOptions.AggressiveInlining)] private static uint Round(long v) { Debug.Assert(bt != null, $"使用前に {nameof(DynamicModInt<T>)}<{nameof(T)}>.{nameof(Mod)} プロパティに mod の値を設定してください。"); var x = v % bt.Mod; if (x < 0) { x += bt.Mod; } return (uint)x; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static DynamicModInt<T> operator ++(DynamicModInt<T> value) { var v = value._v + 1; if (v == bt.Mod) { v = 0; } return new DynamicModInt<T>(v); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static DynamicModInt<T> operator --(DynamicModInt<T> value) { var v = value._v; if (v == 0) { v = bt.Mod; } return new DynamicModInt<T>(v - 1); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static DynamicModInt<T> operator +(DynamicModInt<T> lhs, DynamicModInt<T> rhs) { var v = lhs._v + rhs._v; if (v >= bt.Mod) { v -= bt.Mod; } return new DynamicModInt<T>(v); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static DynamicModInt<T> operator -(DynamicModInt<T> lhs, DynamicModInt<T> rhs) { unchecked { var v = lhs._v - rhs._v; if (v >= bt.Mod) { v += bt.Mod; } return new DynamicModInt<T>(v); } } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static DynamicModInt<T> operator *(DynamicModInt<T> lhs, DynamicModInt<T> rhs) { uint z = bt.Mul(lhs._v, rhs._v); return new DynamicModInt<T>(z); } public static DynamicModInt<T> operator /(DynamicModInt<T> lhs, DynamicModInt<T> rhs) => lhs * rhs.Inv(); public static DynamicModInt<T> operator +(DynamicModInt<T> value) => value; public static DynamicModInt<T> operator -(DynamicModInt<T> value) => new DynamicModInt<T>(Mod - value.Value); public static bool operator ==(DynamicModInt<T> lhs, DynamicModInt<T> rhs) => lhs._v == rhs._v; public static bool operator !=(DynamicModInt<T> lhs, DynamicModInt<T> rhs) => lhs._v != rhs._v; public static implicit operator DynamicModInt<T>(int value) => new DynamicModInt<T>(value); public static implicit operator DynamicModInt<T>(long value) => new DynamicModInt<T>(value); public DynamicModInt<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; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public DynamicModInt<T> Inv() { var (g, x) = Internal.InternalMath.InvGCD(_v, bt.Mod); Debug.Assert(g == 1); return new DynamicModInt<T>(x); } public override string ToString() => _v.ToString(); public override bool Equals(object obj) => obj is DynamicModInt<T> && Equals((DynamicModInt<T>)obj); public bool Equals(DynamicModInt<T> other) => Value == other.Value; public override int GetHashCode() => _v.GetHashCode(); } }
namespace AtCoder.Internal { public static class InternalBit { [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int ExtractLowestSetBit(int n) { if (Bmi1.IsSupported) { return (int)Bmi1.ExtractLowestSetBit((uint)n); } return n & -n; } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static int BSF(uint n) { Debug.Assert(n >= 1); return BitOperations.TrailingZeroCount(n); } public static int CeilPow2(int n) { var un = (uint)n; if (un <= 1) return 0; return BitOperations.Log2(un - 1) + 1; } } }
namespace AtCoder { public static class ExComparer<T> { class ExpressionComparer<K> : IComparer<T> where K : IComparable<K> { private class ParameterReplaceVisitor : ExpressionVisitor { private readonly ParameterExpression from; private readonly ParameterExpression to; public ParameterReplaceVisitor(ParameterExpression from, ParameterExpression to) { this.from = from; this.to = to; } protected override Expression VisitParameter(ParameterExpression node) => node == from ? to : base.VisitParameter(node); } readonly Comparison<T> func; public ExpressionComparer(Expression<Func<T, K>> expression) { var paramA = expression.Parameters[0]; var paramB = Expression.Parameter(typeof(T)); var f2 = (Expression<Func<T, K>>)new ParameterReplaceVisitor(expression.Parameters[0], paramB).Visit(expression); var compExp = Expression.Lambda<Comparison<T>>(Expression.Call( expression.Body, typeof(K).GetMethod(nameof(IComparable<K>.CompareTo), new[] { typeof(K) }), f2.Body), paramA, paramB); this.func = compExp.Compile(); } public int Compare(T x, T y) => func(x, y); public override bool Equals(object obj) => obj is ExpressionComparer<K> c && this.func == c.func; public override int GetHashCode() => func.GetHashCode(); } class ReverseComparer : IComparer<T> { private static readonly Comparer<T> orig = Comparer<T>.Default; public int Compare(T y, T x) => orig.Compare(x, y); public override bool Equals(object obj) => obj is ReverseComparer; public override int GetHashCode() => GetType().GetHashCode(); } public static IComparer<T> CreateExp<K>(Expression<Func<T, K>> expression) where K : IComparable<K> => new ExpressionComparer<K>(expression); public static readonly IComparer<T> DefaultReverse = new ReverseComparer(); } }
namespace AtCoder.Internal { public static partial class InternalMath { private static readonly Dictionary<int, int> primitiveRootsCache = new Dictionary<int, int>() { { 2, 1 }, { 167772161, 3 }, { 469762049, 3 }, { 754974721, 11 }, { 998244353, 3 } }; public static int PrimitiveRoot(int m) { Debug.Assert(m >= 2); if (primitiveRootsCache.TryGetValue(m, out var p)) { return p; } return primitiveRootsCache[m] = Calculate(m); int Calculate(int m) { Span<int> divs = stackalloc int[20]; divs[0] = 2; int cnt = 1; int x = (m - 1) / 2; while (x % 2 == 0) { x >>= 1; } for (int i = 3; (long)i * i <= x; i += 2) { if (x % i == 0) { divs[cnt++] = i; while (x % i == 0) { x /= i; } } } if (x > 1) { divs[cnt++] = x; } for (int g = 2; ; g++) { bool ok = true; for (int i = 0; i < cnt; i++) { if (MathLib.PowMod(g, (m - 1) / divs[i], m) == 1) { ok = false; break; } } if (ok) { return g; } } } } public static (long, long) InvGCD(long a, long b) { a = SafeMod(a, b); if (a == 0) return (b, 0); long s = b, t = a; long m0 = 0, m1 = 1; long u; while (true) { if (t == 0) { if (m0 < 0) m0 += b / s; return (s, m0); } u = s / t; s -= t * u; m0 -= m1 * u; if (s == 0) { if (m1 < 0) m1 += b / t; return (t, m1); } u = t / s; t -= s * u; m1 -= m0 * u; } } public static long SafeMod(long x, long m) { x %= m; if (x < 0) x += m; return x; } public static bool IsPrime(int n) { Debug.Assert(0 <= n); if (n <= 1) return false; if (n == 2 || n == 7 || n == 61) return true; if (n % 2 == 0) return false; long d = n - 1; while (d % 2 == 0) d /= 2; ReadOnlySpan<long> bases = stackalloc long[3] { 2, 7, 61 }; foreach (long a in bases) { long t = d; long y = MathLib.PowMod(a, t, n); while (t != n - 1 && y != 1 && y != n - 1) { y = y * y % n; t <<= 1; } if (y != n - 1 && t % 2 == 0) { return false; } } return true; } } }
namespace AtCoder.Internal { public class Barrett { public uint Mod { get; private set; } internal readonly ulong IM; public Barrett(uint m) { Mod = m; IM = unchecked((ulong)-1) / m + 1; } public uint Mul(uint a, uint b) { ulong z = a; z *= b; if (!Bmi2.X64.IsSupported) return (uint)(z % Mod); var x = Bmi2.X64.MultiplyNoFlags(z, IM); var v = unchecked((uint)(z - x * Mod)); if (Mod <= v) v += Mod; return v; } } }
namespace AtCoder { public static class MathLib { public static int[] Convolution(int[] a, int[] b) => Convolution<Mod998244353>(a, b); public static uint[] Convolution(uint[] a, uint[] b) => Convolution<Mod998244353>(a, b); public static long[] Convolution(long[] a, long[] b) => Convolution<Mod998244353>(a, b); public static ulong[] Convolution(ulong[] a, ulong[] b) => Convolution<Mod998244353>(a, b); public static int[] Convolution<TMod>(int[] a, int[] b) where TMod : struct, IStaticMod { var n = a.Length; var m = b.Length; if (n == 0 || m == 0) { return Array.Empty<int>(); } if (Math.Min(n, m) <= 60) { var c = ConvolutionNaive<TMod>(a.Select(ai => new StaticModInt<TMod>(ai)).ToArray(), b.Select(bi => new StaticModInt<TMod>(bi)).ToArray()); return c.Select(ci => ci.Value).ToArray(); } else { int z = 1 << InternalBit.CeilPow2(n + m - 1); var aTemp = new StaticModInt<TMod>[z]; for (int i = 0; i < a.Length; i++) { aTemp[i] = new StaticModInt<TMod>(a[i]); } var bTemp = new StaticModInt<TMod>[z]; for (int i = 0; i < b.Length; i++) { bTemp[i] = new StaticModInt<TMod>(b[i]); } var c = Convolution<TMod>(aTemp, bTemp, n, m, z)[0..(n + m - 1)]; var result = new int[c.Length]; for (int i = 0; i < result.Length; i++) { result[i] = c[i].Value; } return result; } } public static uint[] Convolution<TMod>(uint[] a, uint[] b) where TMod : struct, IStaticMod { var n = a.Length; var m = b.Length; if (n == 0 || m == 0) { return Array.Empty<uint>(); } if (Math.Min(n, m) <= 60) { var c = ConvolutionNaive<TMod>(a.Select(ai => new StaticModInt<TMod>(ai)).ToArray(), b.Select(bi => new StaticModInt<TMod>(bi)).ToArray()); return c.Select(ci => (uint)ci.Value).ToArray(); } else { int z = 1 << InternalBit.CeilPow2(n + m - 1); var aTemp = new StaticModInt<TMod>[z]; for (int i = 0; i < a.Length; i++) { aTemp[i] = new StaticModInt<TMod>(a[i]); } var bTemp = new StaticModInt<TMod>[z]; for (int i = 0; i < b.Length; i++) { bTemp[i] = new StaticModInt<TMod>(b[i]); } var c = Convolution<TMod>(aTemp, bTemp, n, m, z)[0..(n + m - 1)]; var result = new uint[c.Length]; for (int i = 0; i < result.Length; i++) { result[i] = (uint)c[i].Value; } return result; } } public static long[] Convolution<TMod>(long[] a, long[] b) where TMod : struct, IStaticMod { var n = a.Length; var m = b.Length; if (n == 0 || m == 0) { return Array.Empty<long>(); } if (Math.Min(n, m) <= 60) { var c = ConvolutionNaive<TMod>(a.Select(ai => new StaticModInt<TMod>(ai)).ToArray(), b.Select(bi => new StaticModInt<TMod>(bi)).ToArray()); return c.Select(ci => (long)ci.Value).ToArray(); } else { int z = 1 << InternalBit.CeilPow2(n + m - 1); var aTemp = new StaticModInt<TMod>[z]; for (int i = 0; i < a.Length; i++) { aTemp[i] = new StaticModInt<TMod>(a[i]); } var bTemp = new StaticModInt<TMod>[z]; for (int i = 0; i < b.Length; i++) { bTemp[i] = new StaticModInt<TMod>(b[i]); } var c = Convolution<TMod>(aTemp, bTemp, n, m, z)[0..(n + m - 1)]; var result = new long[c.Length]; for (int i = 0; i < result.Length; i++) { result[i] = c[i].Value; } return result; } } public static ulong[] Convolution<TMod>(ulong[] a, ulong[] b) where TMod : struct, IStaticMod { var n = a.Length; var m = b.Length; if (n == 0 || m == 0) { return Array.Empty<ulong>(); } if (Math.Min(n, m) <= 60) { var c = ConvolutionNaive<TMod>(a.Select(TakeMod).ToArray(), b.Select(TakeMod).ToArray()); return c.Select(ci => (ulong)ci.Value).ToArray(); } else { int z = 1 << InternalBit.CeilPow2(n + m - 1); var aTemp = new StaticModInt<TMod>[z]; for (int i = 0; i < a.Length; i++) { aTemp[i] = TakeMod(a[i]); } var bTemp = new StaticModInt<TMod>[z]; for (int i = 0; i < b.Length; i++) { bTemp[i] = TakeMod(b[i]); } var c = Convolution<TMod>(aTemp, bTemp, n, m, z)[0..(n + m - 1)]; var result = new ulong[c.Length]; for (int i = 0; i < result.Length; i++) { result[i] = (ulong)c[i].Value; } return result; } static StaticModInt<TMod> TakeMod(ulong x) => StaticModInt<TMod>.Raw((int)(x % default(TMod).Mod)); } public static StaticModInt<TMod>[] Convolution<TMod>(StaticModInt<TMod>[] a, StaticModInt<TMod>[] b) where TMod : struct, IStaticMod { var temp = Convolution((ReadOnlySpan<StaticModInt<TMod>>)a, b); return temp.ToArray(); } public static Span<StaticModInt<TMod>> Convolution<TMod>(ReadOnlySpan<StaticModInt<TMod>> a, ReadOnlySpan<StaticModInt<TMod>> b) where TMod : struct, IStaticMod { var n = a.Length; var m = b.Length; if (n == 0 || m == 0) { return Array.Empty<StaticModInt<TMod>>(); } if (Math.Min(n, m) <= 60) { return ConvolutionNaive(a, b); } int z = 1 << InternalBit.CeilPow2(n + m - 1); var aTemp = new StaticModInt<TMod>[z]; a.CopyTo(aTemp); var bTemp = new StaticModInt<TMod>[z]; b.CopyTo(bTemp); return Convolution(aTemp.AsSpan(), bTemp.AsSpan(), n, m, z); } private static Span<StaticModInt<TMod>> Convolution<TMod>(Span<StaticModInt<TMod>> a, Span<StaticModInt<TMod>> b, int n, int m, int z) where TMod : struct, IStaticMod { Internal.Butterfly<TMod>.Calculate(a); Internal.Butterfly<TMod>.Calculate(b); for (int i = 0; i < a.Length; i++) { a[i] *= b[i]; } Internal.Butterfly<TMod>.CalculateInv(a); var result = a[0..(n + m - 1)]; var iz = new StaticModInt<TMod>(z).Inv(); foreach (ref var r in result) { r *= iz; } return result; } public static long[] ConvolutionLong(ReadOnlySpan<long> a, ReadOnlySpan<long> b) { unchecked { var n = a.Length; var m = b.Length; if (n == 0 || m == 0) { return Array.Empty<long>(); } const ulong Mod1 = 754974721; const ulong Mod2 = 167772161; const ulong Mod3 = 469762049; const ulong M2M3 = Mod2 * Mod3; const ulong M1M3 = Mod1 * Mod3; const ulong M1M2 = Mod1 * Mod2; const ulong M1M2M3 = Mod1 * Mod2 * Mod3; ulong i1 = (ulong)InternalMath.InvGCD((long)M2M3, (long)Mod1).Item2; ulong i2 = (ulong)InternalMath.InvGCD((long)M1M3, (long)Mod2).Item2; ulong i3 = (ulong)InternalMath.InvGCD((long)M1M2, (long)Mod3).Item2; var c1 = Convolution<FFTMod1>(a, b); var c2 = Convolution<FFTMod2>(a, b); var c3 = Convolution<FFTMod3>(a, b); var c = new long[n + m - 1]; Span<ulong> offset = stackalloc ulong[] { 0, 0, M1M2M3, 2 * M1M2M3, 3 * M1M2M3 }; for (int i = 0; i < c.Length; i++) { ulong x = 0; x += (c1[i] * i1) % Mod1 * M2M3; x += (c2[i] * i2) % Mod2 * M1M3; x += (c3[i] * i3) % Mod3 * M1M2; long diff = (long)c1[i] - InternalMath.SafeMod((long)x, (long)Mod1); if (diff < 0) { diff += (long)Mod1; } x -= offset[(int)(diff % offset.Length)]; c[i] = (long)x; } return c; } } private static ulong[] Convolution<TMod>(ReadOnlySpan<long> a, ReadOnlySpan<long> b) where TMod : struct, IStaticMod { int z = 1 << InternalBit.CeilPow2(a.Length + b.Length - 1); var aTemp = new StaticModInt<TMod>[z]; for (int i = 0; i < a.Length; i++) { aTemp[i] = new StaticModInt<TMod>(a[i]); } var bTemp = new StaticModInt<TMod>[z]; for (int i = 0; i < b.Length; i++) { bTemp[i] = new StaticModInt<TMod>(b[i]); } var c = AtCoder.MathLib.Convolution<TMod>(aTemp, bTemp, a.Length, b.Length, z); var result = new ulong[c.Length]; for (int i = 0; i < result.Length; i++) { result[i] = (ulong)c[i].Value; } return result; } private static StaticModInt<TMod>[] ConvolutionNaive<TMod>(ReadOnlySpan<StaticModInt<TMod>> a, ReadOnlySpan<StaticModInt<TMod>> b) where TMod : struct, IStaticMod { if (a.Length < b.Length) { var temp = a; a = b; b = temp; } var ans = new StaticModInt<TMod>[a.Length + b.Length - 1]; for (int i = 0; i < a.Length; i++) { for (int j = 0; j < b.Length; j++) { ans[i + j] += a[i] * b[j]; } } return ans; } private readonly struct FFTMod1 : IStaticMod { public uint Mod => 754974721; public bool IsPrime => true; } private readonly struct FFTMod2 : IStaticMod { public uint Mod => 167772161; public bool IsPrime => true; } private readonly struct FFTMod3 : IStaticMod { public uint Mod => 469762049; public bool IsPrime => true; } public static long PowMod(long x, long n, int m) { Debug.Assert(0 <= n && 1 <= m); if (m == 1) return 0; Barrett barrett = new Barrett((uint)m); uint r = 1, y = (uint)InternalMath.SafeMod(x, m); while (0 < n) { if ((n & 1) != 0) r = barrett.Mul(r, y); y = barrett.Mul(y, y); n >>= 1; } return r; } public static long InvMod(long x, long m) { Debug.Assert(1 <= m); var (g, res) = InternalMath.InvGCD(x, m); Debug.Assert(g == 1); return res; } public static (long, long) CRT(long[] r, long[] m) { Debug.Assert(r.Length == m.Length); long r0 = 0, m0 = 1; for (int i = 0; i < m.Length; i++) { Debug.Assert(1 <= m[i]); long r1 = InternalMath.SafeMod(r[i], m[i]); long m1 = m[i]; if (m0 < m1) { (r0, r1) = (r1, r0); (m0, m1) = (m1, m0); } if (m0 % m1 == 0) { if (r0 % m1 != r1) return (0, 0); continue; } var (g, im) = InternalMath.InvGCD(m0, m1); long u1 = (m1 / g); if ((r1 - r0) % g != 0) return (0, 0); long x = (r1 - r0) / g % u1 * im % u1; r0 += x * m0; m0 *= u1; if (r0 < 0) r0 += m0; } return (r0, m0); } public static long FloorSum(long n, long m, long a, long b) { long ans = 0; while (true) { if (a >= m) { ans += (n - 1) * n * (a / m) / 2; a %= m; } if (b >= m) { ans += n * (b / m); b %= m; } long yMax = (a * n + b) / m; long xMax = yMax * m - b; if (yMax == 0) return ans; ans += (n - (xMax + a - 1) / a) * yMax; (n, m, a, b) = (yMax, a, m, (a - xMax % a) % a); } } } }
namespace AtCoder.Internal { public static class Butterfly<T> where T : struct, IStaticMod { internal static readonly StaticModInt<T>[] sumE = CalcurateSumE(); internal static readonly StaticModInt<T>[] sumIE = CalcurateSumIE(); [MethodImpl(MethodImplOptions.AggressiveOptimization)] public static void Calculate(Span<StaticModInt<T>> a) { CheckPow2(a.Length); var n = a.Length; var h = InternalBit.CeilPow2(n); var regLength = Vector<uint>.Count; var modV = new Vector<uint>(default(T).Mod); for (int ph = 1; ph <= h; ph++) { int w = 1 << (ph - 1); int p = 1 << (h - ph); var now = StaticModInt<T>.Raw(1); for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); var ls = a.Slice(offset, p); var rs = a.Slice(offset + p, p); if (p < regLength) { for (int i = 0; i < p; i++) { var l = ls[i]; var r = rs[i] * now; ls[i] = l + r; rs[i] = l - r; } } else { foreach (ref var r in rs) { r *= now; } var lu = MemoryMarshal.Cast<StaticModInt<T>, uint>(ls); var ru = MemoryMarshal.Cast<StaticModInt<T>, uint>(rs); for (int i = 0; i < lu.Length; i += regLength) { var luSliced = lu.Slice(i); var ruSliced = ru.Slice(i); var u = new Vector<uint>(luSliced); var v = new Vector<uint>(ruSliced); var add = u + v; var sub = u - v; var ge = Vector.GreaterThanOrEqual(add, modV); add = Vector.ConditionalSelect(ge, add - modV, add); ge = Vector.GreaterThanOrEqual(sub, modV); sub = Vector.ConditionalSelect(ge, sub + modV, sub); add.CopyTo(luSliced); sub.CopyTo(ruSliced); } } now *= sumE[InternalBit.BSF(~(uint)s)]; } } } [MethodImpl(MethodImplOptions.AggressiveOptimization)] public static void CalculateInv(Span<StaticModInt<T>> a) { CheckPow2(a.Length); var n = a.Length; var h = InternalBit.CeilPow2(n); var regLength = Vector<uint>.Count; var modV = new Vector<uint>(default(T).Mod); for (int ph = h; ph >= 1; ph--) { int w = 1 << (ph - 1); int p = 1 << (h - ph); var iNow = StaticModInt<T>.Raw(1); for (int s = 0; s < w; s++) { int offset = s << (h - ph + 1); var ls = a.Slice(offset, p); var rs = a.Slice(offset + p, p); if (p < regLength) { for (int i = 0; i < p; i++) { var l = ls[i]; var r = rs[i]; ls[i] = l + r; rs[i] = StaticModInt<T>.Raw( (int)((ulong)(default(T).Mod + l.Value - r.Value) * (ulong)iNow.Value % default(T).Mod)); } } else { var lu = MemoryMarshal.Cast<StaticModInt<T>, uint>(ls); var ru = MemoryMarshal.Cast<StaticModInt<T>, uint>(rs); for (int i = 0; i < lu.Length; i += regLength) { var luSliced = lu.Slice(i); var ruSliced = ru.Slice(i); var u = new Vector<uint>(luSliced); var v = new Vector<uint>(ruSliced); var add = u + v; var sub = u - v; var ge = Vector.GreaterThanOrEqual(add, modV); add = Vector.ConditionalSelect(ge, add - modV, add); sub += modV; add.CopyTo(luSliced); sub.CopyTo(ruSliced); } foreach (ref var r in rs) { r *= iNow; } } iNow *= sumIE[InternalBit.BSF(~(uint)s)]; } } } private static StaticModInt<T>[] CalcurateSumE() { int g = InternalMath.PrimitiveRoot((int)default(T).Mod); int cnt2 = InternalBit.BSF(default(T).Mod - 1); var e = new StaticModInt<T>(g).Pow((default(T).Mod - 1) >> cnt2); var ie = e.Inv(); var sumE = new StaticModInt<T>[30]; Span<StaticModInt<T>> es = stackalloc StaticModInt<T>[cnt2 - 1]; Span<StaticModInt<T>> ies = stackalloc StaticModInt<T>[cnt2 - 1]; for (int i = es.Length - 1; i >= 0; i--) { es[i] = e; ies[i] = ie; e *= e; ie *= ie; } var now = StaticModInt<T>.Raw(1); for (int i = 0; i <= cnt2 - 2; i++) { sumE[i] = es[i] * now; now *= ies[i]; } return sumE; } private static StaticModInt<T>[] CalcurateSumIE() { int g = InternalMath.PrimitiveRoot((int)default(T).Mod); int cnt2 = InternalBit.BSF(default(T).Mod - 1); var e = new StaticModInt<T>(g).Pow((default(T).Mod - 1) >> cnt2); var ie = e.Inv(); var sumIE = new StaticModInt<T>[30]; Span<StaticModInt<T>> es = stackalloc StaticModInt<T>[cnt2 - 1]; Span<StaticModInt<T>> ies = stackalloc StaticModInt<T>[cnt2 - 1]; for (int i = es.Length - 1; i >= 0; i--) { es[i] = e; ies[i] = ie; e *= e; ie *= ie; } var now = StaticModInt<T>.Raw(1); for (int i = 0; i <= cnt2 - 2; i++) { sumIE[i] = ies[i] * now; now *= es[i]; } return sumIE; } [Conditional("DEBUG")] private static void CheckPow2(int n) { if (BitOperations.PopCount((uint)n) != 1) { throw new ArgumentException("配列長は2のべき乗でなければなりません。"); } } } }
#endregion Expanded