結果

問題 No.2019 Digits Filling for All Substrings
コンテスト
ユーザー LyricalMaestro
提出日時 2025-05-04 14:08:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 152 ms / 2,000 ms
コード長 942 bytes
コンパイル時間 362 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 76,736 KB
最終ジャッジ日時 2025-05-04 14:08:47
合計ジャッジ時間 5,175 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2019

MOD = 998244353      


def main():
    N = int(input())
    S = input()

    answer = 0
    dp = [0] * 3
    for s in S:
        new_dp = [0] * 3
        for x in range(3):
            y = (x * 10) % 3
            if s == "?":
                for z in range(10):
                    yz = (y + z) % 3
                    new_dp[yz] += dp[x]
                    new_dp[yz] %= MOD
            else:
                yz = (y + int(s)) % 3
                new_dp[yz] += dp[x]
                new_dp[yz] %= MOD
        
        if s == "?":
            for z in range(10):
                new_dp[z % 3] += 1
                new_dp[z % 3] %= MOD
        else:
            new_dp[int(s) % 3] += 1
            new_dp[int(s) % 3] %= MOD
        
        dp = new_dp

        answer += dp[0]
        answer %= MOD
    print(answer)






        

        

        







if __name__ == "__main__":
    main()
0