結果
問題 | No.1677 mæx |
ユーザー |
![]() |
提出日時 | 2022-10-04 04:42:44 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,351 bytes |
コンパイル時間 | 370 ms |
コンパイル使用メモリ | 13,440 KB |
実行使用メモリ | 31,360 KB |
最終ジャッジ日時 | 2024-12-29 07:57:27 |
合計ジャッジ時間 | 5,413 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 2 RE * 16 |
ソースコード
import sys input = sys.stdin.readline sys.setrecursionlimit(2*10**5) S=input().strip() K=int(input()) mod=998244353 if len(S)==1: if S=="?": print(1) else: x=int(S) if K==x: print(1) else: print(0) exit() now=0 X=[[-1,-1] for i in range(len(S))] IND=[] for i in range(len(S)): if S[i]=="m": IND.append(i) elif S[i]==",": X[IND[-1]][0]=i elif S[i]==")": X[IND[-1]][1]=i IND.pop() from functools import lru_cache @lru_cache(maxsize=None) def calc(fr,to,x): #print(fr,to,x) if fr==to: if S[fr]=="?": return 1 y=int(S[fr]) if y==x: return 1 else: return 0 T=S[fr:fr+3] if T=="max": if x==0: return calc(fr+4,X[fr][0]-1,0)*calc(X[fr][0]+1,X[fr][1]-1,0)%mod elif x==1: return (calc(fr+4,X[fr][0]-1,0)*calc(X[fr][0]+1,X[fr][1]-1,1)%mod+calc(fr+4,X[fr][0]-1,1)*calc(X[fr][0]+1,X[fr][1]-1,0)%mod+calc(fr+4,X[fr][0]-1,1)*calc(X[fr][0]+1,X[fr][1]-1,1)%mod)%mod else: return (calc(fr+4,X[fr][0]-1,0)*calc(X[fr][0]+1,X[fr][1]-1,2)%mod+calc(fr+4,X[fr][0]-1,1)*calc(X[fr][0]+1,X[fr][1]-1,2)%mod+calc(fr+4,X[fr][0]-1,2)*calc(X[fr][0]+1,X[fr][1]-1,0)%mod+calc(fr+4,X[fr][0]-1,2)*calc(X[fr][0]+1,X[fr][1]-1,1)%mod+calc(fr+4,X[fr][0]-1,2)*calc(X[fr][0]+1,X[fr][1]-1,2)%mod)%mod elif T=="mex": if x==0: return (calc(fr+4,X[fr][0]-1,1)*calc(X[fr][0]+1,X[fr][1]-1,1)%mod + calc(fr+4,X[fr][0]-1,1)*calc(X[fr][0]+1,X[fr][1]-1,2)%mod +calc(fr+4,X[fr][0]-1,2)*calc(X[fr][0]+1,X[fr][1]-1,1)%mod + calc(fr+4,X[fr][0]-1,2)*calc(X[fr][0]+1,X[fr][1]-1,2)%mod )%mod elif x==1: return (calc(fr+4,X[fr][0]-1,0)*calc(X[fr][0]+1,X[fr][1]-1,0)%mod + calc(fr+4,X[fr][0]-1,0)*calc(X[fr][0]+1,X[fr][1]-1,2)%mod + calc(fr+4,X[fr][0]-1,2)*calc(X[fr][0]+1,X[fr][1]-1,0)%mod)%mod else: return (calc(fr+4,X[fr][0]-1,0)*calc(X[fr][0]+1,X[fr][1]-1,1)%mod+calc(fr+4,X[fr][0]-1,1)*calc(X[fr][0]+1,X[fr][1]-1,0)%mod)%mod else: if x==0: return (calc(fr+4,X[fr][0]-1,0)*calc(X[fr][0]+1,X[fr][1]-1,0)%mod +calc(fr+4,X[fr][0]-1,1)*calc(X[fr][0]+1,X[fr][1]-1,1)%mod + calc(fr+4,X[fr][0]-1,1)*calc(X[fr][0]+1,X[fr][1]-1,2)%mod +calc(fr+4,X[fr][0]-1,2)*calc(X[fr][0]+1,X[fr][1]-1,1)%mod + calc(fr+4,X[fr][0]-1,2)*calc(X[fr][0]+1,X[fr][1]-1,2)%mod )%mod elif x==1: return ((calc(fr+4,X[fr][0]-1,0)*calc(X[fr][0]+1,X[fr][1]-1,1)%mod+calc(fr+4,X[fr][0]-1,1)*calc(X[fr][0]+1,X[fr][1]-1,0)%mod+calc(fr+4,X[fr][0]-1,1)*calc(X[fr][0]+1,X[fr][1]-1,1)%mod)%mod + calc(fr+4,X[fr][0]-1,0)*calc(X[fr][0]+1,X[fr][1]-1,0)%mod + calc(fr+4,X[fr][0]-1,0)*calc(X[fr][0]+1,X[fr][1]-1,2)%mod + calc(fr+4,X[fr][0]-1,2)*calc(X[fr][0]+1,X[fr][1]-1,0)%mod)%mod else: return ((calc(fr+4,X[fr][0]-1,0)*calc(X[fr][0]+1,X[fr][1]-1,2)%mod+calc(fr+4,X[fr][0]-1,1)*calc(X[fr][0]+1,X[fr][1]-1,2)%mod+calc(fr+4,X[fr][0]-1,2)*calc(X[fr][0]+1,X[fr][1]-1,0)%mod+calc(fr+4,X[fr][0]-1,2)*calc(X[fr][0]+1,X[fr][1]-1,1)%mod+calc(fr+4,X[fr][0]-1,2)*calc(X[fr][0]+1,X[fr][1]-1,2)%mod)%mod + (calc(fr+4,X[fr][0]-1,0)*calc(X[fr][0]+1,X[fr][1]-1,1)%mod+calc(fr+4,X[fr][0]-1,1)*calc(X[fr][0]+1,X[fr][1]-1,0)%mod)%mod)%mod print(calc(0,X[0][1],K)%mod)