結果
| 問題 |
No.3045 反復重み付き累積和
|
| ユーザー |
 Nauclhlt🪷
|
| 提出日時 | 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();
}
}