Submission #32513582

Source Code Expand

import numpy as np

mod = 1_000_000_007

def mat_mul(a, b):
    ret = np.zeros((a.shape[0], b.shape[1]), dtype=a.dtype)
    for i in range(a.shape[0]):
        for j in range(b.shape[1]):
            ret[i][j] = sum(a[i] * b[:, j] % mod)
            
    return ret % mod
            
    
def mat_pow(a, n):
    ret = np.eye(*a.shape, dtype=a.dtype)
    
    while n:
        if n & 1:
            ret = mat_mul(ret, a)
        a = mat_mul(a, a)
        n >>= 1

    return ret

def kaisetsu2(N, B, K, c):
    A = np.zeros((B, B), dtype=np.uint64)
    
    for i in range(B):
        for j in c:
            nex = (i*10 + j) % B
            A[i][nex] += 1
    
    return mat_pow(A, N)[0][0]

  
N, B, K, *c = map(int, open(0).read().split())
print(kaisetsu2(N, B, K, c))

Submission Info

Submission Time
Task 005 - Restricted Digits（★7）
User arakaki_tokyo
Language Python (3.8.2)
Score 4
Code Size 808 Byte
Status TLE
Exec Time 5514 ms
Memory 35148 KiB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 1 / 1 3 / 3 0 / 3
Status
AC × 4
TLE × 1
AC × 19
AC × 30
AC × 30
TLE × 11
Set Name Test Cases
Sample subtask01_01_sample_01.txt, subtask01_01_sample_02.txt, subtask01_01_sample_03.txt, subtask02_01_sample_04.txt, subtask03_01_sample_05.txt
Subtask1 subtask01_01_sample_01.txt, subtask01_01_sample_02.txt, subtask01_01_sample_03.txt, subtask01_02_hand_01.txt, subtask01_02_hand_02.txt, subtask01_02_hand_03.txt, subtask01_02_hand_04.txt, subtask01_02_hand_05.txt, subtask01_02_hand_06.txt, subtask01_02_hand_07.txt, subtask01_02_hand_08.txt, subtask01_03_random_01.txt, subtask01_03_random_02.txt, subtask01_03_random_03.txt, subtask01_03_random_04.txt, subtask01_03_random_05.txt, subtask01_03_random_06.txt, subtask01_03_random_07.txt, subtask01_04_max_07.txt
Subtask2 subtask01_01_sample_01.txt, subtask01_01_sample_02.txt, subtask01_01_sample_03.txt, subtask01_02_hand_01.txt, subtask01_02_hand_02.txt, subtask01_02_hand_03.txt, subtask01_02_hand_04.txt, subtask01_02_hand_05.txt, subtask01_02_hand_06.txt, subtask01_02_hand_07.txt, subtask01_02_hand_08.txt, subtask01_03_random_01.txt, subtask01_03_random_02.txt, subtask01_03_random_03.txt, subtask01_03_random_04.txt, subtask01_03_random_05.txt, subtask01_03_random_06.txt, subtask01_03_random_07.txt, subtask01_04_max_07.txt, subtask02_01_sample_04.txt, subtask02_05_random_01.txt, subtask02_05_random_02.txt, subtask02_05_random_03.txt, subtask02_05_random_04.txt, subtask02_05_random_05.txt, subtask02_05_random_06.txt, subtask02_05_random_07.txt, subtask02_06_max_07.txt, subtask02_07_slow_doubling_killer_01.txt, subtask02_07_slow_doubling_killer_02.txt
Subtask3 subtask01_01_sample_01.txt, subtask01_01_sample_02.txt, subtask01_01_sample_03.txt, subtask01_02_hand_01.txt, subtask01_02_hand_02.txt, subtask01_02_hand_03.txt, subtask01_02_hand_04.txt, subtask01_02_hand_05.txt, subtask01_02_hand_06.txt, subtask01_02_hand_07.txt, subtask01_02_hand_08.txt, subtask01_03_random_01.txt, subtask01_03_random_02.txt, subtask01_03_random_03.txt, subtask01_03_random_04.txt, subtask01_03_random_05.txt, subtask01_03_random_06.txt, subtask01_03_random_07.txt, subtask01_04_max_07.txt, subtask02_01_sample_04.txt, subtask02_05_random_01.txt, subtask02_05_random_02.txt, subtask02_05_random_03.txt, subtask02_05_random_04.txt, subtask02_05_random_05.txt, subtask02_05_random_06.txt, subtask02_05_random_07.txt, subtask02_06_max_07.txt, subtask02_07_slow_doubling_killer_01.txt, subtask02_07_slow_doubling_killer_02.txt, subtask03_01_sample_05.txt, subtask03_08_random_01.txt, subtask03_08_random_02.txt, subtask03_08_random_03.txt, subtask03_08_random_04.txt, subtask03_08_random_05.txt, subtask03_08_random_06.txt, subtask03_08_random_07.txt, subtask03_09_max_07.txt, subtask03_10_slow_doubling_killer_01.txt, subtask03_10_slow_doubling_killer_02.txt
Case Name Status Exec Time Memory
subtask01_01_sample_01.txt AC 111 ms 27164 KiB
subtask01_01_sample_02.txt AC 103 ms 27152 KiB
subtask01_01_sample_03.txt AC 251 ms 27176 KiB
subtask01_02_hand_01.txt AC 108 ms 26732 KiB
subtask01_02_hand_02.txt AC 106 ms 26688 KiB
subtask01_02_hand_03.txt AC 105 ms 26804 KiB
subtask01_02_hand_04.txt AC 116 ms 26968 KiB
subtask01_02_hand_05.txt AC 106 ms 27024 KiB
subtask01_02_hand_06.txt AC 107 ms 26808 KiB
subtask01_02_hand_07.txt AC 114 ms 26848 KiB
subtask01_02_hand_08.txt AC 103 ms 26956 KiB
subtask01_03_random_01.txt AC 136 ms 27028 KiB
subtask01_03_random_02.txt AC 145 ms 27032 KiB
subtask01_03_random_03.txt AC 219 ms 27044 KiB
subtask01_03_random_04.txt AC 245 ms 26856 KiB
subtask01_03_random_05.txt AC 261 ms 26948 KiB
subtask01_03_random_06.txt AC 279 ms 26824 KiB
subtask01_03_random_07.txt AC 283 ms 27212 KiB
subtask01_04_max_07.txt AC 308 ms 26996 KiB
subtask02_01_sample_04.txt AC 882 ms 27148 KiB
subtask02_05_random_01.txt AC 368 ms 27024 KiB
subtask02_05_random_02.txt AC 618 ms 26920 KiB
subtask02_05_random_03.txt AC 105 ms 26656 KiB
subtask02_05_random_04.txt AC 721 ms 26980 KiB
subtask02_05_random_05.txt AC 801 ms 26928 KiB
subtask02_05_random_06.txt AC 878 ms 26964 KiB
subtask02_05_random_07.txt AC 883 ms 27176 KiB
subtask02_06_max_07.txt AC 949 ms 27188 KiB
subtask02_07_slow_doubling_killer_01.txt AC 1174 ms 26980 KiB
subtask02_07_slow_doubling_killer_02.txt AC 1292 ms 26972 KiB
subtask03_01_sample_05.txt TLE 5514 ms 34892 KiB
subtask03_08_random_01.txt TLE 5514 ms 32204 KiB
subtask03_08_random_02.txt TLE 5514 ms 29852 KiB
subtask03_08_random_03.txt TLE 5514 ms 28528 KiB
subtask03_08_random_04.txt TLE 5514 ms 34296 KiB
subtask03_08_random_05.txt TLE 5514 ms 34388 KiB
subtask03_08_random_06.txt TLE 5514 ms 35132 KiB
subtask03_08_random_07.txt TLE 5514 ms 35072 KiB
subtask03_09_max_07.txt TLE 5514 ms 34996 KiB
subtask03_10_slow_doubling_killer_01.txt TLE 5514 ms 35148 KiB
subtask03_10_slow_doubling_killer_02.txt TLE 5514 ms 35088 KiB