#981310 (PyPy3) No.1857 Gacha Addiction

提出ソース

結果

問題	No.1857 Gacha Addiction
ユーザー	tassei903
提出日時	2024-05-12 14:41:06
言語	PyPy3 (7.3.15)
結果	AC
実行時間	1,073 ms / 6,000 ms
コード長	5,290 bytes
コンパイル時間	349 ms
コンパイル使用メモリ	82,344 KB
実行使用メモリ	156,872 KB
最終ジャッジ日時	2024-12-20 09:07:26
合計ジャッジ時間	35,900 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	72 ms 77,652 KB
testcase_01	AC	73 ms 77,776 KB
testcase_02	AC	71 ms 77,736 KB
testcase_03	AC	73 ms 77,800 KB
testcase_04	AC	164 ms 93,784 KB
testcase_05	AC	159 ms 93,508 KB
testcase_06	AC	182 ms 93,900 KB
testcase_07	AC	164 ms 93,992 KB
testcase_08	AC	165 ms 93,756 KB
testcase_09	AC	450 ms 109,160 KB
testcase_10	AC	463 ms 109,808 KB
testcase_11	AC	453 ms 109,304 KB
testcase_12	AC	452 ms 109,364 KB
testcase_13	AC	447 ms 109,364 KB
testcase_14	AC	1,046 ms 156,108 KB
testcase_15	AC	1,048 ms 156,868 KB
testcase_16	AC	1,059 ms 156,492 KB
testcase_17	AC	1,045 ms 155,980 KB
testcase_18	AC	1,046 ms 156,872 KB
testcase_19	AC	1,039 ms 156,232 KB
testcase_20	AC	1,052 ms 156,656 KB
testcase_21	AC	1,073 ms 156,492 KB
testcase_22	AC	1,052 ms 156,872 KB
testcase_23	AC	1,040 ms 156,616 KB
testcase_24	AC	1,039 ms 156,496 KB
testcase_25	AC	1,030 ms 156,852 KB
testcase_26	AC	1,036 ms 156,736 KB
testcase_27	AC	1,042 ms 156,604 KB
testcase_28	AC	1,028 ms 156,616 KB
testcase_29	AC	1,052 ms 156,528 KB
testcase_30	AC	1,041 ms 156,596 KB
testcase_31	AC	1,060 ms 156,744 KB
testcase_32	AC	1,056 ms 156,752 KB
testcase_33	AC	1,054 ms 156,744 KB
testcase_34	AC	1,041 ms 156,760 KB
testcase_35	AC	1,053 ms 156,464 KB
testcase_36	AC	1,032 ms 156,868 KB
testcase_37	AC	1,032 ms 156,768 KB
testcase_38	AC	1,041 ms 156,452 KB
testcase_39	AC	476 ms 111,940 KB
testcase_40	AC	492 ms 112,428 KB
testcase_41	AC	573 ms 121,360 KB
testcase_42	AC	271 ms 97,072 KB
testcase_43	AC	943 ms 148,492 KB
testcase_44	AC	1,028 ms 155,196 KB
testcase_45	AC	73 ms 76,980 KB
testcase_46	AC	74 ms 76,912 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################
MOD = 998244353
IMAG = 911660635
IIMAG = 86583718
rate2 = (0, 911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 867605899, 0)
irate2 = (0, 86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 103369235, 0)
rate3 = (0, 372528824, 337190230, 454590761, 816400692, 578227951, 180142363, 83780245, 6597683, 70046822, 623238099, 183021267, 402682409, 631680428, 344509872, 689220186, 365017329, 774342554, 729444058, 102986190, 128751033, 395565204, 0)
irate3 = (0, 509520358, 929031873, 170256584, 839780419, 282974284, 395914482, 444904435, 72135471, 638914820, 66769500, 771127074, 985925487, 262319669, 262341272, 625870173, 768022760, 859816005, 914661783, 430819711, 272774365, 530924681, 0)

