結果
| 問題 | No.3540 Arise |
| コンテスト | |
| ユーザー |
 ゼット
|
| 提出日時 | 2026-05-27 01:12:07 |
| 言語 | PyPy3 (7.3.17) |
| 結果 |
TLE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 8,367 bytes |
| 記録 | |
| コンパイル時間 | 390 ms |
| コンパイル使用メモリ | 85,632 KB |
| 実行使用メモリ | 224,580 KB |
| 最終ジャッジ日時 | 2026-05-31 18:06:45 |
| 合計ジャッジ時間 | 39,043 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| サブタスク1 | 30 % | AC * 19 |
| サブタスク2 | 70 % | AC * 21 TLE * 1 |
| 合計 | 3.5 * 30% = 105 点 |
ソースコード
class FFT:
def primitive_root_constexpr(self, 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 = [0] * 20
divs[0] = 2
cnt = 1
x = (m - 1) // 2
while x % 2 == 0:
x //= 2
i = 3
while i * i <= x:
if x % i == 0:
divs[cnt] = i
cnt += 1
while x % i == 0:
x //= i
i += 2
if x > 1:
divs[cnt] = x
cnt += 1
g = 2
while 1:
ok = True
for i in range(cnt):
if pow(g, (m - 1) // divs[i], m) == 1:
ok = False
break
if ok:
return g
g += 1
def bsf(self, x):
res = 0
while x % 2 == 0:
res += 1
x //= 2
return res
rank2 = 0
root = []
iroot = []
rate2 = []
irate2 = []
rate3 = []
irate3 = []
def __init__(self, MOD):
self.mod = MOD
self.g = self.primitive_root_constexpr(self.mod)
self.rank2 = self.bsf(self.mod - 1)
self.root = [0 for i in range(self.rank2 + 1)]
self.iroot = [0 for i in range(self.rank2 + 1)]
self.rate2 = [0 for i in range(self.rank2)]
self.irate2 = [0 for i in range(self.rank2)]
self.rate3 = [0 for i in range(self.rank2 - 1)]
self.irate3 = [0 for i in range(self.rank2 - 1)]
self.root[self.rank2] = pow(self.g, (self.mod - 1) >> self.rank2, self.mod)
self.iroot[self.rank2] = pow(self.root[self.rank2], self.mod - 2, self.mod)
for i in range(self.rank2 - 1, -1, -1):
self.root[i] = (self.root[i + 1] ** 2) % self.mod
self.iroot[i] = (self.iroot[i + 1] ** 2) % self.mod
prod = 1
iprod = 1
for i in range(self.rank2 - 1):
self.rate2[i] = (self.root[i + 2] * prod) % self.mod
self.irate2[i] = (self.iroot[i + 2] * iprod) % self.mod
prod = (prod * self.iroot[i + 2]) % self.mod
iprod = (iprod * self.root[i + 2]) % self.mod
prod = 1
iprod = 1
for i in range(self.rank2 - 2):
self.rate3[i] = (self.root[i + 3] * prod) % self.mod
self.irate3[i] = (self.iroot[i + 3] * iprod) % self.mod
prod = (prod * self.iroot[i + 3]) % self.mod
iprod = (iprod * self.root[i + 3]) % self.mod
def butterfly(self, a):
n = len(a)
h = (n - 1).bit_length()
LEN = 0
while LEN < h:
if h - LEN == 1:
p = 1 << (h - LEN - 1)
rot = 1
for s in range(1 << LEN):
offset = s << (h - LEN)
for i in range(p):
l = a[i + offset]
r = a[i + offset + p] * rot
a[i + offset] = (l + r) % self.mod
a[i + offset + p] = (l - r) % self.mod
rot *= self.rate2[(~s & -~s).bit_length() - 1]
rot %= self.mod
LEN += 1
else:
p = 1 << (h - LEN - 2)
rot = 1
imag = self.root[2]
for s in range(1 << LEN):
rot2 = (rot * rot) % self.mod
rot3 = (rot2 * rot) % self.mod
offset = s << (h - LEN)
for i in range(p):
a0 = a[i + offset]
a1 = a[i + offset + p] * rot
a2 = a[i + offset + 2 * p] * rot2
a3 = a[i + offset + 3 * p] * rot3
a1na3imag = (a1 - a3) % self.mod * imag
a[i + offset] = (a0 + a2 + a1 + a3) % self.mod
a[i + offset + p] = (a0 + a2 - a1 - a3) % self.mod
a[i + offset + 2 * p] = (a0 - a2 + a1na3imag) % self.mod
a[i + offset + 3 * p] = (a0 - a2 - a1na3imag) % self.mod
rot *= self.rate3[(~s & -~s).bit_length() - 1]
rot %= self.mod
LEN += 2
def butterfly_inv(self, a):
n = len(a)
h = (n - 1).bit_length()
LEN = h
while LEN:
if LEN == 1:
p = 1 << (h - LEN)
irot = 1
for s in range(1 << (LEN - 1)):
offset = s << (h - LEN + 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) * irot % self.mod
irot *= self.irate2[(~s & -~s).bit_length() - 1]
irot %= self.mod
LEN -= 1
else:
p = 1 << (h - LEN)
irot = 1
iimag = self.iroot[2]
for s in range(1 << (LEN - 2)):
irot2 = (irot * irot) % self.mod
irot3 = (irot * irot2) % self.mod
offset = s << (h - LEN + 2)
for i in range(p):
a0 = a[i + offset]
a1 = a[i + offset + p]
a2 = a[i + offset + 2 * p]
a3 = a[i + offset + 3 * p]
a2na3iimag = (a2 - a3) * iimag % self.mod
a[i + offset] = (a0 + a1 + a2 + a3) % self.mod
a[i + offset + p] = (a0 - a1 + a2na3iimag) * irot % self.mod
a[i + offset + 2 * p] = (a0 + a1 - a2 - a3) * irot2 % self.mod
a[i + offset + 3 * p] = (
(a0 - a1 - a2na3iimag) * irot3 % self.mod
)
irot *= self.irate3[(~s & -~s).bit_length() - 1]
irot %= self.mod
LEN -= 2
def convolution(self, a, b):
n = len(a)
m = len(b)
if not (a) or not (b):
return []
if min(n, m) <= 40:
res = [0] * (n + m - 1)
for i in range(n):
for j in range(m):
res[i + j] += a[i] * b[j]
res[i + j] %= self.mod
return res
z = 1 << ((n + m - 2).bit_length())
a = a + [0] * (z - n)
b = b + [0] * (z - m)
self.butterfly(a)
self.butterfly(b)
c = [(a[i] * b[i]) % self.mod for i in range(z)]
self.butterfly_inv(c)
iz = pow(z, self.mod - 2, self.mod)
for i in range(n + m - 1):
c[i] = (c[i] * iz) % self.mod
return c[: n + m - 1]
N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
z=min(A)
mod=998244353
result=0
for i in range(N):
x=A[i]
result+=(1+x)*pow(2,-1,mod)
result%=mod
ncm=[[0]*(N+3) for i in range(N+2)]
ncm[0][0]=1
for x in range(1,N+2):
for y in range(x+1):
ncm[x][y]=ncm[x-1][y]+ncm[x-1][y-1]
ncm[x][y]%=mod
v=[0]*(N+1)
v[0]=z
for n in range(1,N+1):
ans=pow(z+1,n+1,mod)-1
for x in range(n):
ans-=ncm[n+1][x]*v[x]
ans%=mod
ans*=pow(n+1,-1,mod)
ans%=mod
v[n]=ans
dp=[[0]*(N+1) for i in range(N+1)]
dp[0][0]=1
for i in range(N):
x=A[i]
for j in range(i+1):
dp[i+1][j+1]-=dp[i][j]
dp[i+1][j+1]%=mod
dp[i+1][j]+=dp[i][j]*(x+1)
dp[i+1][j]%=mod
w=1
for i in range(N):
w*=A[i]
w%=mod
w=pow(w,-1,mod)
for x in range(N+1):
result-=dp[N][x]*v[x]*w
result%=mod
from collections import deque
Z=FFT(mod)
dp=[[0]*(N+1) for i in range(N+1)]
cp=[[0]*(N+1) for i in range(N+1)]
dp[0][0]=1
for i in range(N):
x=A[i]
for j in range(i+1):
dp[i+1][j]+=dp[i][j]*x
dp[i+1][j]%=mod
dp[i+1][j+1]-=dp[i][j]
dp[i+1][j+1]%=mod
cp[N][0]=1
for i in range(N-1,-1,-1):
x=A[i]
for j in range(N-i):
cp[i][j]+=cp[i+1][j]*(x+1)
cp[i][j]%=mod
cp[i][j+1]-=cp[i+1][j]
cp[i][j+1]%=mod
for i in range(N):
x=A[i]
h=Z.convolution(dp[i],cp[i+1])
for j in range(N):
result+=x*h[j]*v[j]*w
result%=mod
print(result)