Submission #67005206

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
mod=998244353
N=int(input())
S=[input() for _ in range(N)]
child=[[-1, -1]] #[left, right]
cnt=[0]
dp=[0]
f=[False]
pow2=[1]*(N+1)
for i in range(1,N+1):
    pow2[i]=pow2[i-1]*2%mod
def culc(v):
    inc=pow2[cnt[v]-1] if f[v] else 0
    exc=1
    for d in [0,1]:
        c=child[v][d]
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

mod=998244353

N=int(input())
S=[input() for _ in range(N)]


child=[[-1, -1]] #[left, right]
cnt=[0]
dp=[0]
f=[False]


pow2=[1]*(N+1)
for i in range(1,N+1):
    pow2[i]=pow2[i-1]*2%mod

def culc(v):
    inc=pow2[cnt[v]-1] if f[v] else 0
    exc=1
    for d in [0,1]:
        c=child[v][d]
        if c==-1:
            exc=0
            break
        exc=exc*dp[c]%mod
    dp[v]=(inc+exc)%mod

for k in range(N):
    v=0
    path=[0]
    
    for ch in S[k]:
        d=1 if ch=="B" else 0
        
        if child[v][d]==-1:
            child[v][d]=len(child)
            child.append([-1, -1])
            cnt.append(0)
            dp.append(0)
            f.append(False)
            
        
        v=child[v][d]
        path.append(v)
    f[v]=True

    for u in reversed(path):
        cnt[u]+=1
        culc(u)

    print((dp[0]))

Submission Info

Judge Result