結果
問題 | No.1387 Mitarushi's Remodeling |
ユーザー | googol_S0 |
提出日時 | 2021-02-07 22:27:58 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,138 ms / 2,000 ms |
コード長 | 3,234 bytes |
コンパイル時間 | 2,352 ms |
コンパイル使用メモリ | 86,312 KB |
実行使用メモリ | 271,012 KB |
最終ジャッジ日時 | 2023-09-15 12:07:03 |
合計ジャッジ時間 | 79,877 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 407 ms
258,984 KB |
testcase_01 | AC | 332 ms
259,020 KB |
testcase_02 | AC | 324 ms
259,084 KB |
testcase_03 | AC | 329 ms
259,216 KB |
testcase_04 | AC | 328 ms
259,204 KB |
testcase_05 | AC | 328 ms
258,796 KB |
testcase_06 | AC | 331 ms
258,924 KB |
testcase_07 | AC | 330 ms
259,152 KB |
testcase_08 | AC | 378 ms
258,952 KB |
testcase_09 | AC | 385 ms
259,448 KB |
testcase_10 | AC | 378 ms
259,084 KB |
testcase_11 | AC | 377 ms
259,148 KB |
testcase_12 | AC | 377 ms
259,076 KB |
testcase_13 | AC | 380 ms
259,288 KB |
testcase_14 | AC | 1,100 ms
267,284 KB |
testcase_15 | AC | 1,046 ms
267,276 KB |
testcase_16 | AC | 1,060 ms
266,840 KB |
testcase_17 | AC | 1,118 ms
267,392 KB |
testcase_18 | AC | 1,055 ms
267,140 KB |
testcase_19 | AC | 1,048 ms
266,688 KB |
testcase_20 | AC | 1,065 ms
267,064 KB |
testcase_21 | AC | 1,116 ms
267,044 KB |
testcase_22 | AC | 1,075 ms
267,084 KB |
testcase_23 | AC | 1,085 ms
266,272 KB |
testcase_24 | AC | 1,052 ms
266,816 KB |
testcase_25 | AC | 1,069 ms
266,384 KB |
testcase_26 | AC | 1,078 ms
266,576 KB |
testcase_27 | AC | 1,087 ms
266,700 KB |
testcase_28 | AC | 1,110 ms
267,204 KB |
testcase_29 | AC | 1,106 ms
267,304 KB |
testcase_30 | AC | 1,085 ms
267,152 KB |
testcase_31 | AC | 1,110 ms
266,744 KB |
testcase_32 | AC | 1,044 ms
267,076 KB |
testcase_33 | AC | 1,074 ms
266,616 KB |
testcase_34 | AC | 1,070 ms
266,836 KB |
testcase_35 | AC | 1,098 ms
267,456 KB |
testcase_36 | AC | 1,094 ms
267,016 KB |
testcase_37 | AC | 1,087 ms
267,564 KB |
testcase_38 | AC | 1,085 ms
267,184 KB |
testcase_39 | AC | 1,039 ms
266,264 KB |
testcase_40 | AC | 1,104 ms
266,380 KB |
testcase_41 | AC | 1,122 ms
267,236 KB |
testcase_42 | AC | 1,112 ms
266,916 KB |
testcase_43 | AC | 1,108 ms
266,948 KB |
testcase_44 | AC | 1,138 ms
267,572 KB |
testcase_45 | AC | 1,135 ms
267,700 KB |
testcase_46 | AC | 1,112 ms
266,240 KB |
testcase_47 | AC | 1,122 ms
267,568 KB |
testcase_48 | AC | 1,109 ms
267,636 KB |
testcase_49 | AC | 1,122 ms
267,084 KB |
testcase_50 | AC | 1,125 ms
267,412 KB |
testcase_51 | AC | 1,118 ms
266,324 KB |
testcase_52 | AC | 1,128 ms
267,168 KB |
testcase_53 | AC | 1,031 ms
266,688 KB |
testcase_54 | AC | 1,031 ms
266,744 KB |
testcase_55 | AC | 1,034 ms
267,408 KB |
testcase_56 | AC | 1,015 ms
267,232 KB |
testcase_57 | AC | 1,011 ms
266,712 KB |
testcase_58 | AC | 1,016 ms
267,240 KB |
testcase_59 | AC | 1,082 ms
266,416 KB |
testcase_60 | AC | 1,008 ms
267,484 KB |
testcase_61 | AC | 1,010 ms
266,396 KB |
testcase_62 | AC | 1,016 ms
267,648 KB |
testcase_63 | AC | 1,109 ms
267,800 KB |
testcase_64 | AC | 1,111 ms
267,544 KB |
testcase_65 | AC | 1,066 ms
268,008 KB |
testcase_66 | AC | 1,135 ms
267,916 KB |
testcase_67 | AC | 1,090 ms
267,660 KB |
testcase_68 | AC | 959 ms
267,984 KB |
testcase_69 | AC | 957 ms
271,012 KB |
ソースコード
_fft_mod = 998244353 _fft_sum_e = [911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601, 842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 0, 0, 0, 0, 0, 0, 0, 0, 0] _fft_sum_ie = [86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960, 354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 0, 0, 0, 0, 0, 0, 0, 0, 0] def butterfly_998244353(a): n = len(a) h = (n - 1).bit_length() 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 % _fft_mod a[i + offset] = (l + r) % _fft_mod a[i + offset + p] = (l - r) % _fft_mod now = now * _fft_sum_e[(~s & -~s).bit_length() - 1] % _fft_mod def butterfly_inv_998244353(a): n = len(a) h = (n - 1).bit_length() 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) % _fft_mod a[i + offset + p] = (l - r) * inow % _fft_mod inow = inow * _fft_sum_ie[(~s & -~s).bit_length() - 1] % _fft_mod def convolution_998244353(a, b): a = a.copy() b = b.copy() 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] = (ans[i + j] + a[i] * b[j] % _fft_mod) % _fft_mod return ans z = 1 << (n + m - 2).bit_length() a += [0] * (z - n) b += [0] * (z - m) butterfly_998244353(a) butterfly_998244353(b) for i in range(z): a[i] = a[i] * b[i] % _fft_mod butterfly_inv_998244353(a) a = a[:n + m - 1] iz = pow(z, _fft_mod - 2, _fft_mod) for i in range(n + m - 1): a[i] = a[i] * iz % _fft_mod return a mod=998244353 def cmb(n,r): if r<0 or r>n: return 0 return (g1[n]*g2[r]*g2[n-r])%mod g1=[1,1] g2=[1,1] inv=[0,1] for i in range(2,1000003): g1.append((g1[-1]*i)%mod) inv.append((-inv[mod%i]*(mod//i))%mod) g2.append((g2[-1]*inv[-1])%mod) g2.append(1) G=[1,1] for i in range(1,1000003): G.append((G[-1]*i+1)%mod) def psum(N,K): if N<K: K=N return (g1[N]*G[N-K]*(K-N)*g2[N-K]+G[N+1]-1)%mod def solve(A,N,K): P=0 B=convolution_998244353(A[:], A[::-1]) for i in range(N-1): P+=B[i]*(psum(N-1,K)-psum(N-1-abs(N-1-i),K)) return P%mod N,K=map(int,input().split()) M=list(map(int,input().split())) X=1 for i in range(N): X=X*M[i]%mod inv=pow(2,mod-2,mod) A=[(M[i]+1)*inv%mod for i in range(N)] ANS=solve(A,N,K) print(ANS*X%mod)