oj.uz

Submission #83816

# Submission time Handle Problem Language Result Execution time Memory
83816 2018-11-11T03:29:13 Z XBXJLeiLeLeiLe Mate (COCI18_mate) PyPy
40 / 100
 2000 ms 31560 KB 
s = raw_input().split()[0]
q = input()


def combination(n, d):
    k = d - 2
    if n - k < k:
        k = n - k
    result = 1
    for i in range(k):
        result *= n
        n -= 1
    w = k
    for i in range(w):
        result /= k
        k -= 1
    return result


def mod(num):
    return num % (10**9+7)


def lst_id(letter):
    return ord(letter) - ord("a")


arr = [[0 for i in range(26)] for i in range(len(s))]
arr_c = [0 for i in range(26)]
for i in range(len(s)-1, -1, -1):
    for j in range(26):
        arr[i][j] = arr_c[j]
    arr_c[lst_id(s[i])] += 1

arr_r = []
for i in range(q):
    d, xy = raw_input().split()
    total = 0
    d = int(d)
    x = xy[0]
    y = xy[1]
    for i in range(len(s)):
        if s[i] == x and i >= d - 2:
            total += combination(i, d) * arr[i][lst_id(y)]
    arr_r.append(mod(total))

for ans in arr_r:
    print ans

Subtask #1
40.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 21876 KB Output is correct
2 Correct 171 ms 21876 KB Output is correct
3 Correct 184 ms 21876 KB Output is correct
4 Correct 195 ms 22568 KB Output is correct
5 Execution timed out 2047 ms 27980 KB Time limit exceeded
6 Execution timed out 2045 ms 28712 KB Time limit exceeded
7 Execution timed out 2056 ms 29324 KB Time limit exceeded
8 Execution timed out 2041 ms 31560 KB Time limit exceeded
9 Execution timed out 2061 ms 31560 KB Time limit exceeded
10 Execution timed out 2057 ms 31560 KB Time limit exceeded