def butterfly(a):
  n = len(a)
  h = (n - 1).bit_length()
  le = 0
  while le < h:
    if h - le == 1:
      p = 1 << (h - le - 1)
      rot = 1
      for s in range(1 << le):
        offset = s << (h - le)
        for i in range(p):
          l = a[i + offset]
          r = a[i + offset + p] * rot
          a[i + offset] = (l + r) % MOD
          a[i + offset + p] = (l - r) % MOD
        rot *= rate2[(~s & -~s).bit_length()]
        rot %= MOD
      le += 1
    else:
      p = 1 << (h - le - 2)
      rot = 1
      for s in range(1 << le):
        rot2 = rot * rot % MOD
        rot3 = rot2 * rot % MOD
        offset = s << (h - le)
        for i in range(p):
          a0 = a[i + offset]
          a1 = a[i + offset + p] * rot
          a2 = a[i + offset + p * 2] * rot2
          a3 = a[i + offset + p * 3] * rot3
          a1na3imag = (a1 - a3) % MOD * IMAG
          a[i + offset] = (a0 + a2 + a1 + a3) % MOD
          a[i + offset + p] = (a0 + a2 - a1 - a3) % MOD
          a[i + offset + p * 2] = (a0 - a2 + a1na3imag) % MOD
          a[i + offset + p * 3] = (a0 - a2 - a1na3imag) % MOD
        rot *= rate3[(~s & -~s).bit_length()]
        rot %= MOD
      le += 2

def butterfly_inv(a):
  n = len(a)
  h = (n - 1).bit_length()
  le = h
  while le:
    if le == 1:
      p = 1 << (h - le)
      irot = 1
      for s in range(1 << (le - 1)):
        offset = s << (h - le + 1)
        for i in range(p):
          l = a[i + offset]
          r = a[i + offset + p]
          a[i + offset] = (l + r) % MOD
          a[i + offset + p] = (l - r) * irot % MOD
        irot *= irate2[(~s & -~s).bit_length()]
        irot %= MOD
      le -= 1
    else:
      p = 1 << (h - le)
      irot = 1
      for s in range(1 << (le - 2)):
        irot2 = irot * irot % MOD
        irot3 = irot2 * irot % MOD
        offset = s << (h - le + 2)
        for i in range(p):
          a0 = a[i + offset]
          a1 = a[i + offset + p]
          a2 = a[i + offset + p * 2]
          a3 = a[i + offset + p * 3]
          a2na3iimag = (a2 - a3) * IIMAG % MOD
          a[i + offset] = (a0 + a1 + a2 + a3) % MOD
          a[i + offset + p] = (a0 - a1 + a2na3iimag) * irot % MOD
          a[i + offset + p * 2] = (a0 + a1 - a2 - a3) * irot2 % MOD
          a[i + offset + p * 3] = (a0 - a1 - a2na3iimag) * irot3 % MOD
        irot *= irate3[(~s & -~s).bit_length()]
        irot %= MOD
      le -= 2

def multiply(s, t):
  n = len(s)
  m = len(t)
  if min(n, m) <= 60:
    a = [0] * (n + m - 1)
    for i in range(n):
      if i % 8 == 0:        
        for j in range(m):
          a[i + j] += s[i] * t[j]
          a[i + j] %= MOD
      else:
        for j in range(m):
          a[i + j] += s[i] * t[j]
    return [x % MOD for x in a]
  a = s.copy()
  b = t.copy()
  z = 1 << (n + m - 2).bit_length()
  a += [0] * (z - n)
  b += [0] * (z - m)
  butterfly(a)
  butterfly(b)
  for i in range(z):
    a[i] *= b[i]
    a[i] %= MOD
  butterfly_inv(a)
  a = a[:n + m - 1]
  iz = pow(z, MOD - 2, MOD)
  return [v * iz % MOD for v in a]

mod = 998244353
nn = 10**6
fact = [1] * nn
for i in range(nn - 1):
    fact[i + 1] = fact[i] * (i + 1) % mod
invfact = [1] * nn
invfact[nn - 1] = pow(fact[nn - 1], mod - 2, mod)
for i in range(nn - 1)[::-1]:
    invfact[i] = invfact[i + 1] * (i + 1) % mod
 
def binom(x, y):
    if x < 0 or y < 0 or x - y < 0:
        return 0
    return fact[x] * invfact[y] % mod * invfact[x - y] % mod

def p(n, k):
    return fact[n] * invfact[n - k] % mod

def pinv(n, k):
    return invfact[n] * fact[n - k] % mod

n, s = na()
a = na()
sinv = pow(s, mod-2, mod)

from collections import deque
b = deque()
for i in range(n):
    b.append((1, a[i]*sinv%mod))

#print(b)
while len(b) > 1:
    x = b.popleft()
    y = b.popleft()
    b.append(multiply(x, y))

b = b[0]

#print(b)


ans = 0
M = sum(a)

for i in range(n+1):
   ans += b[i]*fact[i] %mod
   ans %= mod

print(ans)

yukicoder

結果

テストケース

ソースコード