結果
問題 | No.1702 count good string |
ユーザー |
![]() |
提出日時 | 2021-10-31 18:04:15 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 404 ms / 2,000 ms |
コード長 | 1,203 bytes |
コンパイル時間 | 451 ms |
コンパイル使用メモリ | 82,072 KB |
実行使用メモリ | 159,284 KB |
最終ジャッジ日時 | 2024-10-09 05:45:34 |
合計ジャッジ時間 | 14,073 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 |
ソースコード
import itertools as iterimport collections as collimport heapq as hqimport bisect as bisfrom decimal import Decimal as decfrom copy import deepcopy as dcopyimport mathimport syssys.setrecursionlimit(10**6)def input():return sys.stdin.readline().rstrip()def getN():return int(sys.stdin.readline().rstrip())def getNs():return map(int,sys.stdin.readline().rstrip().split())def getList():return list(map(int,sys.stdin.readline().rstrip().split()))def strinps(n):return [sys.stdin.readline().rstrip() for _ in range(n)]pi = 3.141592653589793mod = 10**9+7MOD = 998244353INF = math.infdx = [1,0,-1,0]; dy = [0,1,0,-1]"""Main Code"""n = getN()s = input()words = ["yukicoder","?ukicoder","y?kicoder","yu?icoder","yuk?coder","yuki?oder","yukic?der","yukico?er","yukicod?r","yukicode?"]def calc_dp(w):dp = [[0]*n for _ in range(9)]if(s[0] == w[0]):dp[0][0] = 1for i in range(1,n):if(s[i] == w[0]):dp[0][i] = (dp[0][i-1] + 1) % modelse:dp[0][i] = dp[0][i-1]for j in range(1,9):if(s[i] == w[j]):dp[j][i] = (dp[j][i-1] + dp[j-1][i-1]) % modelse:dp[j][i] = dp[j][i-1]return dp[8][n-1]print(sum(calc_dp(w) for w in words) % mod)