結果

問題 No.2053 12345...
ユーザー ayutakeayutake
提出日時 2025-01-14 23:32:27
言語 C#
(.NET 8.0.404)
結果
AC  
実行時間 164 ms / 2,000 ms
コード長 27,240 bytes
コンパイル時間 19,744 ms
コンパイル使用メモリ 174,924 KB
実行使用メモリ 246,168 KB
最終ジャッジ日時 2025-01-14 23:32:52
合計ジャッジ時間 15,210 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 31
権限があれば一括ダウンロードができます
コンパイルメッセージ
  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (97 ミリ秒)。
/home/judge/data/code/Main.cs(240,26): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(909,47): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
/home/judge/data/code/Main.cs(1029,59): warning CS8632: '#nullable' 注釈コンテキスト内のコードでのみ、Null 許容参照型の注釈を使用する必要があります。 [/home/judge/data/code/main.csproj]
  main -> /home/judge/data/code/bin/Release/net8.0/main.dll
  main -> /home/judge/data/code/bin/Release/net8.0/publish/

ソースコード

diff #
プレゼンテーションモードにする

using System;
using System.IO;
using System.Linq;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.IO.Compression;
using System.Dynamic;
using System.Runtime.CompilerServices;
using System.Diagnostics.CodeAnalysis;
using System.Numerics;
using ModInt = ModInt<ModInt998244353>;
class Runner
{
public void Run()
{
var N = IO.Read<int>();
var A = IO.ReadArray<long>(N);
long ans = 0;
foreach(var (d,l) in A.Zip(A.Skip(1),(x,y)=>y-x).RunLengthEncode())
{
if(d!=1) continue;
ans += ((long)l + 1) * l / 2;
}
IO.Write(ans);
}
}
class Program
{
static void Main()
{
try
{
var miiko = new Runner();
do
{
miiko.Run();
IO.Flush();
}
while(IO.HasNextInput);
}
catch
{
IO.Flush();
throw;
}
}
}
static class IO
{
private static readonly Queue<string> que;
static IO()
{
que = new Queue<string>();
var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
Console.SetOut(sw);
}
public static bool HasNextInput => que.Count > 0 || TryReadNextLine();
public static string Yes { get; set; } = "Yes";
public static string No { get; set; } = "No";
public static void Flush() => Console.Out.Flush();
public static T Read<T>()
{
if(que.Count <= 0 && !TryReadNextLine()) throw new InvalidOperationException("Input is missing.");
Func<string,T> converter =
(
typeof(T)==typeof(int) ? (Func<string,T>)(object)(new Func<string,int>(int.Parse)) :
typeof(T)==typeof(long) ? (Func<string,T>)(object)(new Func<string,long>(long.Parse)) :
typeof(T)==typeof(double) ? (Func<string,T>)(object)(new Func<string,double>(double.Parse)) :
typeof(T)==typeof(string) ? (Func<string,T>)(object)(new Func<string,string>(x => x)) :
typeof(T)==typeof(char) ? (Func<string,T>)(object)(new Func<string,char>(x => x[0])) :
null
) ?? throw new InvalidOperationException($"{nameof(T)} is not supported.");
return converter.Invoke(que.Dequeue());
}
public static (T1,T2) Read<T1,T2>() => (Read<T1>(), Read<T2>());
public static (T1,T2,T3) Read<T1,T2,T3>() => (Read<T1>(), Read<T2>(), Read<T3>());
public static (T1,T2,T3,T4) Read<T1,T2,T3,T4>() => (Read<T1>(), Read<T2>(), Read<T3>(), Read<T4>());
public static (T1,T2,T3,T4,T5) Read<T1,T2,T3,T4,T5>() => (Read<T1>(), Read<T2>(), Read<T3>(), Read<T4>(), Read<T5>());
public static (T1,T2,T3,T4,T5,T6) Read<T1,T2,T3,T4,T5,T6>() => (Read<T1>(), Read<T2>(), Read<T3>(), Read<T4>(), Read<T5>(), Read<T6>());
public static T1[] ReadArray<T1>(int len)
{
var A1 = new T1[len];
for(int i=0; i<len; i++) A1[i] = Read<T1>();
return A1;
}
public static (T1[],T2[]) ReadArray<T1,T2>(int len)
{
var (A1,A2) = (new T1[len], new T2[len]);
for(int i=0; i<len; i++) (A1[i],A2[i]) = Read<T1,T2>();
return (A1,A2);
}
public static (T1[],T2[],T3[]) ReadArray<T1,T2,T3>(int len)
{
var (A1,A2,A3) = (new T1[len], new T2[len], new T3[len]);
for(int i=0; i<len; i++) (A1[i],A2[i],A3[i]) = Read<T1,T2,T3>();
return (A1,A2,A3);
}
public static (T1[],T2[],T3[],T4[]) ReadArray<T1,T2,T3,T4>(int len)
{
var (A1,A2,A3,A4) = (new T1[len], new T2[len], new T3[len], new T4[len]);
for(int i=0; i<len; i++) (A1[i],A2[i],A3[i],A4[i]) = Read<T1,T2,T3,T4>();
return (A1,A2,A3,A4);
}
public static (T1[],T2[],T3[],T4[],T5[]) ReadArray<T1,T2,T3,T4,T5>(int len)
{
var (A1,A2,A3,A4,A5) = (new T1[len], new T2[len], new T3[len], new T4[len], new T5[len]);
for(int i=0; i<len; i++) (A1[i],A2[i],A3[i],A4[i],A5[i]) = Read<T1,T2,T3,T4,T5>();
return (A1,A2,A3,A4,A5);
}
public static (T1[],T2[],T3[],T4[],T5[],T6[]) ReadArray<T1,T2,T3,T4,T5,T6>(int len)
{
var (A1,A2,A3,A4,A5,A6) = (new T1[len], new T2[len], new T3[len], new T4[len], new T5[len], new T6[len]);
for(int i=0; i<len; i++) (A1[i],A2[i],A3[i],A4[i],A5[i],A6[i]) = Read<T1,T2,T3,T4,T5,T6>();
return (A1,A2,A3,A4,A5,A6);
}
public static T[,] ReadMatrix<T>(int row, int col)
{
var A = new T[row,col];
for(int r=0; r<row; r++) for(int c=0; c<col; c++) A[r,c] = Read<T>();
return A;
}
public static HashSet<int>[] ReadGraph(int N, int M, bool isDirected = false)
{
var G = Enumerable.Repeat(0,N).Select(x=>new HashSet<int>()).ToArray();
while(M-->0)
{
var (u,v) = IO.Read<int,int>();
u--; v--;
G[u].Add(v);
if(!isDirected) G[v].Add(u);
}
return G;
}
public static Dictionary<int,long>[] ReadWeightedGraph(int N, int M)
{
var G = Enumerable.Repeat(0,N).Select(x=>new Dictionary<int,long>()).ToArray();
while(M-->0)
{
var (u,v,w) = IO.Read<int,int,long>();
u--; v--;
G[u].TryAdd(v,long.MaxValue);
G[u][v] = Math.Min(G[u][v],w);
}
return G;
}
public static void Write<T>(T val) => Console.WriteLine(val.ToStringOrYesNo());
public static void Write<T1,T2>(T1 v1, T2 v2)
{
Console.Write(v1.ToStringOrYesNo()); Console.Write(' '); Write(v2);
}
public static void Write<T1,T2,T3>(T1 v1, T2 v2, T3 v3)
{
Console.Write(v1.ToStringOrYesNo()); Console.Write(' '); Write(v2, v3);
}
public static void Write<T1,T2,T3,T4>(T1 v1, T2 v2, T3 v3, T4 v4)
{
Console.Write(v1.ToStringOrYesNo()); Console.Write(' '); Write(v2, v3, v4);
}
public static void Write<T1,T2,T3,T4,T5>(T1 v1, T2 v2, T3 v3, T4 v4, T5 v5)
{
Console.Write(v1.ToStringOrYesNo()); Console.Write(' '); Write(v2, v3, v4, v5);
}
public static void Write<T1,T2,T3,T4,T5,T6>(T1 v1, T2 v2, T3 v3, T4 v4, T5 v5, T6 v6)
{
Console.Write(v1.ToStringOrYesNo()); Console.Write(' '); Write(v2, v3, v4, v5, v6);
}
public static void WriteArray<T>(IEnumerable<T> vals, bool isMultiLine = false)
{
if(!vals.Any())
{
Console.WriteLine();
return;
}
Console.Write(vals.First().ToStringOrYesNo());
foreach(var val in vals.Skip(1))
{
if(isMultiLine)
{
Console.WriteLine();
}
else
{
Console.Write(' ');
}
Console.Write(val.ToStringOrYesNo());
}
Console.WriteLine();
}
public static void WriteMatrix<T>(T[,] matrix)
{
var row = matrix.GetLength(0);
var col = matrix.GetLength(1);
for(int r=0; r<row; r++)
{
Console.Write(matrix[r,0].ToStringOrYesNo());
for(int c=1; c<col; c++)
{
Console.Write(' ');
Console.Write(matrix[r,c].ToStringOrYesNo());
}
Console.WriteLine();
}
}
private static bool TryReadNextLine()
{
var line = Console.ReadLine();
if(line == null) return false;
foreach(var x in line.Split(' '))
{
if(!string.IsNullOrEmpty(x)) que.Enqueue(x);
}
return que.Count > 0;
}
private static string? ToStringOrYesNo<T>(this T val)
{
return typeof(T) == typeof(bool) ? Convert.ToBoolean(val) ? Yes : No : val?.ToString();
}
}
struct PrimeFactor
{
public long Prime { get; set; }
public int Exponent { get; set; }
public PrimeFactor(long p, int e)
{
Prime = p;
Exponent = e;
}
public override readonly string ToString()
{
return $"[{Prime},{Exponent}]";
}
}
static class MathEx
{
public static long Pow(long x, long n, long mod = -1)
{
if(mod > 0) x %= mod;
if(x == 0) return n==0 ? mod==1 ? 0 : 1 : 0;
long ret = 1;
while (n > 0)
{
if (n%2 == 1)
{
ret *= x;
if(mod > 0) ret %= mod;
}
n = n / 2;
if(n == 0) break;
x *= x;
if(mod > 0) x %= mod;
}
return ret;
}
public static long Pow(long x, int n, long mod = -1) => Pow(x, (long)n, mod);
public static long ModInv(long x, long mod)
{
long y = mod;
long u = 1;
long v = 0;
while(y>0)
{
var t = x / y;
x -= t * y;
(x,y) = (y,x);
u -= t * v;
(u,v) = (v,u);
}
u %= mod;
if(u<0) u += mod;
return u;
}
public static long Gcd(long m, long n)
{
var M = Math.Max(m,n);
var N = Math.Min(m,n);
while(true)
{
var mod = M%N;
if(mod==0) return N;
M = N;
N = mod;
}
}
public static long Lcm(long m, long n) => m / Gcd(m,n) * n;
public static string Convert10toStr2(long n)
{
var s = new StringBuilder();
do
{
s.Insert(0, n % 2);
n = n / 2;
}
while(n > 0);
return s.ToString();
}
public static long ConvertStr2to10(string s)
{
int len = s.Length;
long ret = 0;
for(int i=0; i<len; i++)
{
ret += int.Parse(s[len-i-1].ToString()) * Pow(2, i);
}
return ret;
}
public static IEnumerable<List<T>> NextPermutation<T>(IEnumerable<T> v) where T : IComparable
{
var list = v.ToList();
int len = list.Count;
yield return list;
while(true)
{
int l = len-2;
while(l>=0 && list[l].CompareTo(list[l+1])>=0) l--;
if(l<0) break;
int r = len-1;
while(list[l].CompareTo(list[r])>0) r--;
if(list[l].CompareTo(list[r])>=0) break;
var tmp = list[l];
list[l] = list[r];
list[r] = tmp;
list.Reverse(l+1,len-l-1);
yield return list;
}
}
public static bool IsCross (
long ax, long ay, long bx, long by,
long cx, long cy, long dx, long dy
) {
bool crs = true;
crs &= ((bx-ax)*(cy-ay)-(cx-ax)*(by-ay)) * ((bx-ax)*(dy-ay)-(dx-ax)*(by-ay)) < 0;
crs &= ((dx-cx)*(ay-cy)-(ax-cx)*(dy-cy)) * ((dx-cx)*(by-cy)-(bx-cx)*(dy-cy)) < 0;
return crs;
}
public static long[,] MatrixProduct(long[,] a, long[,] b, long mod = -1)
{
var ha = a.GetLength(0);
var wa = a.GetLength(1);
var hb = b.GetLength(0);
var wb = b.GetLength(1);
if(wa!=hb) throw new ArgumentException();
var c = new long[ha,wb];
for(int i=0; i<ha; i++) for(int j=0; j<wb; j++) for(int k=0; k<wa; k++)
{
if(mod>0)
{
a[i,k] %= mod;
b[k,j] %= mod;
}
c[i,j] += a[i,k] * b[k,j];
if(mod>0) c[i,j] %= mod;
}
return c;
}
public static long[,] MatrixPow(long[,] a, long k, long mod = -1)
{
var n = a.GetLength(0);
if(n != a.GetLength(1)) throw new ArgumentException();
if(mod > 0) for(int i=0; i<n; i++) for(int j=0; j<n; j++) a[i,j] %= mod;
var ret = new long[n,n];
for(int i=0; i<n; i++) ret[i,i] = 1;
while (k > 0)
{
if (k%2 == 1)
{
ret = MatrixProduct(ret,a,mod);
}
k /= 2;
if(k == 0) break;
a = MatrixProduct(a,a,mod);
}
return ret;
}
public static long[,] MatrixPow(long[,] a, int k, long mod = -1) => MatrixPow(a,(long)k,mod);
public static bool IsPrime(long n)
{
if(n<2) return false;
for(long i=2; i*i<=n; i++)
{
if(n%i==0) return false;
}
return true;
}
public static IEnumerable<PrimeFactor> PrimeFactorization(long n)
{
if(n<2) yield break;
for(long i=2; i*i<=n; i++)
{
var e = 0;
while(n%i==0)
{
n /= i;
e++;
}
if(e>0) yield return new PrimeFactor(i,e);
}
if(n>1) yield return new PrimeFactor(n,1);
}
}
static class Ex
{
public static string ToReverseString(this string s) => new string(s.ToString().Reverse().ToArray());
public static T[] Row<T>(this T[,] array, int row)
{
int len = array.GetLength(1);
var ret = new T[len];
for(int c=0; c<len; c++)
{
ret[c] = array[row,c];
}
return ret;
}
public static T[] Column<T>(this T[,] array, int column)
{
int len = array.GetLength(0);
var ret = new T[len];
for(int r=0; r<len; r++)
{
ret[r] = array[r,column];
}
return ret;
}
public static int MgrBinarySearch(int ok, int ng, Func<int,bool> predicate)
=> MgrBinarySearchBase(ok,ng,(x,y)=>(x+y)/2,(x,y)=>Math.Abs(x-y)>1,predicate);
public static long MgrBinarySearch(long ok, long ng, Func<long,bool> predicate)
=> MgrBinarySearchBase(ok,ng,(x,y)=>(x+y)/2,(x,y)=>Math.Abs(x-y)>1,predicate);
public static double MgrBinarySearch(double ok, double ng, Func<double,bool> predicate, int maxLoopCount = 100)
=> MgrBinarySearchBase(ok,ng,(x,y)=>(x+y)/2,(x,y)=>maxLoopCount-->0,predicate);
public static bool ChangeMax<T>(ref this T current, T other) where T : struct, IComparable
{
bool changed = false;
if(current.CompareTo(other) < 0)
{
current = other;
changed = true;
}
return changed;
}
public static bool ChangeMin<T>(ref this T current, T other) where T : struct, IComparable
{
bool changed = false;
if(current.CompareTo(other) > 0)
{
current = other;
changed = true;
}
return changed;
}
public static IEnumerable<(T Value, int Length)> RunLengthEncode<T>(this IEnumerable<T> A) where T : IComparable
{
var nv = A.First();
var nl = 1;
foreach(var v in A.Skip(1))
{
if(nv.CompareTo(v)==0)
{
nl++;
}
else
{
yield return (nv,nl);
nv = v;
nl = 1;
}
}
yield return (nv,nl);
}
public static bool Contains<T>(this (T,T) lr, T x) where T : IComparable<T>
{
var l = lr.Item1;
var r = lr.Item2;
return l.CompareTo(x) <= 0 && x.CompareTo(r) < 0;
}
public static string AsString(this IEnumerable<char> C) => new string(C.ToArray());
private static T MgrBinarySearchBase<T>(T ok, T ng, Func<T,T,T> mid, Func<T,T,bool> loop, Func<T,bool> predicate)
{
while(loop(ok,ng))
{
var m = mid(ok,ng);
if(predicate(m))
{
ok = m;
}
else
{
ng = m;
}
}
return ok;
}
}
class UnionFind
{
private int[] _parent;
private int[] _size;
private int _groupCount;
public int GroupCount => _groupCount;
public UnionFind(int capacity)
{
_parent = new int[capacity];
_size = new int[capacity];
_groupCount = capacity;
for(int i=0; i<capacity; i++)
{
_parent[i] = i;
_size[i] = 1;
}
}
public int Root(int x)
{
if(_parent[x] != x)
{
_parent[x] = Root(_parent[x]);
}
return _parent[x];
}
public bool Same(int x, int y) => Root(x) == Root(y);
public void Unite(int x, int y)
{
x = Root(x);
y = Root(y);
if(x == y) return;
if(_size[x]<_size[y])
{
var tmp = x;
x = y;
y = tmp;
}
_size[x] += _size[y];
_parent[y] = x;
_groupCount -= 1;
}
public int Size(int x) => _size[Root(x)];
}
class SegmentTree<T>
{
private int _n;
private T[] _node;
private IEnumerable<T> _source;
private Func<T,T,T> _updater;
private T _e;
public SegmentTree(IEnumerable<T> source, Func<T,T,T> updater, T e)
{
_source = source;
_updater = updater;
_e = e;
var arr = _source.ToArray();
_n = 1;
while(_n<arr.Length) _n *= 2;
_node = Enumerable.Repeat(_e,_n*2-1).ToArray();
for(int i=0; i<arr.Length; i++) this.Update(i,arr[i]);
}
public T this[int i]
{
get { return _node[i + _n - 1]; }
set { this.Update(i,value); }
}
public void Update(int i, T val)
{
i += _n-1;
_node[i] = val;
while(i>0)
{
i = (i-1)/2;
_node[i] = _updater(_node[2*i+1],_node[2*i+2]);
}
}
public T Query(int a, int b) => this.Query(a,b,0,0,_n);
public T Query(int a, int b, int x, int l, int r)
{
if(b<=l||r<=a) return _e;
if(a<=l&&r<=b) return _node[x];
var vl = Query(a,b,x*2+1,l,(l+r)/2);
var vr = Query(a,b,x*2+2,(l+r)/2,r);
return _updater(vl,vr);
}
}
class LazySegmentTree<T,F>
{
private int _n;
private T[] _node;
private F[] _lazy;
private bool[] _hasLazy;
private T[] _source;
private Func<T,T,T> _op;
private T _e;
private Func<T,F,T> _mapping;
private Func<F,F,F> _composition;
private F _id;
public LazySegmentTree(IEnumerable<T> source, Func<T,T,T> op, T e, Func<T,F,T> mapping, Func<F,F,F> composition, F id)
{
_source = source.ToArray();
_op = op;
_e = e;
_mapping = mapping;
_composition = composition;
_id = id;
var sl = _source.Length;
_n = 1;
while(_n<sl) _n *= 2;
_node = Enumerable.Repeat(_e,_n*2-1).ToArray();
_lazy = Enumerable.Repeat(_id,_n*2-1).ToArray();
_hasLazy = new bool[_n*2-1];
for(int i=0; i<sl; i++) _node[_n+i-1] = _source[i];
for(int i=_n-2; i>=0; i--) _node[i] = _op(_node[i*2+1],_node[i*2+2]);
}
public T this[int i] { get => this[i,i+1]; }
public T this[int i, int j] { get => this.Query(i,j); }
public void Update(int a, F f) => this.Update(a,a+1,f);
public void Update(int a, int b, F f) => this.Update(a,b,f,0,0,_n);
public void Update(int a, int b, F f, int x, int l, int r)
{
this.Eval(x,l,r);
if(b<=l||r<=a) return;
if(a<=l&&r<=b)
{
_lazy[x] = _composition(_lazy[x],f);
_hasLazy[x] = true;
Eval(x,l,r);
}
else
{
this.Update(a,b,f,x*2+1,l,(l+r)/2);
this.Update(a,b,f,x*2+2,(l+r)/2,r);
_node[x] = _op(_node[x*2+1],_node[x*2+2]);
}
}
public T Query(int a, int b) => a==0 && b==_source.Length ? _node[0] : this.Query(a,b,0,0,_n);
public T Query(int a, int b, int x, int l, int r)
{
if(b<=l||r<=a) return _e;
this.Eval(x,l,r);
if(a<=l&&r<=b) return _node[x];
var vl = Query(a,b,x*2+1,l,(l+r)/2);
var vr = Query(a,b,x*2+2,(l+r)/2,r);
return _op(vl,vr);
}
private void Eval(int k, int l, int r)
{
if(!_hasLazy[k]) return;
_node[k] = _mapping(_node[k],_lazy[k]);
if(r-l>1)
{
for(int d=0; d<2; d++)
{
var nk = 2*k + 1 + d;
_lazy[nk] = _composition(_lazy[nk],_lazy[k]);
_hasLazy[nk] = true;
}
}
_lazy[k] = _id;
_hasLazy[k] = false;
}
}
class SimpleMultiSet<T> : IEnumerable<T> where T : notnull
{
private int _countTotal;
private SortedSet<T> _values;
private Dictionary<T,int> _count;
private bool _hasModifiedAfterStartedEnumeration;
public SimpleMultiSet()
{
_countTotal = 0;
_values = new SortedSet<T>();
_count = new Dictionary<T,int>();
}
public SimpleMultiSet(IEnumerable<T> collection) : this()
{
foreach(var v in collection) Add(v);
}
public int Count => _countTotal;
public T Max => _values.Max ?? throw new InvalidOperationException();
public T Min => _values.Min ?? throw new InvalidOperationException();
public bool Add(T v)
{
bool isNew = false;
if(!_count.ContainsKey(v))
{
isNew = true;
_count.Add(v,0);
_values.Add(v);
}
_count[v]++;
_countTotal++;
Modify();
return isNew;
}
public bool Remove(T v) => Remove(v, false);
public bool RemoveAll(T v) => Remove(v, true);
public bool Contains(T v) => _count.ContainsKey(v);
public T UpperOf(T v) => _values.GetViewBetween(v,this.Max).Min ?? throw new InvalidOperationException();
public T LowerOf(T v) => _values.GetViewBetween(this.Min,v).Max ?? throw new InvalidOperationException();
public IEnumerator<T> GetEnumerator()
{
_hasModifiedAfterStartedEnumeration = false;
foreach(var v in _values)
{
for(int i=0; i<_count[v]; i++)
{
yield return v;
if(_hasModifiedAfterStartedEnumeration)
{
throw new InvalidOperationException("Collection was modified.");
}
}
}
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
private bool Remove(T v, bool isAll)
{
if(!_count.TryGetValue(v, out int vc)) return false;
var c = isAll ? vc : 1;
_count[v] -= c;
_countTotal -= c;
if(_count[v]<=0)
{
_count.Remove(v);
_values.Remove(v);
}
Modify();
return true;
}
private void Modify()
{
_hasModifiedAfterStartedEnumeration = true;
}
}
class RollingHash
{
private string s;
private int n => s.Length;
private long b;
private long mod;
private long[] hash;
private long[] p;
public RollingHash(string s, long b, long mod)
{
this.s = s;
this.b = b;
this.mod = mod;
hash = new long[n+1];
p = new long[n+1];
p[0] = 1;
for(int i=0; i<n; i++)
{
hash[i+1] = (hash[i] * b % mod + (int)s[i]) % mod;
p[i+1] = p[i] * b % mod;
}
}
public long GetHash(int l, int r) => (hash[r] - (hash[l] * p[r-l] % mod) + mod) % mod;
public bool Equal(int l1, int r1, int l2, int r2) => (r1-l1)==(r2-l2) && GetHash(l1,r1)==GetHash(l2,r2);
}
class LinearSieve
{
private int N;
private Dictionary<int,int> minDivisor;
private List<int> primes;
public int Max => N;
public LinearSieve(long n, Func<long,bool>? target = null)
{
target ??= x => x <= n;
minDivisor = new();
primes = new();
minDivisor.Add(1,1);
for(int i=2; target(i); i++)
{
if(minDivisor.TryAdd(i,i))
{
primes.Add(i);
}
foreach(var p in primes)
{
if(!target((long)p * i)) break;
if(p > minDivisor[i]) break;
minDivisor.Add(p * i, p);
}
}
N = minDivisor.Count;
}
public IEnumerable<int> PrimeNumbers()
{
foreach(var p in primes) yield return p;
}
public bool IsPrime(int n)
{
AssertLinearSieveTarget(n);
return n > 1 && minDivisor[n] == n;
}
public IEnumerable<PrimeFactor> PrimeFactorization(int n)
{
AssertLinearSieveTarget(n);
var dic = new Dictionary<int,int>();
while(n > 1)
{
var p = minDivisor[n];
dic.TryAdd(p,0);
dic[p]++;
n /= p;
}
foreach(var (p,e) in dic) yield return new PrimeFactor(p,e);
}
private void AssertLinearSieveTarget(long n)
{
if(!(1 <= n && n <= N))
{
throw new Exception($"The target must be between 1 and {N}.");
}
}
}
interface IMod { public long Mod { get; } }
struct ModInt998244353 : IMod { public readonly long Mod => 998244353; }
struct ModInt1000000007 : IMod { public readonly long Mod => 1000000007; }
readonly struct ModInt<T> where T : struct, IMod
{
private static readonly T t = default;
private static readonly long mod = t.Mod;
internal readonly long _v;
public long Value => _v;
public static long Mod => mod;
public ModInt(long v)
{
if(v < 0 || mod <= v)
{
v %= mod;
if(v < 0) v += mod;
}
_v = v;
}
public static ModInt<T> operator +(ModInt<T> a) => a;
public static ModInt<T> operator +(ModInt<T> a, ModInt<T> b)
{
var v = a._v + b._v;
if(v >= mod)
{
v -= mod;
}
return new ModInt<T>(v);
}
public static ModInt<T> operator -(ModInt<T> a) => new(a._v >= 0 ? a._v : mod - a._v);
public static ModInt<T> operator -(ModInt<T> a, ModInt<T> b)
{
var v = a._v - b._v;
if(v < 0)
{
v += mod;
}
return new ModInt<T>(v);
}
public static ModInt<T> operator *(ModInt<T> a, ModInt<T> b) => new(a._v * b._v);
public static ModInt<T> operator /(ModInt<T> a, ModInt<T> b) => new(a._v * MathEx.ModInv(b._v, mod));
public static bool operator ==(ModInt<T> a, ModInt<T> b) => a._v == b._v;
public static bool operator !=(ModInt<T> a, ModInt<T> b) => !(a == b);
public static implicit operator ModInt<T>(int v) => new(v);
public static implicit operator ModInt<T>(long v) => new(v);
public ModInt<T> Pow(long k) => new(MathEx.Pow(_v, k, mod));
public override string ToString() => _v.ToString();
public override bool Equals([NotNullWhen(true)] object? obj)
{
if(obj is ModInt<T> m) return this == m;
if(obj is int i) return this == i;
if(obj is long l) return this == l;
return false;
}
public override int GetHashCode() => _v.GetHashCode();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0