結果
問題 | No.2351 Butterfly in Summer |
ユーザー | ユヅキ |
提出日時 | 2023-06-18 10:21:17 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 24,417 bytes |
コンパイル時間 | 2,534 ms |
コンパイル使用メモリ | 121,872 KB |
実行使用メモリ | 18,176 KB |
最終ジャッジ日時 | 2024-06-25 23:10:10 |
合計ジャッジ時間 | 3,122 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 26 ms
18,048 KB |
testcase_01 | AC | 26 ms
18,176 KB |
testcase_02 | AC | 26 ms
18,048 KB |
testcase_03 | AC | 26 ms
17,792 KB |
testcase_04 | AC | 27 ms
17,920 KB |
testcase_05 | AC | 27 ms
17,920 KB |
testcase_06 | AC | 26 ms
17,792 KB |
testcase_07 | AC | 26 ms
18,048 KB |
testcase_08 | AC | 25 ms
17,920 KB |
testcase_09 | AC | 26 ms
18,176 KB |
testcase_10 | AC | 25 ms
17,920 KB |
testcase_11 | AC | 26 ms
17,792 KB |
testcase_12 | AC | 26 ms
18,048 KB |
testcase_13 | AC | 25 ms
18,176 KB |
testcase_14 | AC | 26 ms
17,920 KB |
testcase_15 | AC | 25 ms
17,792 KB |
testcase_16 | AC | 26 ms
18,048 KB |
testcase_17 | AC | 26 ms
18,176 KB |
testcase_18 | AC | 26 ms
18,048 KB |
testcase_19 | AC | 26 ms
17,536 KB |
testcase_20 | AC | 27 ms
18,048 KB |
testcase_21 | AC | 25 ms
17,792 KB |
testcase_22 | AC | 26 ms
18,176 KB |
testcase_23 | AC | 26 ms
18,176 KB |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using System.IO; using System.Threading.Tasks; using static System.Console; using static System.Math; using P=System.Tuple<long,long>; namespace Tasks{ public class Program{ public static void Main(string[] args){ var sw = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false}; Console.SetOut(sw); new Program().Solve(new ConsoleInput(Console.In, ' ')); Console.Out.Flush(); } public void Solve(ConsoleInput cin){ long N=cin.nextlong,K=cin.nextlong; const long mod=998244353; long a=((K*(K-1))%mod*N)%mod; long b=modpow(K,N,mod); long ans=a*modinv(b,mod); ans%=mod; Out(ans); } public List<List<int>> graph(int n,int m,bool edge=false){ List<List<int>> g=new List<List<int>>(); for(int i=0;i<n;++i) g.Add(new List<int>()); for(int i=0;i<m;++i){ var cin =new ConsoleInput(Console.In, ' '); int u=cin.nextint-1,v=cin.nextint-1; g[u].Add(v); if(!edge) g[v].Add(u); } return g; } public static bool inrange(int y, int x, int h, int w) { return 0 <= x && x < w && 0 <= y && y < h; } public static void Out<T>(params T[] A){ int n=A.Length; for(int i=0;i<n;++i){ if(i!=n-1){ if(typeof(T)==typeof(double)){ Write("{0:f12}",A[i]); Write(" "); } else Write(A[i]+" "); } else{ if(typeof(T)==typeof(double)){ WriteLine("{0:f12}",A[i]); } else WriteLine(A[i]); } } } public static void Out(){WriteLine();} public static void Yes(bool ok) => Console.WriteLine(ok ? "Yes": "No"); public static void YES(bool ok) => Console.WriteLine(ok ? "YES": "NO"); static void chmax(ref long m, long v, long mod = -1) { m = Math.Max(m, v); if (mod != -1) m %= mod; } static void chmax(ref int m, int v) { m = Math.Max(m, v);} static void chmin(ref long m, long v, long mod = -1) { m = Math.Min(m, v); if (mod != -1) m %= mod; } static void chmin(ref int m, int v) { m = Math.Min(m, v);} static void swap<T>(ref T a, ref T b) { var w = a; a = b; b = w; } static void Fill<T>(T[] array, T x) { for (int i = 0; i < array.Length; i++) { array[i] = x; } } static void Fill<T>(T[,] array, T x) { for (int i = 0; i < array.GetLength(0); i++){ for (int j = 0; j < array.GetLength(1); j++) array[i, j] = x; } } static void Showarray<T>(T[,] array){ for(int i=0;i<array.GetLength(0);i++){ for(int j=0;j<array.GetLength(1);j++){ Write(array[i,j]+" "); } WriteLine(); } } static T[,] Rotatearray<T>(T[,] array) { int h=array.GetLength(0); int w=array.GetLength(1); var array2 = new T[w,h]; for (int i = 0; i < h; i++)for (int j = 0; j < w; j++){ array2[j,h - i - 1] = array[i, j]; } return array2; } public static void OutAllLine<T>(IEnumerable<T> items) { var sb = new StringBuilder(); foreach (T result in items) { sb.Append(result + "\n"); } sb = sb.Remove(sb.Length - 1, 1); Console.WriteLine(sb); } public static void OutEachSpace<T>(IEnumerable<T> items) { var sb = new StringBuilder(); foreach (T result in items) { sb.Append(result + " "); } sb = sb.Remove(sb.Length - 1, 1); Console.WriteLine(sb); } static List<T[]> AllPermutation<T>(params T[] array) where T : IComparable { var a = new List<T>(array).ToArray(); var res = new List<T[]>(); res.Add(new List<T>(a).ToArray()); var n = a.Length; var next = true; while (next) { next = false; int i; for (i = n - 2; i >= 0; i--) { if (a[i].CompareTo(a[i + 1]) < 0) break; } if (i < 0) break; var j = n; do { j--; } while (a[i].CompareTo(a[j]) > 0); if (a[i].CompareTo(a[j]) < 0) { var tmp = a[i]; a[i] = a[j]; a[j] = tmp; Array.Reverse(a, i + 1, n - i - 1); res.Add(new List<T>(a).ToArray()); next = true; } } return res; } public static T max<T>(params T[] A) where T : IComparable { int n=A.Length; T max=A[0]; for(int i=1;i<n;++i){ max=max.CompareTo(A[i]) > 0 ? max:A[i]; } return max; } public static T min<T>(params T[] A) where T : IComparable { int n=A.Length; T min=A[0]; for(int i=1;i<n;++i){ min=min.CompareTo(A[i]) < 0 ? min:A[i]; } return min; } static long pow(long a,long n){ long ret=1; while(n>0){ if((n&1)>0) ret*=a; a=a*a; n>>=1; } return ret; } static long modpow(long a,long n, long mod){ long ret=1; while(n>0){ if((n&1)>0) ret=ret*a%mod; a=a*a%mod; n>>=1; } return ret; } public static long modinv( long a, long mod ){ return modpow(a,mod-2,mod); } static long Lcm(long a, long b){return a / Gcd(a, b) * b;} static long Gcd(long m, long n){if (n == 0) return m;return Gcd(n, m % n);} public static int LowerBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer) { int low = start; int high = end; int mid; while (low < high) { mid = ((high - low) >> 1) + low; if (comparer.Compare(arr[mid], value) < 0) low = mid + 1; else high = mid; } return low; } public static int LowerBound<T>(T[] arr, T value) where T : IComparable { return LowerBound(arr, 0, arr.Length, value, Comparer<T>.Default); } public static int UpperBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer) { int low = start; int high = end; int mid; while (low < high) { mid = ((high - low) >> 1) + low; if (comparer.Compare(arr[mid], value) <= 0) low = mid + 1; else high = mid; } return low; } public static int UpperBound<T>(T[] arr, T value) { return UpperBound(arr, 0, arr.Length, value, Comparer<T>.Default); } public static Dictionary<long, long> PrimeFactorization(long n) { var result = new Dictionary<long, long>(); for (long i = 2; i * i <= n; i++) { if (n % i != 0) continue; long exponents = 0; while (n % i == 0) { exponents++; n /= i; } result[i] = exponents; } if (n != 1) result[n] = 1; return result; } public static bool Isprime(long num) { if (num < 2) { return false; } if (num == 2) { return true; } if (num % 2 == 0) { return false; } double sqrtNum = Math.Sqrt(num); for (int i = 3; i <= sqrtNum; i += 2) { if (num % i == 0) { return false; } } return true; } public static long[] GetDivisors(long n) { HashSet<long> divisors = new HashSet<long>(); for (long i = 1; i * i <= n; i++) { if (n % i != 0) { continue; } divisors.Add(i); divisors.Add(n / i); } return divisors.OrderBy(x => x).ToArray(); } public static bool[] PrimeTable(int n) { var prime = new bool[n + 1]; for(int i=0;i<=n;i++) prime[i]=true; if (n >= 0) prime[0] = false; if (n >= 1) prime[1] = false; for (int i = 2; i * i <= n; i++){ if (!prime[i]) continue; for (int j = i * i; j <= n; j += i) prime[j] = false; } return prime; } static int lis(int[] a){ const int inf=(1<<30); int n=a.Length; int[] dp=new int[n+1]; Fill(dp,inf); for(int i=0;i<n;++i){ int idx=LowerBound(dp,a[i]); dp[idx]=a[i]; } int ret=LowerBound(dp,inf); return ret; } static int[,] lcs(char[] s,char[] t){ int n=s.Length,m=t.Length; int[,] dp=new int[n+1,m+1]; for(int i=0;i<n;++i){ for(int j=0;j<m;++j){ if(s[i]==t[j]) dp[i+1,j+1]=dp[i,j]+1; else dp[i+1,j+1]=max(dp[i+1,j],dp[i,j+1]); } } return dp; } static long inversionnum(int[] array){ int n=array.Length; if(n==0) return 0; int[] copy=new int[n]; Array.Copy(array,copy,n); Array.Sort(copy); int[] bit=new int[n+1]; long ans=((long)n*(n-1)) >> 1; for(int i=0;i<n;++i){ int min=0,max=n; int comp=array[i]; while(max-min>1){ int mid=(min+max) >> 1; if(copy[mid]<=comp) min=mid; else max=mid; } for(int j=max; j>0;j-=j&-j) ans-=bit[j]; for(int j=max;j<n+1;j+=j&-j) ++bit[j]; } return ans; } } class Dikstra { public int N { get; } private List<Edge>[] _graph; public Dikstra(int n) { N = n; _graph = new List<Edge>[n]; for (int i = 0; i < n; i++) _graph[i] = new List<Edge>(); } public void Add(int a, int b, long cost = 1) => _graph[a].Add(new Edge(b, cost)); public long[] GetMinCost(int start) { var cost = new long[N]; for (int i = 0; i < N; i++) cost[i] = ((long)1<<60); cost[start] = 0; var q = new PriorityQueue<Vertex>(isDescending:false); q.Enqueue(new Vertex(start, 0)); while (q.Count > 0) { var v = q.Dequeue(); if (v.cost != cost[v.index]) continue; foreach (var e in _graph[v.index]) { if (cost[e.to] > v.cost + e.cost) { cost[e.to] = v.cost + e.cost; q.Enqueue(new Vertex(e.to, cost[e.to])); } } } return cost; } public struct Edge { public int to; public long cost; public Edge(int to, long cost) { this.to = to; this.cost = cost; } } public struct Vertex : IComparable<Vertex> { public int index; public long cost; public Vertex(int index, long cost) { this.index = index; this.cost = cost; } public int CompareTo(Vertex other) => cost.CompareTo(other.cost); } } class PriorityQueue<T> : IEnumerable<T> { private readonly List<T> _data = new List<T>(); private readonly IComparer<T> _comparer; private readonly bool _isDescending; public PriorityQueue(IComparer<T> comparer, bool isDescending = true) { _comparer = comparer; _isDescending = isDescending; } public PriorityQueue(Comparison<T> comparison, bool isDescending = true) : this(Comparer<T>.Create(comparison), isDescending) { } public PriorityQueue(bool isDescending = true) : this(Comparer<T>.Default, isDescending) { } public void Enqueue(T item) { _data.Add(item); var childIndex = _data.Count - 1; while (childIndex > 0) { var parentIndex = (childIndex - 1) / 2; if (Compare(_data[childIndex], _data[parentIndex]) >= 0) break; Swap(childIndex, parentIndex); childIndex = parentIndex; } } public T Dequeue() { var lastIndex = _data.Count - 1; var firstItem = _data[0]; _data[0] = _data[lastIndex]; _data.RemoveAt(lastIndex--); var parentIndex = 0; while (true) { var childIndex = parentIndex * 2 + 1; if (childIndex > lastIndex) break; var rightChild = childIndex + 1; if (rightChild <= lastIndex && Compare(_data[rightChild], _data[childIndex]) < 0) childIndex = rightChild; if (Compare(_data[parentIndex], _data[childIndex]) <= 0) break; Swap(parentIndex, childIndex); parentIndex = childIndex; } return firstItem; } public T Peek() { return _data[0]; } private void Swap(int a, int b) { var tmp = _data[a]; _data[a] = _data[b]; _data[b] = tmp; } private int Compare(T a, T b) { return _isDescending ? _comparer.Compare(b, a) : _comparer.Compare(a, b); } public int Count => _data.Count; public IEnumerator<T> GetEnumerator() { return _data.GetEnumerator(); } IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); } class UnionFind{ private int[] _unionfind; private int[] _unionfind_size; public UnionFind(int a){ _unionfind = new int[a]; _unionfind_size = new int[a]; for(int i=0;i<a;i++){ _unionfind[i] = i; _unionfind_size[i] = 1; } } public int Root(int x){ if(_unionfind[x] == x) return x; return _unionfind[x] = Root(_unionfind[x]); } public void Unite(int a,int b){ a = Root(a); b = Root(b); if(a == b) return; if(_unionfind_size[a] < _unionfind_size[b]){ int temp = a; a = b; b = temp; } _unionfind[b] = a; _unionfind_size[a] += _unionfind_size[b]; } public bool Same(int a,int b){ return Root(a) == Root(b); } public int Size(int x){ return _unionfind_size[Root(x)]; } } public class SegmentTree<T> { public int N { get; private set; } private T[] _tree; private readonly Func<T, T, T> _updateMethod; private readonly T _initValue; public SegmentTree(IEnumerable<T> items, Func<T, T, T> updateMethod, T initValue) { T[] array = items.ToArray(); _updateMethod = updateMethod; _initValue = initValue; N = 1; while (N < array.Length) N *= 2; _tree = Enumerable.Repeat(initValue, 2 * N - 1).ToArray(); for (int i = 0; i < array.Length; i++) _tree[N + i - 1] = array[i]; for (int i = N - 2; i >= 0; i--) _tree[i] = _updateMethod(_tree[2 * i + 1], _tree[2 * i + 2]); } public void Update(int i, T x) { i = N + i - 1; _tree[i] = x; while(i > 0) { i = (i - 1) / 2; _tree[i] = _updateMethod(_tree[2 * i + 1], _tree[2 * i + 2]); } } public T Execute(int a, int b) => Execute(a, b, 0, 0, N); private T Execute(int a, int b, int k, int l, int r) { if (r <= a || b <= l) return _initValue; if (a <= l && r <= b) return _tree[k]; var vl = Execute(a, b, 2 * k + 1, l, (l + r) / 2); var vr = Execute(a, b, 2 * k + 2, (l + r) / 2, r); return _updateMethod(vl, vr); } } class Deque<T> : IEnumerable<T> { public T this[int i] { get { return this.Buffer[(this.FirstIndex + i) % this.Capacity]; } set { if (i < 0) throw new ArgumentOutOfRangeException(); this.Buffer[(this.FirstIndex + i) % this.Capacity] = value; } } private T[] Buffer; private int Capacity; private int FirstIndex; private int LastIndex { get { return (this.FirstIndex + this.Length) % this.Capacity; } } public int Length; public Deque(int capacity = 16) { this.Capacity = capacity; this.Buffer = new T[this.Capacity]; this.FirstIndex = 0; } public void PushBack(T data) { if (this.Length == this.Capacity) this.Resize(); this.Buffer[this.LastIndex] = data; this.Length++; } public void PushFront(T data) { if (this.Length == this.Capacity) this.Resize(); var index = this.FirstIndex - 1; if (index < 0) index = this.Capacity - 1; this.Buffer[index] = data; this.Length++; this.FirstIndex = index; } public T PopBack() { if (this.Length == 0) throw new InvalidOperationException("There is no data available."); var data = this[this.Length - 1]; this.Length--; return data; } public T PopFront() { if (this.Length == 0) throw new InvalidOperationException("There is no data available."); var data = this[0]; this.FirstIndex++; this.FirstIndex %= this.Capacity; this.Length--; return data; } private void Resize() { var newArray = new T[this.Capacity * 2]; for (int i = 0; i < this.Length; i++) { newArray[i] = this[i]; } this.FirstIndex = 0; this.Capacity *= 2; this.Buffer = newArray; } public IEnumerator<T> GetEnumerator() { for (int i = 0; i < this.Length; i++) { yield return this[i]; } } IEnumerator IEnumerable.GetEnumerator() { for (int i = 0; i < this.Length; i++) { yield return this[i]; } } } public class ConsoleInput { private readonly System.IO.TextReader _stream; private char _separator = ' '; private Queue<string> inputStream; public ConsoleInput(System.IO.TextReader stream, char separator = ' ') { this._separator = separator; this._stream = stream; inputStream = new Queue<string>(); } public string Read { get { if (inputStream.Count != 0) return inputStream.Dequeue(); string[] tmp = _stream.ReadLine().Split(_separator); for (int i = 0; i < tmp.Length; ++i) inputStream.Enqueue(tmp[i]); return inputStream.Dequeue(); } } public string next { get { return _stream.ReadLine(); }} public int nextint { get { return int.Parse(Read); }} public long nextlong { get { return long.Parse(Read); }} public double nextdouble { get { return double.Parse(Read); }} public string[] strarray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;} public int[] intarray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = nextint; return ret;} public long[] longarray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = nextlong; return ret;} public int[,] intarray2(long h,long w){ var ret=new int[h,w]; for(long i=0;i<h;++i) { int[] tmparray=intarray(w); for(long j=0;j<w;++j) ret[i,j]=tmparray[j]; } return ret; } public long[,] longarray2(long h,long w){ var ret=new long[h,w]; for(long i=0;i<h;++i) { long[] tmparray=longarray(w); for(long j=0;j<w;++j) ret[i,j]=tmparray[j]; } return ret; } public char[] chararray(long N){var ret=new char[N]; string tmp=next;for(int i=0;i<N;++i) ret[i]=tmp[i]; return ret;} public char[,] chararray2(long h,long w){ var ret=new char[h,w]; for(int i=0;i<h;++i){ char[] tmparray=chararray(w); for(int j=0;j<w;++j) ret[i,j]=tmparray[j]; } return ret; } public void array2(long[] A,long[] B){ int n=A.Length; for(int i=0;i<n;++i){A[i]=nextlong;B[i]=nextlong;} } public void array2(int[] A, int[] B){ int n=A.Length; for(int i=0;i<n;++i){A[i]=nextint;B[i]=nextint;} } public void array3(long[] A,long[] B,long[] C){ int n=A.Length; for(int i=0;i<n;++i){A[i]=nextlong;B[i]=nextlong;C[i]=nextlong;} } public void array3(int[] A,int[] B,int[] C){ int n=A.Length; for(int i=0;i<n;++i){A[i]=nextint;B[i]=nextint;C[i]=nextint;} } } }