結果
問題 |
No.3040 Aoiスコア
|
ユーザー |
![]() |
提出日時 | 2025-02-28 22:04:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 212 ms / 1,000 ms |
コード長 | 7,889 bytes |
コンパイル時間 | 203 ms |
コンパイル使用メモリ | 82,300 KB |
実行使用メモリ | 81,464 KB |
最終ジャッジ日時 | 2025-06-20 20:57:59 |
合計ジャッジ時間 | 3,854 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
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,m=map(int,input().split()) S=input() e=[[] for i in range(n)] for i in range(m): a,b=map(int,input().split()) a-=1 b-=1 e[a]+=[b] e[b]+=[a] M=998244353 convolution=FFT(M) N=n fa=[1] for i in range(1,N+1): fa+=[fa[-1]*i%M] fb=[pow(fa[N],M-2,M)] for i in reversed(range(1,N+1)): fb+=[fb[-1]*i%M] fb.reverse() qc=S.count("?") ans=0 p26=[1] for i in range(n): p26+=[p26[-1]*26%M] p24=[1] for i in range(n): p24+=[p24[-1]*24%M] for s in range(n): if S[s]=="o" or S[s]=="?": c=[0,0,0] for t in e[s]: if S[t]=="a": c[0]+=1 if S[t]=="i": c[1]+=1 if S[t]=="?": c[2]+=1 q1=[(c[0]+i)*fb[i] for i in range(c[2]+1)] q2=[(c[1]+i)*fb[i] for i in range(c[2]+1)] q3=[p24[i]*fb[i] for i in range(c[2]+1)] q=convolution.convolution(q1,q2) q=convolution.convolution(q3,q) ans+=q[c[2]]*fa[c[2]]*p26[qc-c[2]-(S[s]=="?")] ans%=M print(ans)