結果

問題 No.1702 count good string
コンテスト
ユーザー norioc
提出日時 2025-10-21 09:05:57
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 491 ms / 2,000 ms
コード長 3,147 bytes
コンパイル時間 348 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 81,308 KB
最終ジャッジ日時 2025-10-21 09:06:14
合計ジャッジ時間 15,945 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections.abc import Iterable
from enum import IntEnum, auto
from functools import cache


class E(IntEnum):
    S = 0
    Y0 = auto()
    Y_Q = auto()
    U0 = auto()
    U_Q = auto()
    U1 = auto()
    K0 = auto()
    K_Q = auto()
    K1 = auto()
    I0 = auto()
    I_Q = auto()
    I1 = auto()
    C0 = auto()
    C_Q = auto()
    C1 = auto()
    O0 = auto()
    O_Q = auto()
    O1 = auto()
    D0 = auto()
    D_Q = auto()
    D1 = auto()
    E0 = auto()
    E_Q = auto()
    E1 = auto()
    R0 = auto()
    R_Q = auto()
    R1 = auto()

    def nexts(self):
        match self:
            case E.S:   return [E.Y0, E.Y_Q]
            case E.Y0:  return [E.U0, E.U_Q]
            case E.Y_Q: return [E.U1]
            case E.U0:  return [E.K0, E.K_Q]
            case E.U_Q: return [E.K1]
            case E.U1:  return [E.K1]
            case E.K0:  return [E.I0, E.I_Q]
            case E.K_Q: return [E.I1]
            case E.K1:  return [E.I1]
            case E.I0:  return [E.C0, E.C_Q]
            case E.I_Q: return [E.C1]
            case E.I1:  return [E.C1]
            case E.C0:  return [E.O0, E.O_Q]
            case E.C_Q: return [E.O1]
            case E.C1:  return [E.O1]
            case E.O0:  return [E.D0, E.D_Q]
            case E.O_Q: return [E.D1]
            case E.O1:  return [E.D1]
            case E.D0:  return [E.E0, E.E_Q]
            case E.D_Q: return [E.E1]
            case E.D1:  return [E.E1]
            case E.E0:  return [E.R0, E.R_Q]
            case E.E_Q: return [E.R1]
            case E.E1:  return [E.R1]
            case E.R0:  return []
            case E.R_Q: return []
            case E.R1:  return []

        assert False

    @staticmethod
    @cache
    def states():
        res = []
        for fm in E:
            for to in fm.nexts():
                res.append((fm, to))

        return res


def state_dp(xs: Iterable, op, e, init: dict, *, is_reset=True):
    dp = [e] * len(E)
    for k, v in init.items():
        dp[k] = v

    for x in xs:
        pp = [e] * len(E) if is_reset else dp.copy()
        dp, pp = pp, dp
        for fm, to in E.states():
            if not is_valid(to, pp[fm], x): continue
            dp[to] = op(to, dp[to], fm, pp[fm], x)

    return dp


def is_valid(to: E, fm_v, v) -> bool:
    match to:
        case E.Y_Q | E.U_Q | E.K_Q | E.I_Q | E.C_Q | E.O_Q | E.D_Q | E.E_Q | E.R_Q:
            return v == '?'
        case E.Y0:
            return v == 'y'
        case E.U0 | E.U1:
            return v == 'u'
        case E.K0 | E.K1:
            return v == 'k'
        case E.I0 | E.I1:
            return v == 'i'
        case E.C0 | E.C1:
            return v == 'c'
        case E.O0 | E.O1:
            return v == 'o'
        case E.D0 | E.D1:
            return v == 'd'
        case E.E0 | E.E1:
            return v == 'e'
        case E.R0 | E.R1:
            return v == 'r'

    return True


def op(to: E, to_v, fm: E, fm_v, v):
    return (to_v + fm_v) % MOD


MOD = 10**9 + 7
N = int(input())
S = input()

dp = state_dp(S, op, 0, {E.S: 1}, is_reset=False)
ans = sum(dp[x] for x in [E.R0, E.R1, E.R_Q]) % MOD
print(ans)
0