結果

問題 No.3098 Linear Reversi
コンテスト
ユーザー tassei903
提出日時 2025-04-06 18:07:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 175 ms / 4,000 ms
コード長 2,604 bytes
コンパイル時間 450 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 78,796 KB
最終ジャッジ日時 2025-04-06 18:07:09
合計ジャッジ時間 4,730 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################

def f(now, i, t):
    nxt = list(now)
    L = -1
    for j in range(i-1, -1, -1):
        if now[j] == -1:
            break
        if now[j] == t:
            L = j
            break
    if L != -1:
        for j in range(L+1, i):
            nxt[j] = t
    R = -1
    for j in range(i+1, len(now)):
        if now[j] == -1:
            break
        if now[j] == t:
            R = j
            break
    if R != -1:
        for j in range(i+1, R):
            nxt[j] = t
    nxt[i] = t
    
    return tuple(nxt)
def g(now):
    r = 0
    for i in range(n):
        r |= now[i] << i
    return r
def h(x, n):
    res = []
    for i in range(n):
        res.append(x % 2)
        x //= 2
    return res

def check(a):
    for i in range(len(a)-3):
        if a[i:i+4] == [0, 1, 0, 1] or a[i:i+4] == [1, 0, 1, 0]:
            return False
    for i in range(len(a)-5):
        if a[i:i+6] == [0, 1, 0, 0, 1, 0] or a[i:i+6] == [1, 0, 1, 1, 0, 1]:
            return False
    for i in range(len(a) - 7):
        if a[i:i+8] == [0, 1, 0, 0, 1, 1, 0, 1] or a[i:i+8] == [1, 0, 1, 1, 0, 0, 1, 0]:
            return False
    return True

ans = set()
from functools import lru_cache
@lru_cache(maxsize=None)
def saiki(now):
    if all(x != -1 for x in now):
        ans.add(g(now))
    
    for i in range(len(now)):
        if now[i] == -1:
            nxt = f(now, i, 0)
            saiki(nxt)
            nxt = f(now, i, 1)
            saiki(nxt)

# for n in range(1, 12):
#     ans.clear()
#     saiki(tuple([-1] * n))
#     print(n, len(ans), 2 ** n - len(ans))
#     b = [0] * (1 << n)
#     for i in ans:
#         b[i] = 1
#         assert check(h(i, n))
    
#     for i in range(1 << n):
#         if b[i] == 0 and check(h(i, n)):
#             print(h(i, n))
#             # assert not check(h(i, n))

mod = 998244353
n = ni()
s = input()
a = [1, 1, 4, 5, 1, 4, 7, 7]
b = [2, 3, 2, 2, 6, 7, 3, 7]

dp = [0] * 8
dp[0] = 1

for i in range(n):
    ndp = [0] * 8
    if s[i] == "o" or s[i] == "?":
        for j in range(8):
            ndp[a[j]] += dp[j]
            ndp[a[j]] %= mod
    if s[i] == "x" or s[i] == "?":
        for j in range(8):
            ndp[b[j]] += dp[j]
            ndp[b[j]] %= mod
    dp = ndp

print(sum(dp[:7]) % mod)
0