結果
| 問題 | No.1068 #いろいろな色 / Red and Blue and more various colors (Hard) |
| ユーザー |
 yupiteru_kun
|
| 提出日時 | 2023-05-09 20:23:39 |
| 言語 | C# (.NET 8.0.203) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 60,334 bytes |
| コンパイル時間 | 15,133 ms |
| コンパイル使用メモリ | 166,080 KB |
| 実行使用メモリ | 202,940 KB |
| 最終ジャッジ日時 | 2024-11-26 06:02:03 |
| 合計ジャッジ時間 | 39,653 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 62 ms
28,800 KB |
| testcase_01 | AC | 62 ms
28,800 KB |
| testcase_02 | AC | 61 ms
29,184 KB |
| testcase_03 | AC | 93 ms
38,504 KB |
| testcase_04 | AC | 81 ms
36,096 KB |
| testcase_05 | AC | 87 ms
37,120 KB |
| testcase_06 | AC | 79 ms
34,788 KB |
| testcase_07 | AC | 78 ms
34,304 KB |
| testcase_08 | AC | 84 ms
36,352 KB |
| testcase_09 | AC | 88 ms
37,760 KB |
| testcase_10 | AC | 71 ms
32,512 KB |
| testcase_11 | AC | 76 ms
34,048 KB |
| testcase_12 | AC | 68 ms
31,872 KB |
| testcase_13 | AC | 1,190 ms
124,800 KB |
| testcase_14 | AC | 1,166 ms
124,444 KB |
| testcase_15 | AC | 1,187 ms
124,684 KB |
| testcase_16 | AC | 1,177 ms
125,536 KB |
| testcase_17 | AC | 1,189 ms
124,412 KB |
| testcase_18 | AC | 1,181 ms
124,092 KB |
| testcase_19 | AC | 1,220 ms
124,156 KB |
| testcase_20 | AC | 1,193 ms
124,944 KB |
| testcase_21 | AC | 1,204 ms
123,716 KB |
| testcase_22 | AC | 1,175 ms
123,192 KB |
| testcase_23 | AC | 1,198 ms
122,976 KB |
| testcase_24 | AC | 1,205 ms
123,664 KB |
| testcase_25 | AC | 1,202 ms
123,640 KB |
| testcase_26 | AC | 1,210 ms
124,180 KB |
| testcase_27 | AC | 1,182 ms
121,976 KB |
| testcase_28 | AC | 1,182 ms
121,848 KB |
| testcase_29 | AC | 1,146 ms
121,784 KB |
| testcase_30 | AC | 1,150 ms
124,804 KB |
| testcase_31 | RE | - |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (124 ms)。 MSBuild のバージョン 17.9.6+a4ecab324 (.NET) main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using static System.Math;
using System.Text;
using System.Threading;
using System.Globalization;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
using Library;
namespace Program
{
public static class ProblemA
{
static bool SAIKI = false;
static public int numberOfRandomCases = 0;
static public void MakeTestCase(List<string> _input, List<string> _output, ref Func<string[], bool> _outputChecker)
{
}
static public void Solve()
{
var N = NN;
var Q = NN;
var AList = NNList(N);
var BList = NNList(Q);
var F = LIB_FPS.MakeBuilder(N);
var ans = F();
var oneCount = AList.Count(e => e == 1);
var excludeOne = AList.Where(e => e != 1).ToArray();
var rt = (int)Sqrt(N);
var q = new LIB_Deque<long[]>();
q.PushBack(new[] { 1L });
foreach (var item in excludeOne)
{
var tmp2 = new long[2];
tmp2[0] = item - 1;
tmp2[1] = 1;
q.PushBack(tmp2);
}
while (q.Count > 1) q.PushBack(LIB_NTT.Multiply(q.PopFront(), q.PopFront()));
ans = F(q.PopFront()) * F(0, 1).Pow(oneCount);
foreach (var item in BList)
{
Console.WriteLine(ans[item]);
}
}
class Printer : StreamWriter
{
public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { base.AutoFlush = false; }
public Printer(Stream stream, Encoding encoding) : base(stream, encoding) { base.AutoFlush = false; }
}
static LIB_FastIO fastio = new LIB_FastIODebug();
static string[] args;
static public void Main(string[] args_t) { args = args_t; if (args_t.Length == 0) { fastio = new LIB_FastIO(); Console.SetOut(new Printer(Console.OpenStandardOutput())); } if (SAIKI) { var t = new Thread(Solve, 134217728); t.Start(); t.Join(); } else Solve(); Console.Out.Flush(); }
static long NN => fastio.Long();
static double ND => fastio.Double();
static string NS => fastio.Scan();
static long[] NNList(long N) => Repeat(0, N).Select(_ => NN).ToArray();
static double[] NDList(long N) => Repeat(0, N).Select(_ => ND).ToArray();
static string[] NSList(long N) => Repeat(0, N).Select(_ => NS).ToArray();
static long Count<T>(this IEnumerable<T> x, Func<T, bool> pred) => Enumerable.Count(x, pred);
static IEnumerable<T> Repeat<T>(T v, long n) => Enumerable.Repeat<T>(v, (int)n);
static IEnumerable<int> Range(long s, long c) => Enumerable.Range((int)s, (int)c);
static IOrderedEnumerable<T> OrderByRand<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x, _ => xorshift);
static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x) => Enumerable.OrderBy(x.OrderByRand(), e => e);
static IOrderedEnumerable<T1> OrderBy<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderBy(x.OrderByRand(), selector);
static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x) => Enumerable.OrderByDescending(x.OrderByRand(), e => e);
static IOrderedEnumerable<T1> OrderByDescending<T1, T2>(this IEnumerable<T1> x, Func<T1, T2> selector) => Enumerable.OrderByDescending(x.OrderByRand(), selector);
static IOrderedEnumerable<string> OrderBy(this IEnumerable<string> x) => x.OrderByRand().OrderBy(e => e, StringComparer.OrdinalIgnoreCase);
static IOrderedEnumerable<T> OrderBy<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderBy(selector, StringComparer.OrdinalIgnoreCase);
static IOrderedEnumerable<string> OrderByDescending(this IEnumerable<string> x) => x.OrderByRand().OrderByDescending(e => e, StringComparer.OrdinalIgnoreCase);
static IOrderedEnumerable<T> OrderByDescending<T>(this IEnumerable<T> x, Func<T, string> selector) => x.OrderByRand().OrderByDescending(selector, StringComparer.OrdinalIgnoreCase);
static string Join<T>(this IEnumerable<T> x, string separator = "") => string.Join(separator, x);
static uint xorshift { get { _xsi.MoveNext(); return _xsi.Current; } }
static IEnumerator<uint> _xsi = _xsc();
static IEnumerator<uint> _xsc() { uint x = 123456789, y = 362436069, z = 521288629, w = (uint)(DateTime.Now.Ticks & 0xffffffff); while (true) { var t = x ^ (x << 11); x = y; y = z; z = w; w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); yield return w; } }
static bool Chmax<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) < 0) { lhs = rhs; return true; } return false; }
static bool Chmin<T>(this ref T lhs, T rhs) where T : struct, IComparable<T> { if (lhs.CompareTo(rhs) > 0) { lhs = rhs; return true; } return false; }
static void Fill<T>(this T[] array, T value) => array.AsSpan().Fill(value);
static void Fill<T>(this T[,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0], array.Length).Fill(value);
static void Fill<T>(this T[,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0], array.Length).Fill(value);
static void Fill<T>(this T[,,,] array, T value) => MemoryMarshal.CreateSpan(ref array[0, 0, 0, 0], array.Length).Fill(value);
}
}
namespace Library {
class LIB_FastIO
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FastIO() { str = Console.OpenStandardInput(); }
readonly Stream str;
readonly byte[] buf = new byte[2048];
int len, ptr;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
byte read()
{
if (ptr >= len)
{
ptr = 0;
if ((len = str.Read(buf, 0, 2048)) <= 0)
{
return 0;
}
}
return buf[ptr++];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
char Char()
{
byte b = 0;
do b = read();
while (b < 33 || 126 < b);
return (char)b;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
virtual public string Scan()
{
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
sb.Append(b);
return sb.ToString();
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
virtual public long Long()
{
long ret = 0; byte b = 0; var ng = false;
do b = read();
while (b != '-' && (b < '0' || '9' < b));
if (b == '-') { ng = true; b = read(); }
for (; true; b = read())
{
if (b < '0' || '9' < b)
return ng ? -ret : ret;
else ret = (ret << 3) + (ret << 1) + b - '0';
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
virtual public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); }
}
class LIB_FastIODebug : LIB_FastIO
{
Queue<string> param = new Queue<string>();
[MethodImpl(MethodImplOptions.AggressiveInlining)]
string NextString() { if (param.Count == 0) foreach (var item in Console.ReadLine().Split(' ')) param.Enqueue(item); return param.Dequeue(); }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FastIODebug() { }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public override string Scan() => NextString();
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public override long Long() => long.Parse(NextString());
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public override double Double() => double.Parse(NextString());
}
class LIB_NTT
{
const uint mod1 = 167772161;
const uint root1 = 3;
const uint mod2 = 469762049;
const uint root2 = 3;
const uint mod3 = 754974721;
const uint root3 = 11;
const uint mod4 = 998244353;
const uint root4 = 3;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint mul1(uint x, uint y) => (uint)((ulong)x * y % mod1);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint mul2(uint x, uint y) => (uint)((ulong)x * y % mod2);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint mul3(uint x, uint y) => (uint)((ulong)x * y % mod3);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint mul4(uint x, uint y) => (uint)((ulong)x * y % mod4);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint pow1(uint x, uint n) { uint res = 1; while (n > 0) { if ((n & 1) != 0) res = mul1(res, x); x = mul1(x, x); n >>= 1; } return res; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint pow2(uint x, uint n) { uint res = 1; while (n > 0) { if ((n & 1) != 0) res = mul2(res, x); x = mul2(x, x); n >>= 1; } return res; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint pow3(uint x, uint n) { uint res = 1; while (n > 0) { if ((n & 1) != 0) res = mul3(res, x); x = mul3(x, x); n >>= 1; } return res; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint pow4(uint x, uint n) { uint res = 1; while (n > 0) { if ((n & 1) != 0) res = mul4(res, x); x = mul4(x, x); n >>= 1; } return res; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint inverse1(uint x) { long b = mod1, r = 1, u = 0, t = 0, x2 = x; while (b > 0) { var q = x2 / b; t = u; u = r - q * u; r = t; t = b; b = x2 - q * b; x2 = t; } return (uint)(r < 0 ? r + mod1 : r); }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint inverse2(uint x) { long b = mod2, r = 1, u = 0, t = 0, x2 = x; while (b > 0) { var q = x2 / b; t = u; u = r - q * u; r = t; t = b; b = x2 - q * b; x2 = t; } return (uint)(r < 0 ? r + mod2 : r); }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint inverse3(uint x) { long b = mod3, r = 1, u = 0, t = 0, x2 = x; while (b > 0) { var q = x2 / b; t = u; u = r - q * u; r = t; t = b; b = x2 - q * b; x2 = t; } return (uint)(r < 0 ? r + mod3 : r); }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint inverse4(uint x) { long b = mod4, r = 1, u = 0, t = 0, x2 = x; while (b > 0) { var q = x2 / b; t = u; u = r - q * u; r = t; t = b; b = x2 - q * b; x2 = t; } return (uint)(r < 0 ? r + mod4 : r); }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void ntt1(ref Span<uint> a, bool rev = false) { var alen = a.Length; if (alen == 1) return; var halfn = alen >> 1; Span<uint> b = new uint[alen]; var s = pow1(root1, rev ? (mod1 - 1 - (mod1 - 1) / (uint)alen) : (mod1 - 1) / (uint)alen); int i, j, k, l, r; var regLength = System.Numerics.Vector<uint>.Count; Span<uint> mods = stackalloc uint[regLength]; mods.Fill(mod1); var modV = new System.Numerics.Vector<uint>(mods); var kp = new uint[halfn + 1]; ref uint kpref = ref kp[0]; kpref = 1; for (l = 0; l < halfn; ++l) Unsafe.Add(ref kpref, l + 1) = mul1(Unsafe.Add(ref kpref, l), s); for (i = 1; i < alen; i <<= 1, l >>= 1) { for (j = 0, r = 0; j < l; ++j, r += i) { s = Unsafe.Add(ref kpref, i * j); var ten = i - regLength; var rshift = (r << 1); var rshifti = rshift + i; for (k = 0; k < ten; k += regLength) { var u = new System.Numerics.Vector<uint>(a.Slice(k + r)); var v = new System.Numerics.Vector<uint>(a.Slice(k + r + halfn)); var add = u + v; var sub = modV + u - v; var ge = System.Numerics.Vector.GreaterThanOrEqual(add, modV); add = System.Numerics.Vector.ConditionalSelect(ge, add - modV, add); add.CopyTo(b.Slice(k + rshift)); sub.CopyTo(b.Slice(k + rshifti)); } ref uint aref = ref a[0]; ref uint bref = ref b[0]; for (k = 0; k < ten; ++k) { ref uint brefi = ref Unsafe.Add(ref bref, k + rshifti); brefi = mul1(brefi, s); } for (; k < i; ++k) { var kr = k + r; ref uint akr = ref Unsafe.Add(ref aref, kr); ref uint krhalfn = ref Unsafe.Add(ref aref, kr + halfn); Unsafe.Add(ref bref, kr + r) = (akr + krhalfn) % mod1; Unsafe.Add(ref bref, kr + r + i) = mul1(akr + mod1 - krhalfn, s); } } var t = a; a = b; b = t; } if (rev) { s = inverse1((uint)alen); ref uint aref = ref a[0]; for (i = 0; i < alen; ++i) { ref uint arefi = ref Unsafe.Add(ref aref, i); arefi = mul1(arefi, s); } } }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void ntt2(ref Span<uint> a, bool rev = false) { var alen = a.Length; if (alen == 1) return; var halfn = alen >> 1; Span<uint> b = new uint[alen]; var s = pow2(root2, rev ? (mod2 - 1 - (mod2 - 1) / (uint)alen) : (mod2 - 1) / (uint)alen); int i, j, k, l, r; var regLength = System.Numerics.Vector<uint>.Count; Span<uint> mods = stackalloc uint[regLength]; mods.Fill(mod2); var modV = new System.Numerics.Vector<uint>(mods); var kp = new uint[halfn + 1]; ref uint kpref = ref kp[0]; kpref = 1; for (l = 0; l < halfn; ++l) Unsafe.Add(ref kpref, l + 1) = mul2(Unsafe.Add(ref kpref, l), s); for (i = 1; i < alen; i <<= 1, l >>= 1) { for (j = 0, r = 0; j < l; ++j, r += i) { s = Unsafe.Add(ref kpref, i * j); var ten = i - regLength; var rshift = (r << 1); var rshifti = rshift + i; for (k = 0; k < ten; k += regLength) { var u = new System.Numerics.Vector<uint>(a.Slice(k + r)); var v = new System.Numerics.Vector<uint>(a.Slice(k + r + halfn)); var add = u + v; var sub = modV + u - v; var ge = System.Numerics.Vector.GreaterThanOrEqual(add, modV); add = System.Numerics.Vector.ConditionalSelect(ge, add - modV, add); add.CopyTo(b.Slice(k + rshift)); sub.CopyTo(b.Slice(k + rshifti)); } ref uint aref = ref a[0]; ref uint bref = ref b[0]; for (k = 0; k < ten; ++k) { ref uint brefi = ref Unsafe.Add(ref bref, k + rshifti); brefi = mul2(brefi, s); } for (; k < i; ++k) { var kr = k + r; ref uint akr = ref Unsafe.Add(ref aref, kr); ref uint krhalfn = ref Unsafe.Add(ref aref, kr + halfn); Unsafe.Add(ref bref, kr + r) = (akr + krhalfn) % mod2; Unsafe.Add(ref bref, kr + r + i) = mul2(akr + mod2 - krhalfn, s); } } var t = a; a = b; b = t; } if (rev) { s = inverse2((uint)alen); ref uint aref = ref a[0]; for (i = 0; i < alen; ++i) { ref uint arefi = ref Unsafe.Add(ref aref, i); arefi = mul2(arefi, s); } } }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void ntt3(ref Span<uint> a, bool rev = false) { var alen = a.Length; if (alen == 1) return; var halfn = alen >> 1; Span<uint> b = new uint[alen]; var s = pow3(root3, rev ? (mod3 - 1 - (mod3 - 1) / (uint)alen) : (mod3 - 1) / (uint)alen); int i, j, k, l, r; var regLength = System.Numerics.Vector<uint>.Count; Span<uint> mods = stackalloc uint[regLength]; mods.Fill(mod3); var modV = new System.Numerics.Vector<uint>(mods); var kp = new uint[halfn + 1]; ref uint kpref = ref kp[0]; kpref = 1; for (l = 0; l < halfn; ++l) Unsafe.Add(ref kpref, l + 1) = mul3(Unsafe.Add(ref kpref, l), s); for (i = 1; i < alen; i <<= 1, l >>= 1) { for (j = 0, r = 0; j < l; ++j, r += i) { s = Unsafe.Add(ref kpref, i * j); var ten = i - regLength; var rshift = (r << 1); var rshifti = rshift + i; for (k = 0; k < ten; k += regLength) { var u = new System.Numerics.Vector<uint>(a.Slice(k + r)); var v = new System.Numerics.Vector<uint>(a.Slice(k + r + halfn)); var add = u + v; var sub = modV + u - v; var ge = System.Numerics.Vector.GreaterThanOrEqual(add, modV); add = System.Numerics.Vector.ConditionalSelect(ge, add - modV, add); add.CopyTo(b.Slice(k + rshift)); sub.CopyTo(b.Slice(k + rshifti)); } ref uint aref = ref a[0]; ref uint bref = ref b[0]; for (k = 0; k < ten; ++k) { ref uint brefi = ref Unsafe.Add(ref bref, k + rshifti); brefi = mul3(brefi, s); } for (; k < i; ++k) { var kr = k + r; ref uint akr = ref Unsafe.Add(ref aref, kr); ref uint krhalfn = ref Unsafe.Add(ref aref, kr + halfn); Unsafe.Add(ref bref, kr + r) = (akr + krhalfn) % mod3; Unsafe.Add(ref bref, kr + r + i) = mul3(akr + mod3 - krhalfn, s); } } var t = a; a = b; b = t; } if (rev) { s = inverse3((uint)alen); ref uint aref = ref a[0]; for (i = 0; i < alen; ++i) { ref uint arefi = ref Unsafe.Add(ref aref, i); arefi = mul3(arefi, s); } } }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public void ntt4(ref Span<uint> a, bool rev = false)
{
var alen = a.Length;
if (alen == 1) return;
var halfn = alen >> 1;
Span<uint> b = new uint[alen];
var s = pow4(root4, rev ? (mod4 - 1 - (mod4 - 1) / (uint)alen) : (mod4 - 1) / (uint)alen);
int i, j, k, l, r;
var regLength = System.Numerics.Vector<uint>.Count;
Span<uint> mods = stackalloc uint[regLength];
mods.Fill(mod4);
var modV = new System.Numerics.Vector<uint>(mods);
var kp = new uint[halfn + 1];
ref uint kpref = ref kp[0];
kpref = 1;
for (l = 0; l < halfn; ++l) Unsafe.Add(ref kpref, l + 1) = mul4(Unsafe.Add(ref kpref, l), s);
for (i = 1; i < alen; i <<= 1, l >>= 1)
{
for (j = 0, r = 0; j < l; ++j, r += i)
{
s = Unsafe.Add(ref kpref, i * j);
var ten = i - regLength;
var rshift = (r << 1);
var rshifti = rshift + i;
for (k = 0; k < ten; k += regLength)
{
var u = new System.Numerics.Vector<uint>(a.Slice(k + r));
var v = new System.Numerics.Vector<uint>(a.Slice(k + r + halfn));
var add = u + v;
var sub = modV + u - v;
var ge = System.Numerics.Vector.GreaterThanOrEqual(add, modV);
add = System.Numerics.Vector.ConditionalSelect(ge, add - modV, add);
add.CopyTo(b.Slice(k + rshift));
sub.CopyTo(b.Slice(k + rshifti));
}
ref uint aref = ref a[0];
ref uint bref = ref b[0];
for (k = 0; k < ten; ++k)
{
ref uint brefi = ref Unsafe.Add(ref bref, k + rshifti);
brefi = mul4(brefi, s);
}
for (; k < i; ++k)
{
var kr = k + r;
ref uint akr = ref Unsafe.Add(ref aref, kr);
ref uint krhalfn = ref Unsafe.Add(ref aref, kr + halfn);
Unsafe.Add(ref bref, kr + r) = (akr + krhalfn) % mod4;
Unsafe.Add(ref bref, kr + r + i) = mul4(akr + mod4 - krhalfn, s);
}
}
var t = a; a = b; b = t;
}
if (rev)
{
s = inverse4((uint)alen);
ref uint aref = ref a[0];
for (i = 0; i < alen; ++i)
{
ref uint arefi = ref Unsafe.Add(ref aref, i);
arefi = mul4(arefi, s);
}
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public long[] NTT998244353(long[] ary, int len, bool isInverse = false)
{
var t = 1;
while (t < len) t <<= 1;
Span<uint> na = new uint[t];
ref long aref = ref ary[0];
ref uint naref = ref na[0];
for (var i = 0; i < ary.Length; ++i) Unsafe.Add(ref naref, i) = (uint)Unsafe.Add(ref aref, i);
ntt4(ref na, isInverse);
naref = ref na[0];
var ret = new long[t];
ref var retref = ref ret[0];
for (var i = 0; i < ret.Length; ++i) Unsafe.Add(ref retref, i) = Unsafe.Add(ref naref, i);
return ret;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint[] Multiply1(uint[] a, uint[] b) { var n = a.Length + b.Length - 1; var t = 1; while (t < n) t <<= 1; Span<uint> na = new uint[t]; Span<uint> nb = new uint[t]; ref uint naref = ref na[0]; ref uint nbref = ref nb[0]; Unsafe.CopyBlock(ref Unsafe.As<uint, byte>(ref naref), ref Unsafe.As<uint, byte>(ref a[0]), (uint)(a.Length << 2)); Unsafe.CopyBlock(ref Unsafe.As<uint, byte>(ref nbref), ref Unsafe.As<uint, byte>(ref b[0]), (uint)(b.Length << 2)); ntt1(ref na); ntt1(ref nb); naref = ref na[0]; nbref = ref nb[0]; for (var i = 0; i < t; ++i) { ref uint narefi = ref Unsafe.Add(ref naref, i); narefi = mul1(narefi, Unsafe.Add(ref nbref, i)); } ntt1(ref na, true); var ret = new uint[n]; naref = ref na[0]; ref uint retref = ref ret[0]; for (var i = 0; i < n; ++i) Unsafe.Add(ref retref, i) = Unsafe.Add(ref naref, i); return ret; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint[] Multiply2(uint[] a, uint[] b) { var n = a.Length + b.Length - 1; var t = 1; while (t < n) t <<= 1; Span<uint> na = new uint[t]; Span<uint> nb = new uint[t]; ref uint naref = ref na[0]; ref uint nbref = ref nb[0]; Unsafe.CopyBlock(ref Unsafe.As<uint, byte>(ref naref), ref Unsafe.As<uint, byte>(ref a[0]), (uint)(a.Length << 2)); Unsafe.CopyBlock(ref Unsafe.As<uint, byte>(ref nbref), ref Unsafe.As<uint, byte>(ref b[0]), (uint)(b.Length << 2)); ntt2(ref na); ntt2(ref nb); naref = ref na[0]; nbref = ref nb[0]; for (var i = 0; i < t; ++i) { ref uint narefi = ref Unsafe.Add(ref naref, i); narefi = mul2(narefi, Unsafe.Add(ref nbref, i)); } ntt2(ref na, true); var ret = new uint[n]; naref = ref na[0]; ref uint retref = ref ret[0]; for (var i = 0; i < n; ++i) Unsafe.Add(ref retref, i) = Unsafe.Add(ref naref, i); return ret; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static uint[] Multiply3(uint[] a, uint[] b) { var n = a.Length + b.Length - 1; var t = 1; while (t < n) t <<= 1; Span<uint> na = new uint[t]; Span<uint> nb = new uint[t]; ref uint naref = ref na[0]; ref uint nbref = ref nb[0]; Unsafe.CopyBlock(ref Unsafe.As<uint, byte>(ref naref), ref Unsafe.As<uint, byte>(ref a[0]), (uint)(a.Length << 2)); Unsafe.CopyBlock(ref Unsafe.As<uint, byte>(ref nbref), ref Unsafe.As<uint, byte>(ref b[0]), (uint)(b.Length << 2)); ntt3(ref na); ntt3(ref nb); naref = ref na[0]; nbref = ref nb[0]; for (var i = 0; i < t; ++i) { ref uint narefi = ref Unsafe.Add(ref naref, i); narefi = mul3(narefi, Unsafe.Add(ref nbref, i)); } ntt3(ref na, true); var ret = new uint[n]; naref = ref na[0]; ref uint retref = ref ret[0]; for (var i = 0; i < n; ++i) Unsafe.Add(ref retref, i) = Unsafe.Add(ref naref, i); return ret; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static long[] MultiplySparse(long[] a, long[] b, long mod = -1)
{
if (mod == -1)
{
var ret = new long[a.Length + b.Length - 1];
var data = new List<(int idx, long val)>();
var datb = new List<(int idx, long val)>();
for (var i = 0; i < a.Length; ++i) if (a[i] != 0) data.Add((i, a[i]));
for (var i = 0; i < b.Length; ++i) if (b[i] != 0) datb.Add((i, b[i]));
if (data.Count * (long)datb.Count > a.Length + b.Length)
{
return null;
}
foreach (var item in data)
{
foreach (var item2 in datb)
{
ret[item.idx + item2.idx] += item.val * item2.val;
}
}
return ret;
}
else
{
var ret = new ulong[a.Length + b.Length - 1];
var br = new LIB_BarrettReduction((ulong)mod);
var data = new List<(int idx, ulong val)>();
var datb = new List<(int idx, ulong val)>();
for (var i = 0; i < a.Length; ++i) if (a[i] != 0)
{
var v = a[i] % mod;
if (v < 0) v += mod;
data.Add((i, (ulong)v));
}
for (var i = 0; i < b.Length; ++i) if (b[i] != 0)
{
var v = b[i] % mod;
if (v < 0) v += mod;
datb.Add((i, (ulong)v));
}
if (data.Count * (long)datb.Count > a.Length + b.Length)
{
return null;
}
foreach (var item in data)
{
foreach (var item2 in datb)
{
ret[item.idx + item2.idx] += br.Reduce(item.val * item2.val);
}
}
return ret.Select(e => (long)(br.Reduce(e))).ToArray();
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public long[] Multiply(long[] a, long[] b)
{
var sparse = MultiplySparse(a, b, mod4);
if (sparse != null) return sparse;
var n = a.Length + b.Length - 1;
var t = 1;
while (t < n) t <<= 1;
Span<uint> na = new uint[t];
Span<uint> nb = new uint[t];
ref long aref = ref a[0];
ref long bref = ref b[0];
ref uint naref = ref na[0];
ref uint nbref = ref nb[0];
for (var i = 0; i < a.Length; ++i) Unsafe.Add(ref naref, i) = (uint)(Unsafe.Add(ref aref, i) % mod4);
for (var i = 0; i < b.Length; ++i) Unsafe.Add(ref nbref, i) = (uint)(Unsafe.Add(ref bref, i) % mod4);
ntt4(ref na);
ntt4(ref nb);
naref = ref na[0];
nbref = ref nb[0];
for (var i = 0; i < t; ++i)
{
ref uint narefi = ref Unsafe.Add(ref naref, i);
narefi = mul4(narefi, Unsafe.Add(ref nbref, i));
}
ntt4(ref na, true);
var ret = new long[n];
naref = ref na[0];
ref long retref = ref ret[0];
for (var i = 0; i < n; ++i) Unsafe.Add(ref retref, i) = Unsafe.Add(ref naref, i);
return ret;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public long[] Multiply(long[] a, long[] b, long mod)
{
var sparse = MultiplySparse(a, b, mod);
if (sparse != null) return sparse;
if (mod == 998244353) return Multiply(a, b);
var x = Multiply1(a.Select(e => (uint)(e % mod1)).ToArray(), b.Select(e => (uint)(e % mod1)).ToArray());
var y = Multiply2(a.Select(e => (uint)(e % mod2)).ToArray(), b.Select(e => (uint)(e % mod2)).ToArray());
var z = Multiply3(a.Select(e => (uint)(e % mod3)).ToArray(), b.Select(e => (uint)(e % mod3)).ToArray());
var m1_inv_m2 = inverse2(mod1);
var m12_inv_m3 = inverse3(mul3(mod1, mod2));
var m12_mod = (long)mod1 * mod2 % mod;
var ret = new long[x.Length];
ref long retref = ref ret[0];
ref uint xref = ref x[0];
ref uint yref = ref y[0];
ref uint zref = ref z[0];
for (var i = 0; i < x.Length; ++i)
{
var xv = Unsafe.Add(ref xref, i);
var v1 = mul2(Unsafe.Add(ref yref, i) + (mod2 << 1) - xv, m1_inv_m2);
var v2 = mul3(Unsafe.Add(ref zref, i) + (mod3 << 1) - xv + mod3 - mul3(mod1, v1), m12_inv_m3);
Unsafe.Add(ref retref, i) = (xv + ((long)mod1 * v1 % mod) + (m12_mod * v2 % mod)) % mod;
}
return ret;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public long[] MultiplyLong(long[] a, long[] b)
{
var sparse = MultiplySparse(a, b);
if (sparse != null) return sparse;
unchecked
{
const ulong mod23 = (ulong)mod2 * mod3;
const ulong mod13 = (ulong)mod1 * mod3;
const ulong mod12 = (ulong)mod1 * mod2;
const ulong mod123 = (ulong)mod1 * mod2 * mod3;
ulong[] offset = new ulong[] { 0, 0, mod123, 2 * mod123, 3 * mod123 };
const ulong i1 = 190329765;
const ulong i2 = 58587104;
const ulong i3 = 187290749;
var c1 = Multiply1(a.Select(e => (uint)(e % mod1) + mod1).ToArray(), b.Select(e => (uint)(e % mod1) + mod1).ToArray());
var c2 = Multiply2(a.Select(e => (uint)(e % mod2) + mod2).ToArray(), b.Select(e => (uint)(e % mod2) + mod2).ToArray());
var c3 = Multiply3(a.Select(e => (uint)(e % mod3) + mod3).ToArray(), b.Select(e => (uint)(e % mod3) + mod3).ToArray());
var c = new long[a.Length + b.Length - 1];
for (var i = 0; i < c.Length; ++i)
{
var x = 0UL;
x += c1[i] * i1 % mod1 * mod23;
x += c2[i] * i2 % mod2 * mod13;
x += c3[i] * i3 % mod3 * mod12;
var tmp = (long)x % mod1;
if (tmp < 0) tmp += mod1;
var diff = c1[i] - tmp;
if (diff < 0) diff += mod1;
c[i] = (long)(x - offset[diff % 5]);
}
return c;
}
}
}
class LIB_FPS
{
const uint MOD = 998244353;
uint[] ary;
public int K
{
get;
private set;
}
public delegate LIB_FPS FPSBuilder(params long[] a);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public FPSBuilder MakeBuilder(long K) => new FPSBuilder(a => new LIB_FPS(K, a));
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FPS(long K)
{
this.K = (int)K;
ary = new uint[K + 1];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FPS(long K, int[] a) : this(K, a.Select(e => (long)e).ToArray())
{
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FPS(long K, long[] a) : this(K)
{
var ten = Min(ary.Length, a.Length);
for (var i = 0; i < ten; ++i)
{
var val = a[i] % MOD;
if (val < 0) val += MOD;
ary[i] = (uint)val;
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FPS Clone()
{
var ret = new LIB_FPS(K);
ret.ary = (uint[])ary.Clone();
return ret;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_FPS operator +(LIB_FPS x, LIB_FPS y)
{
var ret = new LIB_FPS(Max(x.K, y.K));
for (var i = 0; i < x.ary.Length; ++i) ret.ary[i] += x.ary[i];
for (var i = 0; i < y.ary.Length; ++i)
{
var sum = ret.ary[i] + y.ary[i];
ret.ary[i] = sum >= MOD ? sum - MOD : sum;
}
return ret;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_FPS operator +(LIB_FPS x, long y)
{
var ret = x.Clone();
var sum = ret[0] + y;
sum %= MOD;
ret[0] = sum < 0 ? sum + MOD : sum;
return ret;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_FPS operator +(long x, LIB_FPS y) => y + x;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_FPS operator -(LIB_FPS x, LIB_FPS y)
{
var ret = new LIB_FPS(Max(x.K, y.K));
for (var i = 0; i < x.ary.Length; ++i) ret.ary[i] += x.ary[i];
for (var i = 0; i < y.ary.Length; ++i)
{
var sum = ret.ary[i] + MOD - y.ary[i];
ret.ary[i] = sum >= MOD ? sum - MOD : sum;
}
return ret;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_FPS operator -(LIB_FPS x, long y)
{
var ret = x.Clone();
var sum = ret[0] - y;
sum %= MOD;
ret[0] = sum < 0 ? sum + MOD : sum;
return ret;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_FPS operator -(long x, LIB_FPS y) => -1 * (y - x);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_FPS operator *(LIB_FPS x, LIB_FPS y)
{
return new LIB_FPS(Max(x.K, y.K), LIB_NTT.Multiply(x.ary.Select(e => (long)e).ToArray(), y.ary.Select(e => (long)e).ToArray()));
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_FPS operator *(LIB_FPS x, long y)
{
var ret = x.Clone();
for (var i = 0; i < ret.ary.Length; ++i) ret.ary[i] = (uint)((MOD + y % MOD) * ret.ary[i] % MOD);
return ret;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_FPS operator *(long x, LIB_FPS y) => y * x;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_FPS operator /(LIB_FPS x, LIB_FPS y) => x * y.Inverse();
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_FPS operator /(LIB_FPS x, long y) => x * LIB_Mod998244353.Inverse(y);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_FPS operator /(long x, LIB_FPS y) => y.Inverse() * x;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public long BostanMori(long N, LIB_FPS nume, LIB_FPS deno)
{
var p = nume.ary.Select(e => (long)e).ToArray();
var q = deno.ary.Select(e => (long)e).ToArray();
while (N > 0)
{
var flipQ = q.ToArray();
for (var i = 1; i < flipQ.Length; i += 2) flipQ[i] = flipQ[i] == 0 ? 0 : MOD - flipQ[i];
var tmp = LIB_NTT.Multiply(p, flipQ);
p = new long[(tmp.Length + (~N & 1)) / 2];
for (var i = 0; i < p.Length; ++i) p[i] = tmp[i * 2 + (N & 1)];
tmp = LIB_NTT.Multiply(q, flipQ);
q = new long[(tmp.Length + 1) / 2];
for (var i = 0; i < q.Length; ++i) q[i] = tmp[i * 2];
N /= 2;
}
return p[0] * LIB_Mod998244353.Inverse(q[0]) % MOD;
}
/// <summary>
/// べき乗
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FPS Pow(long M)
{
var ret = Clone();
ret.Pow_inplace(M);
return ret;
}
/// <summary>
/// べき乗
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Pow_inplace(long M)
{
if (M == 0)
{
for (var i = 1; i < ary.Length; ++i) ary[i] = 0;
ary[0] = 1;
return;
}
var l = 0;
while (l < ary.Length && ary[l] == 0) ++l;
if (l == ary.Length || l > (ary.Length - 1) / M)
{
for (var i = 0; i < ary.Length; ++i) ary[i] = 0;
return;
}
var powc = LIB_Mod998244353.Pow(ary[l], M);
var invc = LIB_Mod998244353.Inverse(ary[l]);
var g = new LIB_FPS(K - l);
for (var i = l; i < ary.Length; ++i) g.ary[i - l] = (uint)(ary[i] * invc % MOD);
var dat = new List<(int idx, long val)>();
for (var i = 1; i < g.ary.Length; ++i) if (g.ary[i] != 0) dat.Add((i, g.ary[i]));
var ten = l * M;
M %= MOD;
if (dat.Count > 100)
{
g.Log_inplace_dense();
for (var i = 0; i < g.ary.Length; ++i) g.ary[i] = (uint)(M * g.ary[i] % MOD);
g.Exp_inplace_dense();
}
else
{
var inv = new long[g.ary.Length];
inv[1] = 1;
for (var i = 2; i < inv.Length; ++i) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
for (var n = 0; n < g.ary.Length - 1; ++n)
{
g.ary[n + 1] = 0;
foreach (var item in dat)
{
if (item.idx > n + 1) break;
var t = item.val * g.ary[n - item.idx + 1] % MOD;
t = t * ((M * item.idx % MOD) - n + item.idx - 1) % MOD;
if (t < 0) t += MOD;
g.ary[n + 1] += (uint)t;
if (g.ary[n + 1] >= MOD) g.ary[n + 1] -= MOD;
}
g.ary[n + 1] = (uint)(g.ary[n + 1] * inv[n + 1] % MOD);
}
}
for (var i = ary.Length - 1; i >= ten; --i) ary[i] = (uint)(powc * g.ary[i - ten] % MOD);
for (var i = 0; i < ten; ++i) ary[i] = 0;
}
/// <summary>
/// 指数 (a0 == 0)
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FPS Exp()
{
var ret = Clone();
ret.Exp_inplace();
return ret;
}
/// <summary>
/// 指数 (a0 == 0)
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Exp_inplace()
{
var dat = new List<(int idx, long val)>();
for (var i = 1; i < ary.Length; ++i) if (ary[i] != 0) dat.Add((i - 1, (long)i * ary[i] % MOD));
if (dat.Count > 320)
{
Exp_inplace_dense();
return;
}
// sparse
var inv = new long[ary.Length + 1];
inv[1] = 1;
for (var i = 2; i < inv.Length; ++i) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
ary[0] = 1;
for (var n = 1; n < ary.Length; ++n)
{
var rhs = 0L;
foreach (var item in dat)
{
if (item.idx > n - 1) break;
rhs += item.val * ary[n - 1 - item.idx] % MOD;
}
ary[n] = (uint)((rhs % MOD) * inv[n] % MOD);
}
}
/// <summary>
/// 指数 (a0 == 0)
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Exp_inplace_dense()
{
var maxlen = 2;
while ((maxlen << 1) <= K) maxlen <<= 1;
var g = new uint[maxlen];
var inv = new long[maxlen * 2];
inv[1] = 1;
for (var i = 2; i < inv.Length; ++i) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
Span<uint> nttg = new uint[2];
g[0] = 1;
nttg[0] = 1;
nttg[1] = 1;
ary[0] = 1;
var h_drv = Differential();
var len = 2;
while (len <= K)
{
var nextlen = len * 2;
Span<uint> nttf = new uint[nextlen];
for (var i = 0; i < len; ++i) nttf[i] = ary[i];
LIB_NTT.ntt4(ref nttf);
{
Span<uint> ntth = new uint[len];
for (var i = 0; i < len; ++i) ntth[i] = (uint)((ulong)nttf[i * 2] * nttg[i] % MOD);
LIB_NTT.ntt4(ref ntth, true);
for (var i = 0; i < len / 2; ++i) ntth[i] = ntth[i + len / 2];
for (var i = len / 2; i < len; ++i) ntth[i] = 0;
LIB_NTT.ntt4(ref ntth);
for (var i = 0; i < len; ++i) ntth[i] = (uint)((ulong)ntth[i] * nttg[i] % MOD);
LIB_NTT.ntt4(ref ntth, true);
for (var i = len / 2; i < len; ++i) g[i] = (ntth[i - len / 2] == 0 ? 0 : MOD - ntth[i - len / 2]);
}
Span<uint> t = new uint[len];
{
Span<uint> ntth = new uint[len];
for (var i = 0; i < len - 1; ++i) ntth[i] = h_drv.ary[i];
LIB_NTT.ntt4(ref ntth);
for (var i = 0; i < len; ++i) ntth[i] = (uint)((ulong)ntth[i] * nttf[i * 2] % MOD);
LIB_NTT.ntt4(ref ntth, true);
for (var i = 1; i < len; ++i) t[i] = (uint)(((ulong)i * ary[i] + MOD - ntth[i - 1]) % MOD);
t[0] = ntth[len - 1] == 0 ? 0 : MOD - ntth[len - 1];
}
if (2 * len <= K)
{
Span<uint> newt = new uint[nextlen];
for (var i = 0; i < len; ++i) newt[i] = t[i];
LIB_NTT.ntt4(ref newt);
nttg = new uint[nextlen];
for (var i = 0; i < len; ++i) nttg[i] = g[i];
LIB_NTT.ntt4(ref nttg);
for (var i = 0; i < nextlen; ++i) newt[i] = (uint)((ulong)newt[i] * nttg[i] % MOD);
LIB_NTT.ntt4(ref newt, true);
for (var i = 0; i < len; ++i) t[i] = newt[i];
}
else
{
Span<uint> g1 = new uint[len];
Span<uint> s1 = new uint[len];
for (var i = 0; i < len / 2; ++i) g1[i] = g[i + len / 2];
for (var i = 0; i < len / 2; ++i) s1[i] = t[i + len / 2];
for (var i = len / 2; i < len; ++i) t[i] = 0;
LIB_NTT.ntt4(ref g1);
LIB_NTT.ntt4(ref s1);
LIB_NTT.ntt4(ref t);
for (var i = 0; i < len; ++i)
{
s1[i] = (uint)(((ulong)nttg[i] * s1[i] + (ulong)g1[i] * t[i]) % MOD);
t[i] = (uint)((ulong)nttg[i] * t[i] % MOD);
}
LIB_NTT.ntt4(ref t, true);
LIB_NTT.ntt4(ref s1, true);
for (var i = len / 2; i < len; ++i) t[i] = (t[i] + s1[i - len / 2]) % MOD;
}
{
Span<uint> ntth = new uint[nextlen];
var ten = Min(ary.Length, 2 * len);
for (var i = len; i < ten; ++i) ntth[i - len] = ary[i];
for (var i = 0; i < len; ++i) ntth[i] = (ntth[i] + MOD - (uint)(inv[i + len] * t[i] % MOD)) % MOD;
LIB_NTT.ntt4(ref ntth);
for (var i = 0; i < nextlen; ++i) ntth[i] = (uint)((ulong)ntth[i] * nttf[i] % MOD);
LIB_NTT.ntt4(ref ntth, true);
ten = Min(ary.Length - len, len);
for (var i = 0; i < ten; ++i) ary[i + len] = ntth[i];
}
len = nextlen;
}
}
/// <summary>
/// 対数 (a0 == 1)
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FPS Log()
{
var ret = Clone();
ret.Log_inplace();
return ret;
}
/// <summary>
/// 対数 (a0 == 1)
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Log_inplace()
{
if (K == 0)
{
ary[0] = 0;
return;
}
var dat = new List<(int idx, uint val)>();
for (var i = 1; i < ary.Length; ++i) if (ary[i] != 0) dat.Add((i, ary[i]));
if (dat.Count > 200)
{
Log_inplace_dense();
return;
}
// sparse
var g = new long[ary.Length - 1];
var inv = new long[ary.Length];
inv[1] = 1;
for (var i = 2; i < inv.Length; ++i) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
ary[0] = 0;
for (var n = 0; n < ary.Length - 1; ++n)
{
var rhs = (long)(n + 1) * ary[n + 1] % MOD;
foreach (var item in dat)
{
if (item.idx > n) break;
rhs = rhs - item.val * g[n - item.idx] % MOD;
if (rhs < 0) rhs += MOD;
}
g[n] = rhs;
ary[n + 1] = (uint)(rhs * inv[n + 1] % MOD);
}
}
/// <summary>
/// 対数 (a0 == 1)
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void Log_inplace_dense()
{
var f2 = Differential();
Inverse_inplace();
var len = 1;
while (len < ary.Length + f2.ary.Length - 1) len <<= 1;
Span<uint> nttdiff = new uint[len];
Span<uint> nttinv = new uint[len];
for (var i = 0; i < f2.ary.Length; ++i) nttdiff[i] = f2.ary[i];
for (var i = 0; i < ary.Length; ++i) nttinv[i] = ary[i];
LIB_NTT.ntt4(ref nttdiff);
LIB_NTT.ntt4(ref nttinv);
for (var i = 0; i < nttinv.Length; ++i) nttinv[i] = (uint)((long)nttinv[i] * nttdiff[i] % MOD);
LIB_NTT.ntt4(ref nttinv, true);
for (var i = 0; i < ary.Length; ++i) ary[i] = nttinv[i];
Integral_inplace();
}
/// <summary>
/// 微分
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FPS Differential()
{
var ret = Clone();
ret.Differential_inplace();
return ret;
}
/// <summary>
/// 微分
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Differential_inplace()
{
if (K == 0)
{
ary[0] = 0;
return;
}
for (var i = 1L; i < ary.Length; ++i) ary[i - 1] = (uint)(i * ary[i] % MOD);
ary[ary.Length - 1] = 0;
}
/// <summary>
/// 積分
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FPS Integral()
{
var ret = Clone();
ret.Integral_inplace();
return ret;
}
/// <summary>
/// 積分
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Integral_inplace()
{
var inv = new long[ary.Length];
inv[1] = 1;
for (var i = 2; i < inv.Length; ++i) inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
for (var i = ary.Length - 1; i > 0; --i) ary[i] = (uint)(inv[i] * ary[i - 1] % MOD);
ary[0] = 0;
}
/// <summary>
/// 逆元 (a0 != 0)
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_FPS Inverse()
{
var ret = Clone();
ret.Inverse_inplace();
return ret;
}
/// <summary>
/// 逆元 (a0 != 0)
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Inverse_inplace()
{
var dat = new List<(int idx, long val)>();
for (var i = 1; i < ary.Length; ++i) if (ary[i] != 0) dat.Add((i, ary[i]));
if (dat.Count > 160)
{
Inverse_inplace_dense();
return;
}
// sparse
ary[0] = (uint)LIB_Mod998244353.Inverse(ary[0]);
for (var n = 1; n < ary.Length; ++n)
{
var rhs = 0L;
foreach (var item in dat)
{
if (item.idx > n) break;
rhs -= item.val * ary[n - item.idx] % MOD;
}
rhs = (rhs % MOD) * ary[0] % MOD;
if (rhs < 0) rhs += MOD;
ary[n] = (uint)rhs;
}
}
/// <summary>
/// 逆元 (a0 != 0)
/// </summary>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Inverse_inplace_dense()
{
var maxlen = 1;
while (maxlen <= K) maxlen <<= 1;
var g = new uint[maxlen];
g[0] = (uint)LIB_Mod998244353.Inverse((long)ary[0]);
var len = 1;
while (len <= K)
{
var nextlen = len << 1;
Span<uint> nttf = new uint[nextlen];
Span<uint> nttg = new uint[nextlen];
var ten = Min(nextlen, ary.Length);
for (var i = 0; i < ten; ++i) nttf[i] = ary[i];
for (var i = 0; i < len; ++i) nttg[i] = g[i];
LIB_NTT.ntt4(ref nttf);
LIB_NTT.ntt4(ref nttg);
for (var i = 0; i < nextlen; ++i) nttf[i] = (uint)((ulong)nttf[i] * nttg[i] % MOD);
LIB_NTT.ntt4(ref nttf, true);
for (var i = 0; i < len; ++i) nttf[i] = 0;
LIB_NTT.ntt4(ref nttf);
for (var i = 0; i < nextlen; ++i) nttf[i] = (uint)((ulong)nttf[i] * nttg[i] % MOD);
LIB_NTT.ntt4(ref nttf, true);
for (var i = len; i < nextlen; ++i) g[i] = (nttf[i] == 0 ? 0 : MOD - nttf[i]);
len = nextlen;
}
for (var i = 0; i < ary.Length; ++i) ary[i] = g[i];
}
public long this[long index]
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get { return (long)ary[index]; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
set
{
var v = value % MOD;
ary[index] = (uint)(v < 0 ? v + MOD : v);
}
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public string Join(string separator = "") => string.Join(separator, ary);
}
class LIB_Deque<T>
{
T[] array;
int front, cap;
public int Count;
public T this[long i]
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get { return array[GetIndex((int)i)]; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
set { array[GetIndex((int)i)] = value; }
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_Deque(long cap = 16)
{
array = new T[this.cap = (int)cap];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
int GetIndex(int i)
{
if (i >= cap) throw new Exception();
var r = front + i;
return r >= cap ? r - cap : r;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void PushFront(T x)
{
if (Count == cap) Extend();
if (--front < 0) front += array.Length;
array[front] = x;
++Count;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public T PopFront()
{
if (Count-- == 0) throw new Exception();
var r = array[front++];
if (front >= cap) front -= cap;
return r;
}
public T Front => array[front];
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void PushBack(T x)
{
if (Count == cap) Extend();
var i = front + Count++;
array[i >= cap ? i - cap : i] = x;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public T PopBack()
{
if (Count == 0) throw new Exception();
return array[GetIndex(--Count)];
}
public T Back => array[GetIndex(Count - 1)];
[MethodImpl(MethodImplOptions.AggressiveInlining)]
void Extend()
{
T[] nb = new T[cap << 1];
if (front > cap - Count)
{
var l = array.Length - front; Array.Copy(array, front, nb, 0, l);
Array.Copy(array, 0, nb, l, Count - l);
}
else Array.Copy(array, front, nb, 0, Count);
array = nb; front = 0; cap <<= 1;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Insert(long i, T x)
{
if (i > Count) throw new Exception();
this.PushFront(x);
for (int j = 0; j < i; j++) this[j] = this[j + 1];
this[i] = x;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public T RemoveAt(long i)
{
if (i < 0 || i >= Count) throw new Exception();
var r = this[i];
for (var j = i; j > 0; j--) this[j] = this[j - 1];
this.PopFront();
return r;
}
}
class LIB_BarrettReduction
{
ulong MOD;
ulong mh;
ulong ml;
const ulong ALL1_32 = (ulong)~0U;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_BarrettReduction(ulong mod)
{
MOD = mod;
var m = ~0UL / MOD;
unchecked { if (m * MOD + MOD == 0) ++m; }
mh = m >> 32;
ml = m & ALL1_32;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public ulong Reduce(ulong x)
{
var z = (x & ALL1_32) * ml;
z = (x & ALL1_32) * mh + (x >> 32) * ml + (z >> 32);
z = (x >> 32) * mh + (z >> 32);
x -= z * MOD;
return x < MOD ? x : x - MOD;
}
}
partial struct LIB_Mod998244353 : IEquatable<LIB_Mod998244353>, IEquatable<long>
{
const int _mod = 998244353; long v;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public LIB_Mod998244353(long x)
{
if (x < _mod && x >= 0) v = x;
else if ((v = x % _mod) < 0) v += _mod;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public implicit operator LIB_Mod998244353(long x) => new LIB_Mod998244353(x);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public implicit operator long(LIB_Mod998244353 x) => x.v;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Add(LIB_Mod998244353 x) { if ((v += x.v) >= _mod) v -= _mod; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Sub(LIB_Mod998244353 x) { if ((v -= x.v) < 0) v += _mod; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Mul(LIB_Mod998244353 x) => v = (v * x.v) % _mod;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void Div(LIB_Mod998244353 x) => v = (v * Inverse(x.v)) % _mod;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_Mod998244353 operator +(LIB_Mod998244353 x, LIB_Mod998244353 y) { var t = x.v + y.v; return t >= _mod ? new LIB_Mod998244353 { v = t - _mod } : new LIB_Mod998244353 { v = t }; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_Mod998244353 operator -(LIB_Mod998244353 x, LIB_Mod998244353 y) { var t = x.v - y.v; return t < 0 ? new LIB_Mod998244353 { v = t + _mod } : new LIB_Mod998244353 { v = t }; }
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_Mod998244353 operator *(LIB_Mod998244353 x, LIB_Mod998244353 y) => x.v * y.v;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_Mod998244353 operator /(LIB_Mod998244353 x, LIB_Mod998244353 y) => x.v * Inverse(y.v);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public bool operator ==(LIB_Mod998244353 x, LIB_Mod998244353 y) => x.v == y.v;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public bool operator !=(LIB_Mod998244353 x, LIB_Mod998244353 y) => x.v != y.v;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public long Inverse(long x)
{
long b = _mod, r = 1, u = 0, t = 0;
while (b > 0)
{
var q = x / b;
t = u;
u = r - q * u;
r = t;
t = b;
b = x - q * b;
x = t;
}
return r < 0 ? r + _mod : r;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public bool Equals(LIB_Mod998244353 x) => v == x.v;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public bool Equals(long x) => v == x;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public override bool Equals(object x) => x == null ? false : Equals((LIB_Mod998244353)x);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public override int GetHashCode() => v.GetHashCode();
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public override string ToString() => v.ToString();
static List<LIB_Mod998244353> _fact = new List<LIB_Mod998244353>() { 1, 1 };
static List<LIB_Mod998244353> _inv = new List<LIB_Mod998244353>() { 0, 1 };
static List<LIB_Mod998244353> _factinv = new List<LIB_Mod998244353>() { 1, 1 };
static long _factm = _mod;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static void B(long n)
{
if (_factm != _mod)
{
_fact = new List<LIB_Mod998244353>() { 1, 1 };
_inv = new List<LIB_Mod998244353>() { 0, 1 };
_factinv = new List<LIB_Mod998244353>() { 1, 1 };
}
if (n >= _fact.Count)
{
for (int i = _fact.Count; i <= n; ++i)
{
_fact.Add(_fact[i - 1] * i);
_inv.Add(_mod - _inv[(int)(_mod % i)] * (_mod / i));
_factinv.Add(_factinv[i - 1] * _inv[i]);
}
}
_factm = _mod;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_Mod998244353 Comb(long n, long k)
{
B(n);
if (n == 0 && k == 0) return 1;
if (n < k || n < 0) return 0;
return _fact[(int)n] * _factinv[(int)(n - k)] * _factinv[(int)k];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_Mod998244353 CombOK(long n, long k)
{
LIB_Mod998244353 ret = 1;
LIB_Mod998244353 deno = 1;
var chk = n - k;
if (chk < k) k = chk;
for (var i = 0; i < k; i++) ret *= n - i;
for (var i = 1; i <= k; i++) deno *= i;
return ret / deno;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_Mod998244353 Perm(long n, long k)
{
B(n);
if (n == 0 && k == 0) return 1;
if (n < k || n < 0) return 0;
return _fact[(int)n] * _factinv[(int)(n - k)];
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_Mod998244353 KanzenPerm(long n, long k) => Enumerable.Range(0, (int)k + 1).Aggregate((LIB_Mod998244353)0, (a, e) => a + (1 - ((e & 1) << 1)) * LIB_Mod998244353.Comb(k, e) * LIB_Mod998244353.Perm(n - e, k - e));
[MethodImpl(MethodImplOptions.AggressiveInlining)]
static public LIB_Mod998244353 Pow(LIB_Mod998244353 x, long y)
{
LIB_Mod998244353 a = 1;
while (y != 0)
{
if ((y & 1) == 1) a.Mul(x);
x.Mul(x);
y >>= 1;
}
return a;
}
}
}