Submission #6332188

Source Code Expand

import sys
input = sys.stdin.readline
import numpy as np

N,X,Y,Z = map(int,input().split())

MOD = 10 ** 9 + 7

# ダメなやつを数える
L = max(10,X + Y + Z)
dp = np.zeros(1 << L+1, dtype = np.int64) # 右から見て部分和として踏む場所
rng = np.arange(1 << L+1, dtype=np.int64)
x575 = (1 << Z) + (1 << (Y+Z)) + (1 << (X+Y+Z))
bad = ((x575 & rng) == x575)
dp[1] = 1

for n in range(N):
    prev = dp
    dp = np.zeros_like(prev)
    for i in range(1, 11):
        dp[1::1<<i] += prev.reshape(1<<i, 1<<(L+1-i)).sum(axis = 0)
    dp[bad] = 0
    dp %= MOD

answer = pow(10,N,MOD) - dp.sum()
answer %= MOD
print(answer)

Submission Info

Submission Time
Task E - Iroha and Haiku
User maspy
Language Python (3.4.3)
Score 700
Code Size 660 Byte
Status AC
Exec Time 442 ms
Memory 19900 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 4
AC × 35
Set Name Test Cases
Sample subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt
All subtask0_sample_01.txt, subtask0_sample_02.txt, subtask0_sample_03.txt, subtask0_sample_04.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask1_17.txt, subtask1_18.txt, subtask1_19.txt, subtask1_20.txt, subtask1_21.txt, subtask1_22.txt, subtask1_23.txt, subtask1_24.txt, subtask1_25.txt, subtask1_max1.txt, subtask1_max2.txt, subtask1_max3.txt, subtask1_min1.txt, subtask1_min2.txt, subtask1_min3.txt
Case Name Status Exec Time Memory
subtask0_sample_01.txt AC 175 ms 19804 KiB
subtask0_sample_02.txt AC 182 ms 19900 KiB
subtask0_sample_03.txt AC 157 ms 12240 KiB
subtask0_sample_04.txt AC 442 ms 19900 KiB
subtask1_01.txt AC 159 ms 12500 KiB
subtask1_02.txt AC 165 ms 12612 KiB
subtask1_03.txt AC 154 ms 12500 KiB
subtask1_04.txt AC 156 ms 12868 KiB
subtask1_05.txt AC 155 ms 12500 KiB
subtask1_06.txt AC 151 ms 12496 KiB
subtask1_07.txt AC 155 ms 12404 KiB
subtask1_08.txt AC 152 ms 12496 KiB
subtask1_09.txt AC 152 ms 12496 KiB
subtask1_10.txt AC 151 ms 12244 KiB
subtask1_11.txt AC 151 ms 12244 KiB
subtask1_12.txt AC 175 ms 14268 KiB
subtask1_13.txt AC 160 ms 12868 KiB
subtask1_14.txt AC 152 ms 12496 KiB
subtask1_15.txt AC 173 ms 12900 KiB
subtask1_16.txt AC 263 ms 16188 KiB
subtask1_17.txt AC 185 ms 13112 KiB
subtask1_18.txt AC 224 ms 14140 KiB
subtask1_19.txt AC 191 ms 13372 KiB
subtask1_20.txt AC 165 ms 12484 KiB
subtask1_21.txt AC 219 ms 14140 KiB
subtask1_22.txt AC 191 ms 13368 KiB
subtask1_23.txt AC 186 ms 13276 KiB
subtask1_24.txt AC 171 ms 12868 KiB
subtask1_25.txt AC 190 ms 13112 KiB
subtask1_max1.txt AC 437 ms 19896 KiB
subtask1_max2.txt AC 421 ms 19804 KiB
subtask1_max3.txt AC 294 ms 16188 KiB
subtask1_min1.txt AC 148 ms 12404 KiB
subtask1_min2.txt AC 148 ms 12500 KiB
subtask1_min3.txt AC 174 ms 19900 KiB