結果
問題 | No.1307 Rotate and Accumulate |
ユーザー | keymoon |
提出日時 | 2020-05-28 15:28:20 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,150 ms / 5,000 ms |
コード長 | 6,066 bytes |
コンパイル時間 | 4,279 ms |
コンパイル使用メモリ | 111,012 KB |
実行使用メモリ | 61,068 KB |
最終ジャッジ日時 | 2023-10-12 09:51:49 |
合計ジャッジ時間 | 15,991 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 68 ms
23,896 KB |
testcase_01 | AC | 69 ms
21,952 KB |
testcase_02 | AC | 69 ms
21,840 KB |
testcase_03 | AC | 70 ms
23,960 KB |
testcase_04 | AC | 70 ms
21,828 KB |
testcase_05 | AC | 70 ms
22,012 KB |
testcase_06 | AC | 70 ms
22,016 KB |
testcase_07 | AC | 70 ms
21,892 KB |
testcase_08 | AC | 1,036 ms
50,644 KB |
testcase_09 | AC | 1,070 ms
45,872 KB |
testcase_10 | AC | 606 ms
44,676 KB |
testcase_11 | AC | 567 ms
41,844 KB |
testcase_12 | AC | 602 ms
41,616 KB |
testcase_13 | AC | 149 ms
30,616 KB |
testcase_14 | AC | 325 ms
40,264 KB |
testcase_15 | AC | 1,150 ms
59,016 KB |
testcase_16 | AC | 1,146 ms
61,068 KB |
testcase_17 | AC | 1,148 ms
57,116 KB |
testcase_18 | AC | 1,001 ms
48,896 KB |
testcase_19 | AC | 1,081 ms
59,036 KB |
testcase_20 | AC | 1,021 ms
59,044 KB |
testcase_21 | AC | 67 ms
21,856 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.IO; using System.Linq; using System.Numerics; using System.Text; using System.Text.RegularExpressions; using System.Threading.Tasks; using static System.Math; public static class P { public static void Main() { var mod1 = 998244353; ModInt.Mod = mod1; var nq = Console.ReadLine().Split().Select(int.Parse).ToArray(); var n = nq[0]; var q = nq[1]; var a = Console.ReadLine().Split().Select(x => new ModInt(int.Parse(x))).ToArray(); var b = new ModInt[n]; foreach (var item in Console.ReadLine().Split().Select(int.Parse).ToArray()) { b[item == 0 ? 0 : n - item] += 1; } ModInt.Mod = mod1; var res1 = NumberTheoreticTransform.Convolute(a, b); var mod2 = 469762049; ModInt.Mod = mod2; var res2 = NumberTheoreticTransform.Convolute(a, b); var inv = 1 / new ModInt(mod1); var fftres = res1.Zip(res2, (x, y) => (long)(((int)y - (int)x) * inv) * mod1 + (int)x).ToArray(); long[] res = new long[n]; for (int i = 0; i < n; i++) { long item = 0; if (i < fftres.Length) item += fftres[i]; if (n + i < fftres.Length) item += fftres[n + i]; res[i] = item; } Console.WriteLine(string.Join(" ", res)); } static long ExtGCD(long a, long b, out long x, out long y) { long div; long x1 = 1, y1 = 0, x2 = 0, y2 = 1; while (true) { if (b == 0) { x = x1; y = y1; return a; } div = a / b; x1 -= x2 * div; y1 -= y2 * div; a %= b; if (a == 0) { x = x2; y = y2; return b; } div = b / a; x2 -= x1 * div; y2 -= y1 * div; b %= a; } } } class NumberTheoreticTransform { const int primitive_root = 3; static NumberTheoreticTransform() { } public static ModInt[] Convolute(ModInt[] A, ModInt[] B) { int sz = A.Length + B.Length - 1; int N = 1; while (N < sz) N <<= 1; var G = new ModInt[N]; Array.Copy(A, G, A.Length); var H = new ModInt[N]; Array.Copy(B, H, B.Length); NTT(G); NTT(H); for (int i = 0; i < N; i++) G[i] *= H[i]; NTT(G, -1); Array.Resize(ref G, sz); return G; } static void NTT(ModInt[] F, int rev = 1) { int N = F.Length; ModInt h = ModInt.Pow(primitive_root, (ModInt.Mod - 1) / N); if (rev == -1) h = 1 / h; for (int i = 0, j = 1; j < N - 1; j++) { for (int k = N >> 1; k > (i ^= k); k >>= 1) ; if (j < i) { var tmp = F[i]; F[i] = F[j]; F[j] = tmp; } } for (int i = 2; i <= N; i <<= 1) { int m = i >> 1; // zeta = exp(rev * PI / m * i) ModInt zeta = ModInt.Pow(h, N / i); for (int j = 0; j < N; j += i) { ModInt zeta_pow = 1; for (int u = j, v = j + m; v < j + i; u++, v++) { ModInt vl = F[u], vr = zeta_pow * F[v]; F[u] = vl + vr; F[v] = vl - vr; zeta_pow = zeta_pow * zeta; } } } if (rev == -1) { ModInt n_inv = (ModInt)1 / N; for (int i = 0; i < F.Length; i++) { F[i] *= n_inv; } } } } struct ModInt { public static int mod; public static int Mod { get { return mod; } set { POSITIVIZER = ((long)value) << 31; mod = value; } } static long POSITIVIZER; long Data; public ModInt(long data) { if ((Data = data % Mod) < 0) Data += Mod; } public static implicit operator long(ModInt modInt) => modInt.Data; public static implicit operator ModInt(long val) => new ModInt(val); public static ModInt operator +(ModInt a, int b) => new ModInt() { Data = (a.Data + b + POSITIVIZER) % Mod }; public static ModInt operator +(ModInt a, long b) => new ModInt(a.Data + b); public static ModInt operator +(ModInt a, ModInt b) { long res = a.Data + b.Data; return new ModInt() { Data = res >= Mod ? res - Mod : res }; } public static ModInt operator -(ModInt a, int b) => new ModInt() { Data = (a.Data - b + POSITIVIZER) % Mod }; public static ModInt operator -(ModInt a, long b) => new ModInt(a.Data - b); public static ModInt operator -(ModInt a, ModInt b) { long res = a.Data - b.Data; return new ModInt() { Data = res < 0 ? res + Mod : res }; } public static ModInt operator *(ModInt a, int b) => new ModInt(a.Data * b); public static ModInt operator *(ModInt a, long b) => a * new ModInt(b); public static ModInt operator *(ModInt a, ModInt b) => new ModInt() { Data = a.Data * b.Data % Mod }; public static ModInt operator /(ModInt a, ModInt b) => new ModInt() { Data = a.Data * GetInverse(b) % Mod }; public static bool operator ==(ModInt a, ModInt b) => a.Data == b.Data; public static bool operator !=(ModInt a, ModInt b) => a.Data != b.Data; public override string ToString() => Data.ToString(); public override bool Equals(object obj) => (ModInt)obj == this; public override int GetHashCode() => (int)Data; static long GetInverse(long a) { long div, p = Mod, x1 = 1, y1 = 0, x2 = 0, y2 = 1; while (true) { if (p == 1) return x2 + Mod; div = a / p; x1 -= x2 * div; y1 -= y2 * div; a %= p; if (a == 1) return x1 + Mod; div = p / a; x2 -= x1 * div; y2 -= y1 * div; p %= a; } } public static ModInt Pow(ModInt n, long m) { ModInt pow = n; ModInt res = 1; while (m > 0) { if ((m & 1) == 1) res *= pow; pow *= pow; m >>= 1; } return res; } }