답안 #83833

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83833 2018-11-11T10:24:07 Z XBXJLeiLeLeiLe Mate (COCI18_mate) PyPy
80 / 100
567 ms 132096 KB
s = raw_input().split()[0]
q = input()


length = len(s)+1
arr1 = [[] for i in range(length)]
arr1[0].append(1)


def get_num(row, column):
    num = 0
    if column >= 0:
        num = arr1[row][column]
    return num


for j in range(1, length):
    for i in range(j):
        arr1[j].append(get_num(j - 1, i - 1) + get_num(j - 1, i))
    arr1[j].append(1)


def combination(n, d):
    k = d - 2
    return arr1[n][k]


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




# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 15248 KB Output is correct
2 Correct 100 ms 15248 KB Output is correct
3 Correct 101 ms 15248 KB Output is correct
4 Correct 113 ms 15676 KB Output is correct
5 Correct 523 ms 31888 KB Output is correct
6 Correct 567 ms 33820 KB Output is correct
7 Correct 458 ms 33820 KB Output is correct
8 Correct 460 ms 33820 KB Output is correct
9 Runtime error 367 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 350 ms 132096 KB Execution killed with signal 9 (could be triggered by violating memory limits)