結果
問題 |
No.3247 Multiplication 8 2
|
ユーザー |
![]() |
提出日時 | 2025-08-24 01:30:32 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 8,263 bytes |
コンパイル時間 | 251 ms |
コンパイル使用メモリ | 82,188 KB |
実行使用メモリ | 299,680 KB |
最終ジャッジ日時 | 2025-08-24 01:30:39 |
合計ジャッジ時間 | 7,092 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 3 TLE * 1 -- * 24 |
ソースコード
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,K=map(int,input().split()) A=list(map(int,input().split())) v=[0]*(N+1) t=0 z=1 v[0]=1 dp=[0]*(N+1) dp[0]=1 mod=998244353 p=[0]*(N+1) G=[[] for i in range(N+1)] G[0].append(0) for i in range(N): x=A[i] z*=x if z==8: t+=1 z=1 p[i+1]=t if z==1: dp[i+1]+=v[t-1] v[t]+=dp[i+1] v[t]%=mod G[t].append(i+1) if z!=1: print(0) exit() G[t]=[N] G[0]=[0] F=t cp=[0]*(N+1) cp[N]=1 v2=[0]*(N+1) t=0 z=1 v2[0]=1 for i in range(N-1,-1,-1): x=A[i] z*=x if z==8: t+=1 z=1 if z==1: cp[i]+=v2[t-1] v2[t]+=cp[i] v2[t]%=mod result=0 Z=FFT(mod) for e in range(1,F+1): d=G[e][-1]-G[e-1][0]+1 u=[0]*d v=[0]*d for pos in G[e-1]: a=pos-G[e-1][0] u[a]=cp[pos] v[G[e][-1]-pos]=dp[pos] for pos in G[e]: a=pos-G[e-1][0] u[a]=cp[pos] v[G[e][-1]-pos]=dp[pos] h=Z.convolution(u,v) for y in range(d,len(h)): result+=pow((y-(d-1)),K,mod)*h[y] result%=mod for e in range(F+1): d=G[e][-1]-G[e][0]+1 u=[0]*d v=[0]*d for pos in G[e]: a=pos-G[e][0] u[a]=cp[pos] v[G[e][-1]-pos]=dp[pos] h=Z.convolution(u,v) for y in range(d,len(h)): if e==0 or e==F: result-=pow((y-(d-1)),K,mod)*h[y] result%=mod else: result-=2*pow((y-(d-1)),K,mod)*h[y] result%=mod print(result)