結果
問題 | No.2817 Competition |
ユーザー |
|
提出日時 | 2024-07-19 23:10:38 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 4,172 bytes |
コンパイル時間 | 276 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 199,504 KB |
最終ジャッジ日時 | 2024-07-19 23:10:42 |
合計ジャッジ時間 | 4,273 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 44 ms
58,240 KB |
testcase_01 | AC | 45 ms
53,120 KB |
testcase_02 | AC | 40 ms
52,736 KB |
testcase_03 | TLE | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
ソースコード
def primitive_root(m): if m == 2: return 1 if m == 167772161: return 3 if m == 469762049: return 3 if m == 754974721: return 11 if m == 998244353: return 3 divs = [2] x = (m - 1) // 2 while (x % 2 == 0): x //= 2 i = 3 while i * i <= x: if x % i == 0: divs.append(i) while x % i == 0: x //= i i += 2 if x > 1: divs.append(x) g = 2 while 1: if all(pow(g, (m - 1) // d, m) != 1 for d in divs): return g g += 1 class Convolution: def __init__(self, MOD = 998244353): self.MOD = MOD self.g = primitive_root(self.MOD) self.sum_e = [] self.sum_ie = [] es = [0] * 30 ies = [0] * 30 cnt2 = self.bsf(self.MOD - 1) e = pow(self.g, (self.MOD - 1) >> cnt2, self.MOD) ie = pow(e, self.MOD - 2, self.MOD) for i in range(cnt2, 1, -1): es[i - 2] = e ies[i - 2] = ie e *= e e %= self.MOD ie *= ie ie %= self.MOD now = 1 inow = 1 for i in range(cnt2 - 1): self.sum_e.append((es[i] * now) % self.MOD) now *= ies[i] now %= self.MOD self.sum_ie.append((ies[i] * inow) % self.MOD) inow *= es[i] inow %= self.MOD def butterfly(self, a): n = len(a) h = self.ceil_pow2(n) for ph in range(1, h + 1): w = 1 << (ph - 1) p = 1 << (h - ph) now = 1 for s in range(w): offset = s << (h - ph + 1) for i in range(p): l = a[i + offset] r = a[i + offset + p] * now a[i + offset] = (l + r) % self.MOD a[i + offset + p] = (l - r) % self.MOD now *= self.sum_e[self.bsf(~s)] now %= self.MOD return a def butterfly_inv(self, a): n = len(a) h = self.ceil_pow2(n) for ph in range(h, 0, -1): w = 1 << (ph - 1) p = 1 << (h - ph) inow = 1 for s in range(w): offset = s << (h - ph + 1) for i in range(p): l = a[i + offset] r = a[i + offset + p] a[i + offset] = (l + r) % self.MOD a[i + offset + p] = ((l - r) * inow) % self.MOD inow *= self.sum_ie[self.bsf(~s)] inow %= self.MOD return a def convolution(self, a, b): n = len(a) m = len(b) if n == 0 or m == 0: return [] if min(n, m) <= 60: if n < m: n, m = m, n a, b = b, a ans = [0] * (n + m - 1) for i in range(n): for j in range(m): ans[i + j] += a[i] * b[j] ans[i + j] %= self.MOD return ans z = 1 << self.ceil_pow2(n + m - 1) for _ in range(z - n): a.append(0) for _ in range(z - m): b.append(0) a = self.butterfly(a) b = self.butterfly(b) for i in range(z): a[i] *= b[i] a[i] %= self.MOD a = self.butterfly_inv(a)[:n + m - 1] iz = pow(z, self.MOD - 2, self.MOD) a = [(ai * iz) % self.MOD for ai in a] return a def bsf(self, x): ans = 0 t = 1 while x & t == 0: ans += 1 t <<= 1 return ans def ceil_pow2(self, x): return (x - 1).bit_length() if x != 1 else 0 MOD = 998244353 N = int(input()) A = list(map(int, input().split())) conv = Convolution(MOD) fs = [[1, A[i]] for i in range(N)] for i in range(70): l = 0 r = l + (1 << i) while r < N: fs[l] = conv.convolution(fs[l], fs[r]) l += (1 << (i + 1)) r = l + (1 << i) ans = 0 for k in range(1, N + 1): ans += fs[0][k] * pow(k, N - k, MOD) ans %= MOD # print(fs[0][k] * pow(k, N - k, MOD)) print(ans)