結果
問題 | No.1387 Mitarushi's Remodeling |
ユーザー |
|
提出日時 | 2021-02-07 22:03:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,044 ms / 2,000 ms |
コード長 | 2,580 bytes |
コンパイル時間 | 239 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 300,748 KB |
最終ジャッジ日時 | 2024-07-04 15:36:01 |
合計ジャッジ時間 | 62,273 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 67 |
ソースコード
mod = 998244353 omega = pow(3,119,mod) rev_omega = pow(omega,mod-2,mod) N = 5*10**5 g1 = [1]*(N+1) # 元テーブル g2 = [1]*(N+1) #逆元テーブル inv = [1]*(N+1) #逆元テーブル計算用テーブル for i in range( 2, N + 1 ): g1[i]=( ( g1[i-1] * i ) % mod ) inv[i]=( ( -inv[mod % i] * (mod//i) ) % mod ) g2[i]=( (g2[i-1] * inv[i]) % mod ) inv[0]=0 def _ntt(f,L,reverse=False): F=[f[i] for i in range(L)] n = L.bit_length() - 1 base = omega if reverse: base = rev_omega if not n: return F size = 2**n wj = pow(base,2**22,mod) res = [0]*2**n for i in range(n,0,-1): use_omega = pow(base,2**(22+i-n),mod) res = [0]*2**n size //= 2 w = 1 for j in range(0,L//2,size): for a in range(size): res[a+j] = (F[a+2*j] + w * F[a+size+2*j]) % mod t = (w * wj) % mod res[L//2+a+j] = (F[a+2*j] + t * F[a+size+2*j]) % mod w = (w * use_omega) % mod F = res return res def ntt(f,L=0): l = len(f) if not L: L = 1<<((l-1).bit_length()) while len(f)<L: f.append(0) f=f[:L] F = _ntt(f,L) return F def intt(f,L=0): l = len(f) if not L: L = 1<<((l-1).bit_length()) while len(f)<L: f.append(0) f=f[:L] F = _ntt(f,L,reverse=True) inv = pow(L,mod-2,mod) for i in range(L): F[i] *= inv F[i] %= mod return F def convolve(f,g,limit): l = len(f)+len(g)-1 L = 1<<((l-1).bit_length()) F = ntt(f,L) G = ntt(g,L) H = [(F[i] * G[i]) % mod for i in range(L)] h = intt(H,L) return h[:limit] inv2 = pow(2,mod-2,mod) N,K = map(int,input().split()) M = list(map(int,input().split())) c = 1 for m in M: c *= m c %= mod M = [(M[i]+1)*inv2 % mod for i in range(N)] Mi = [M[N-i-1] for i in range(N)] conv = convolve(M,Mi,2*N)[N-1:] check = [conv[i]*4 % mod for i in range(N)] imos = [g2[i] for i in range(N)] for i in range(1,N): imos[i] += imos[i-1] imos[i] %= mod prod = [N-1 for i in range(K+1)] for i in range(2,K+1): prod[i] = (prod[i-1] * (N-i)) % mod prod[0] = 0 imos_prod = [prod[i] for i in range(K+1)] for i in range(1,K+1): imos_prod[i] += imos_prod[i-1] imos_prod[i] %= mod res = imos_prod[K] * conv[N-1] % mod for x in range(1,N-1): L = 1 R = min(K,N-1-x) tmp = g1[N-1-x] * (imos[N-1-x-L] - imos[N-1-x-R] + g2[N-1-x-R]) tmp2 = (imos_prod[K] - tmp) % mod res += tmp2 * conv[x] res %= mod print(res*c % mod)