結果
問題 |
No.3045 反復重み付き累積和
|
ユーザー |
![]() |
提出日時 | 2025-01-25 20:07:14 |
言語 | C# (.NET 8.0.404) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 17,187 bytes |
コンパイル時間 | 17,800 ms |
コンパイル使用メモリ | 171,592 KB |
実行使用メモリ | 120,028 KB |
最終ジャッジ日時 | 2025-01-28 11:38:20 |
合計ジャッジ時間 | 143,720 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 RE * 1 |
other | AC * 20 RE * 10 TLE * 7 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (94 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System.ComponentModel; using System.Diagnostics.CodeAnalysis; using System.Numerics; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using System.Collections; using System.Text; using System.Text.RegularExpressions; using System.Collections.Specialized; using System.Globalization; using System.Diagnostics; StreamWriter writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; //using StreamWriter writer = new StreamWriter(File.Open("turn.txt", FileMode.Create, FileAccess.ReadWrite)); Console.SetOut(writer); //using StreamReader reader = new StreamReader(File.Open("in.txt", FileMode.Open)); //Console.SetIn(reader); Solver.Solve(); Console.Out.Flush(); public static class Solver { private static readonly AtCoderIO cin = new AtCoderIO(); public static unsafe void Solve() { ModFactorialCache cache = new(1000000); int N = cin.Int(); int Q = cin.Int(); long[] A = new long[N + 1]; for (int i = 0; i < N; i++) { A[i + 1] = cin.Long(); } Convolution conv = new(998244353); for (int i = 0; i < Q; i++) { int q = cin.Int(); if (q == 1) { long k = cin.Long(); int x = cin.Int(); long[] factor = new long[N + 1]; for (int j = 0; j <= N; j++) { factor[j] = (cache.Combination(j + x - 1, x - 1) * ((ModInt)k).Power(j)).Raw(); } A = conv.CalcConvolution(A, factor); Array.Resize(ref A, N + 1); } else if (q == 2) { int x = cin.Int(); Console.WriteLine(A[x]); } } } } // modintの階乗とその逆元を前計算して高速化. // 前計算O(最大値). 階乗, 順列, 二項係数それぞれ定数時間. // Depends on: ModInt // @author Nauclhlt. public sealed class ModFactorialCache { private ModInt[] _factorial; private ModInt[] _inverseFactorial; // 階乗とその逆元を前計算する. // O(max) public ModFactorialCache(long max) { _factorial = new ModInt[max + 1]; _inverseFactorial = new ModInt[max + 1]; _factorial[0] = 1; _inverseFactorial[0] = ((ModInt)1).Inv(); for (long p = 1; p <= max; p++) { _factorial[p] = _factorial[p - 1] * p; _inverseFactorial[p] = _inverseFactorial[p - 1] * ((ModInt)p).Inv(); } } // 二項係数nCrを計算する. // O(1) public ModInt Combination(long n, long r) { return _factorial[n] * (_inverseFactorial[n - r] * _inverseFactorial[r]); } // 順列の個数nPrを計算する. // O(1) public ModInt Permutation(long n, long r) { return _factorial[n] * _inverseFactorial[n - r]; } // n!を計算する. // O(1) public ModInt Factorial(long n) { return _factorial[n]; } } public sealed class Convolution { private readonly long _mod; private readonly long _primitiveRoot; private readonly int _maxExp; private readonly long _factor; private long[] _root; private long[] _inverseRoot; public Convolution(long mod = 998244353L) { _mod = mod; _primitiveRoot = FindPrimitiveRoot(mod); _maxExp = 0; long mm = mod - 1; while ((mm & 1) == 0) { mm >>= 1; _maxExp++; } _factor = mm; _root = new long[_maxExp + 1]; _inverseRoot = new long[_maxExp + 1]; CalcRoot(_root); for (int i = 0; i <= _maxExp; i++) { _inverseRoot[i] = Inverse(_root[i], _mod); } } private static long Inverse(long a, long mod) { return CalcPow(a, mod - 2, mod); } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static long CalcPow(long b, long exp, long mod) { // if (exp == 0) return 1; // if (exp == 1) return b % mod; // long m = CalcPow(b, exp / 2L, mod); // m *= m; // m %= mod; // if (exp % 2L == 1) m *= b % mod; // m %= mod; // return m; b %= mod; long res = 1L; while (exp > 0) { if ((exp & 1L) == 1L) { res *= b; res %= mod; } b *= b; b %= mod; exp >>= 1; } return res; } private long FindPrimitiveRoot(long m) { if (m == 2) return 1; if (m == 167772161) return 3; if (m == 377487361) return 7; if (m == 469762049) return 3; if (m == 595591169) return 3; if (m == 645922817) return 3; if (m == 754974721) return 11; if (m == 880803841) return 26; if (m == 897581057) return 3; if (m == 998244353) return 3; List<long> divisors = new(); long m1 = m - 1; for (long i = 2; i * i <= m1; i++) { if (m1 % i == 0) { while (m1 % i == 0) m1 /= i; divisors.Add(i); } } if (m1 > 1) { divisors.Add(m1); } Span<long> divSpan = CollectionsMarshal.AsSpan(divisors); for (long g = 2; g <= m; g++) { bool ok = true; for (int i = 0; i < divSpan.Length; i++) { ok &= CalcPow(g, (m - 1) / divSpan[i], m) != 1L; } if (ok) { return g; } } return -1; } private void CalcRoot(long[] root) { root[0] = 1L; root[_maxExp] = CalcPow(_primitiveRoot, _factor, _mod); for (int i = _maxExp - 1; i >= 1; i--) { root[i] = (root[i + 1] * root[i + 1]) % _mod; } } private void NTT(long[] target, int size, int exp, long[] root) { if (size == 1) { return; } else { int half = size >> 1; long[] odd = new long[half]; long[] even = new long[half]; for (int i = 0; i < size; i++) { if ((i & 1) == 0) { even[i >> 1] = target[i]; } else { odd[(i - 1) >> 1] = target[i]; } } NTT(even, half, exp - 1, root); NTT(odd, half, exp - 1, root); long r = root[exp]; long f = 1L; for (int i = 0; i < size; i++) { target[i] = (even[i % half] + (f * odd[i % half]) % _mod) % _mod; f *= r; f %= _mod; } } } private void ButterflyNTT(Span<long> target, int exp, long[] root) { if (target.Length == 1) return; int n = target.Length; int k = exp; int r = 1 << (k - 1); for (int m = k; m > 0; m--) { for (int l = 0; l < n; l += (r << 1)) { long wi = 1; for (int i = 0; i < r; i++) { long temp = (target[l + i] + target[l + i + r]) % _mod; target[l + i + r] = (target[l + i] - target[l + i + r]) * wi % _mod; target[l + i] = temp; wi = wi * root[m] % _mod; } } r >>= 1; } } private void ButterflyINTT(Span<long> target, int exp, long[] root) { if (target.Length == 1) return; int n = target.Length; int k = exp; int r = 1; for (int m = 1; m < k + 1; m++) { for (int l = 0; l < n; l += (r << 1)) { long wi = 1; for (int i = 0; i < r; i++) { long temp = (target[l + i] + target[l + i + r] * wi) % _mod; target[l + i + r] = (target[l + i] - target[l + i + r] * wi) % _mod; target[l + i] = temp; wi = wi * root[m] % _mod; } } r <<= 1; } long ni = Inverse(n, _mod); for (int i = 0; i < n; i++) { target[i] = ((target[i] * ni % _mod) + _mod) % _mod; } } public long[] CalcConvolution(long[] a, long[] b) { int dsize = a.Length + b.Length; int exp = 0; while ((1 << exp) < dsize) { exp++; } int n = 1 << exp; if (exp > _maxExp) { throw new InvalidOperationException("Data too large."); } long[] buffer = new long[n]; long[] c = new long[n]; Array.Copy(a, 0, c, 0, a.Length); Array.Copy(b, 0, buffer, 0, b.Length); ButterflyNTT(c, exp, _root); ButterflyNTT(buffer, exp, _root); for (int i = 0; i < n; i++) { c[i] *= buffer[i]; c[i] %= _mod; } ButterflyINTT(c, exp, _inverseRoot); return c; } private static long SafeMod(long x, long m) { x %= m; if (x < 0) x += m; return x; } private static long ExtEuclid(long a, long b, ref long p, ref long q) { if (b == 0) { p = 1; q = 0; return a; } long d = ExtEuclid(b, a % b, ref q, ref p); q -= a / b * p; return d; } private static (long rem, long mod) CRT(long x1, long m1, long x2, long m2) { long p = 0, q = 0; long d = ExtEuclid(m1, m2, ref p, ref q); if ((x2 - x1) % d != 0) return (0, -1); long m = m1 * (m2 / d); long temp = (x2 - x1) / d * p % (m2 / d); long r = SafeMod(x1 + m1 * temp, m); return (r, m); } private static (long rem, long mod) CRT(List<long> x, List<long> mod) { long r = 0, m = 1; for (int i = 0; i < x.Count; i++) { long p = 0, q = 0; long d = ExtEuclid(m, mod[i], ref p, ref q); if ((x[i] - r) % d != 0) return (0, -1); long temp = (x[i] - r) / d * p % (mod[i] / d); r += m * temp; m *= mod[i] / d; } return (SafeMod(r, m), m); } } static class Constants { public const long Mod = 998244353L; //public const long Mod = 10007L; //public const long Mod = 1000000007L; } public sealed class AtCoderIO { Queue<string> _readQueue = new Queue<string>(); private void LoadQueue() { if (_readQueue.Count > 0) return; string line = Console.ReadLine(); string[] split = line.Split(' ', StringSplitOptions.RemoveEmptyEntries); for (int i = 0; i < split.Length; i++) _readQueue.Enqueue(split[i]); } private void Guard() { if (_readQueue.Count == 0) { throw new Exception("NO DATA TO READ"); } } public int Int() { LoadQueue(); Guard(); return int.Parse(_readQueue.Dequeue()); } public long Long() { LoadQueue(); Guard(); return long.Parse(_readQueue.Dequeue()); } public string String() { LoadQueue(); Guard(); return _readQueue.Dequeue(); } public short Short() { LoadQueue(); Guard(); return short.Parse(_readQueue.Dequeue()); } public byte Byte() { LoadQueue(); Guard(); return byte.Parse(_readQueue.Dequeue()); } public char Char() { LoadQueue(); Guard(); return char.Parse(_readQueue.Dequeue()); } public double Double() { LoadQueue(); Guard(); return double.Parse(_readQueue.Dequeue()); } public float Float() { LoadQueue(); Guard(); return float.Parse(_readQueue.Dequeue()); } public ModInt ModInt() { return new ModInt(Long()); } public T Read<T>() { Type type = typeof(T); if (type == typeof(int)) return (T)(object)Int(); else if (type == typeof(long)) return (T)(object)Long(); else if (type == typeof(float)) return (T)(object)Float(); else if (type == typeof(double)) return (T)(object)Double(); else if (type == typeof(short)) return (T)(object)Short(); else if (type == typeof(byte)) return (T)(object)Byte(); else if (type == typeof(char)) return (T)(object)Char(); else if (type == typeof(string)) return (T)(object)String(); else if (type == typeof(ModInt)) return (T)(object)ModInt(); else return default(T); } public int[] IntArray(int n) { if (n == 0) return Array.Empty<int>(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = Int(); } return arr; } public int[] ZeroIndexedPermutation(int n) { if (n == 0) return Array.Empty<int>(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = Int() - 1; } return arr; } public long[] LongArray(int n) { if (n == 0) return Array.Empty<long>(); long[] arr = new long[n]; for (int i = 0; i < n; i++) { arr[i] = Long(); } return arr; } public double[] DoubleArray(int n) { if (n == 0) return Array.Empty<double>(); double[] arr = new double[n]; for (int i = 0; i < n; i++) { arr[i] = Double(); } return arr; } public ModInt[] ModIntArray(int n) { if (n == 0) return Array.Empty<ModInt>(); ModInt[] arr = new ModInt[n]; for (int i = 0; i < n; i++) { arr[i] = (ModInt)Long(); } return arr; } public T[] ReadArray<T>(int n) { if (n == 0) return Array.Empty<T>(); T[] arr = new T[n]; for (int i = 0; i < n; i++) { arr[i] = Read<T>(); } return arr; } } public readonly struct ModInt : IEquatable<ModInt> { private readonly long Value; public static ModInt One => (ModInt)1L; public static ModInt Zero => (ModInt)0L; public ModInt(long value) { Value = SafeMod(value); } [MethodImpl(MethodImplOptions.AggressiveInlining)] private static long SafeMod(long a) { a %= Constants.Mod; if (a < 0) a += Constants.Mod; return a; } public ModInt Power(long exp) { if (exp <= -1) return this; if (exp == 0) return 1; if (exp == 1) return this; ModInt m = Power(exp / 2); m *= m; if (exp % 2 == 1) m *= this; return m; } public ModInt Inv() { return this.Power(Constants.Mod - 2L); } public static ModInt operator +(ModInt left, ModInt right) { return new ModInt(SafeMod(left.Value + right.Value)); } public static ModInt operator -(ModInt left, ModInt right) { return new ModInt(SafeMod(left.Value - right.Value)); } public static ModInt operator *(ModInt left, ModInt right) { return new ModInt(SafeMod(left.Value * right.Value)); } public static ModInt operator /(ModInt left, ModInt right) { if (right.Value == 0L) { return Zero; } ModInt inv = right.Inv(); return SafeMod(left * inv); } public static ModInt operator %(ModInt left, ModInt right) { if (right.Value == 0L) { return Zero; } return new ModInt(SafeMod(left.Value % right.Value)); } public static bool operator ==(ModInt left, ModInt right) { return left.Value == right.Value; } public static bool operator != (ModInt left, ModInt right) { return !(left == right); } public bool Equals(ModInt other) { return Value == other.Value; } public override bool Equals(object other) { if (other is ModInt m) { return this == m; } else return false; } public override int GetHashCode() { return Value.GetHashCode(); } public static implicit operator ModInt(long v) { return new ModInt(v); } public static implicit operator ModInt(int v) { return new ModInt(v); } public static implicit operator long(ModInt m) { return m.Value; } public static implicit operator int(ModInt m) { return (int)m.Value; } public long Raw() => Value; public override string ToString() { return Value.ToString(); } }