結果
問題 | No.1740 Alone 'a' |
ユーザー | MasKoaTS |
提出日時 | 2021-11-13 12:55:35 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 607 ms / 2,000 ms |
コード長 | 1,696 bytes |
コンパイル時間 | 260 ms |
コンパイル使用メモリ | 87,336 KB |
実行使用メモリ | 175,456 KB |
最終ジャッジ日時 | 2023-08-18 04:34:50 |
合計ジャッジ時間 | 18,401 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 234 ms
83,200 KB |
testcase_01 | AC | 226 ms
83,236 KB |
testcase_02 | AC | 230 ms
83,316 KB |
testcase_03 | AC | 607 ms
175,408 KB |
testcase_04 | AC | 576 ms
175,456 KB |
testcase_05 | AC | 273 ms
87,276 KB |
testcase_06 | AC | 274 ms
87,136 KB |
testcase_07 | AC | 245 ms
84,424 KB |
testcase_08 | AC | 226 ms
83,360 KB |
testcase_09 | AC | 230 ms
83,388 KB |
testcase_10 | AC | 229 ms
83,436 KB |
testcase_11 | AC | 315 ms
97,220 KB |
testcase_12 | AC | 508 ms
154,152 KB |
testcase_13 | AC | 499 ms
149,548 KB |
testcase_14 | AC | 577 ms
173,576 KB |
testcase_15 | AC | 263 ms
85,400 KB |
testcase_16 | AC | 481 ms
144,404 KB |
testcase_17 | AC | 257 ms
85,108 KB |
testcase_18 | AC | 301 ms
93,684 KB |
testcase_19 | AC | 515 ms
154,256 KB |
testcase_20 | AC | 391 ms
117,708 KB |
testcase_21 | AC | 433 ms
128,784 KB |
testcase_22 | AC | 479 ms
141,436 KB |
testcase_23 | AC | 476 ms
141,124 KB |
testcase_24 | AC | 395 ms
117,456 KB |
testcase_25 | AC | 394 ms
117,328 KB |
testcase_26 | AC | 433 ms
128,444 KB |
testcase_27 | AC | 446 ms
134,140 KB |
testcase_28 | AC | 415 ms
122,692 KB |
testcase_29 | AC | 580 ms
174,308 KB |
testcase_30 | AC | 450 ms
132,528 KB |
testcase_31 | AC | 491 ms
144,164 KB |
testcase_32 | AC | 419 ms
123,808 KB |
testcase_33 | AC | 480 ms
142,604 KB |
testcase_34 | AC | 312 ms
96,740 KB |
testcase_35 | AC | 417 ms
122,292 KB |
testcase_36 | AC | 383 ms
114,360 KB |
testcase_37 | AC | 310 ms
96,728 KB |
testcase_38 | AC | 364 ms
109,600 KB |
testcase_39 | AC | 278 ms
87,748 KB |
testcase_40 | AC | 331 ms
100,104 KB |
ソースコード
import itertools as iter import collections as coll import heapq as hq import bisect as bis from decimal import Decimal as dec from copy import deepcopy as dcopy import math import sys sys.setrecursionlimit(10**6) def input(): return sys.stdin.readline().rstrip() def getN(): return int(sys.stdin.readline()) def getNs(): return map(int,sys.stdin.readline().split()) def getList(): return list(map(int,sys.stdin.readline().split())) def strinps(n): return [sys.stdin.readline().rstrip() for _ in range(n)] pi = 3.141592653589793 mod = 10**9+7 MOD = 998244353 INF = math.inf dx = [1,0,-1,0]; dy = [0,1,0,-1] def ctoi(char): return ord(char)-ord('a') """ Main Code """ n = getN() s = input() l = [ctoi(c) for c in s] dp = [[0]*4 for _ in [0]*n] ndp = dcopy(dp) dp[0][0b00] = max(0,l[0]-1) dp[0][0b01] = int(l[0] != 0) dp[0][0b10] = int(l[0] != 0) dp[0][0b11] = int(l[0] == 0) #print(dp) for i in range(1,n): # 0 を 1 つも含まず、S より小さい dp[i][0b00] += dp[i-1][0b00] * 25; dp[i][0b00] %= MOD dp[i][0b00] += dp[i-1][0b10] * max(0,l[i]-1); dp[i][0b00] %= MOD # 0 を 1 つだけ含み、S より小さい dp[i][0b01] += dp[i-1][0b00]; dp[i][0b01] %= MOD dp[i][0b01] += dp[i-1][0b01] * 25; dp[i][0b01] %= MOD dp[i][0b01] += dp[i-1][0b10] * (l[i] != 0); dp[i][0b01] %= MOD dp[i][0b01] += dp[i-1][0b11] * max(0,l[i]-1); dp[i][0b01] %= MOD # 0 を 1 つも含まず、S と等しい dp[i][0b10] += dp[i-1][0b10] * (l[i] != 0); dp[i][0b10] %= MOD # 0 を 1 つだけ含み、S と等しい dp[i][0b11] += dp[i-1][0b10] * (l[i] == 0); dp[i][0b11] %= MOD dp[i][0b11] += dp[i-1][0b11] * (l[i] != 0); dp[i][0b10] %= MOD #print(dp) print(dp[n-1][0b01])