Submission #69685779

---

Source Code Expand

import sys
from collections import defaultdict
MOD=998244353
input=sys.stdin.readline
N=int(input().strip())
T=input().strip()
A=[ord(c)-97 for c in T]
if len(set(A))==N:
  x=1
  for i in range(2,N+1):
    x=x*i%MOD
  print(x)
  sys.exit(0)
Nx=[[-1]*26 for _ in range(N+1)]
last=[-1]*26
for pos in range(N-1,-1,-1):
  last[A[pos]]=pos
  row=Nx[pos]
  for c in range(26):
    row[c]=last[c]
P=[[-1]*26 for _ in range(N+1)]
prev=[-1]*26
for pos in range(N+1):
  row=P[pos]
  for c in range(26):
    row[c]=prev[c]
  if pos<N:
    prev[A[pos]]=pos
pref=[0]*(N+1)
for i in range(N):
  pref[i+1]=pref[i]|(1<<A[i])
def mask_between(l,r):
  return pref[r]&~pref[l]
cur={():1}
for _ in range(N):
  nxt=defaultdict(int)
  for s,cnt in cur.items():
    k=len(s)
    L=[-1]*(k+1)
    x=-1
    for i in range(k):
      x=Nx[x+1][s[i]]
      L[i+1]=x
    R=[N]*(k+1)
    x=N
    for i in range(k-1,-1,-1):
      x=P[x][s[i]]
      R[i]=x
    seen=set()
    for r in range(k+1):
      lb=L[r]
      rb=R[r]
      if rb-lb<=1: 
        continue
      m=mask_between(lb+1,rb)
      while m>=0:
        b=m&-m
        m-=b
        ch=(b.bit_length()-1)
        s2=s[:r]+(ch,)+s[r:]
        if s2 in seen: 
          continue
        seen.add(s2)
        nxt[s2]=(nxt[s2]+cnt)%MOD
  cur=nxt
print(cur.get(tuple(A),0)%MOD)

Submission Info

Judge Result