結果
問題 | No.1702 count good string |
ユーザー |
![]() |
提出日時 | 2021-10-17 20:04:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 427 ms / 2,000 ms |
コード長 | 596 bytes |
コンパイル時間 | 149 ms |
コンパイル使用メモリ | 82,132 KB |
実行使用メモリ | 200,184 KB |
最終ジャッジ日時 | 2024-09-17 19:45:21 |
合計ジャッジ時間 | 10,692 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 47 |
ソースコード
import sysinput = sys.stdin.readlinedef f(T):dp = [[0]*N for _ in range(len(T))]for i in range(N):if S[i]==T[0]:dp[0][i] = 1for i in range(1, len(T)):acc = [0]for j in range(N):acc.append((acc[-1]+dp[i-1][j])%MOD)for j in range(N):if S[j]==T[i]:dp[i][j] = acc[j]return sum(dp[-1])%MODN = int(input())S = input()[:-1]MOD = 10**9+7T = 'yukicoder'ans = f(T)for i in range(len(T)):ans += f(T[:i]+'?'+T[i+1:])ans %= MODprint(ans)