Submission #71165267

Source Code Expand

from collections import defaultdict

def nCr(n, r):
    return ((fact[n] * inv[n-r] % MOD) * inv[r]) % MOD


S = list(input())
S_num = list(map(int, S))
N = len(S_num)
MOD = 998244353

fact = [1, 1]
inv = [1, 1]
for i in range(2, 2 * 10 ** 6+5):
    fact.append(fact[-1] * i % MOD)
    inv.append(pow(fact[-1], MOD-2, MOD))


left = defaultdict(int)
right = defaultdict(int)

for i in range(N):
    right[S_num[i]] += 1

ans = 0
for i in range(N):
    p = S_num[i]
    left[p] += 1
    right[p] -= 1

    if right[p+1] == 0:
        continue

    ans += nCr(left[p] + right[p+1] - 1, left[p])
    ans %= MOD

print(ans)

Submission Info

Submission Time
Task F - 1122 Subsequence 2
User kokonotsu
Language Python (PyPy 3.11-v7.3.20)
Score 500
Code Size 655 Byte
Status AC
Exec Time 1097 ms
Memory 513368 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 27
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 798 ms 384788 KiB
00_sample_01.txt AC 796 ms 384892 KiB
00_sample_02.txt AC 796 ms 385116 KiB
01_random_00.txt AC 795 ms 384792 KiB
01_random_01.txt AC 917 ms 513072 KiB
01_random_02.txt AC 1097 ms 513044 KiB
01_random_03.txt AC 925 ms 513044 KiB
01_random_04.txt AC 931 ms 513084 KiB
01_random_05.txt AC 925 ms 513308 KiB
01_random_06.txt AC 924 ms 513044 KiB
01_random_07.txt AC 926 ms 512736 KiB
01_random_08.txt AC 860 ms 442124 KiB
01_random_09.txt AC 927 ms 512948 KiB
01_random_10.txt AC 850 ms 433492 KiB
01_random_11.txt AC 928 ms 513056 KiB
01_random_12.txt AC 813 ms 390900 KiB
01_random_13.txt AC 936 ms 513084 KiB
01_random_14.txt AC 820 ms 396448 KiB
01_random_15.txt AC 933 ms 513036 KiB
01_random_16.txt AC 831 ms 413856 KiB
01_random_17.txt AC 927 ms 513104 KiB
01_random_18.txt AC 928 ms 513160 KiB
01_random_19.txt AC 914 ms 513052 KiB
01_random_20.txt AC 916 ms 513368 KiB
01_random_21.txt AC 916 ms 512768 KiB
01_random_22.txt AC 825 ms 396696 KiB
01_random_23.txt AC 823 ms 396504 KiB