Submission #13759276

Source Code Expand

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

N, M = map(int, read().split())

def make_power(a, L, MOD=MOD):
    B = L.bit_length()
    x = np.empty(1 << B, np.int64)
    x[0] = 1
    for n in range(B):
        x[1 << n:1 << (n + 1)] = x[:1 << n] * a % MOD
        a *= a
        a %= MOD
    x = x[:L]
    x.flags.writeable = False
    return x

pow2 = make_power(2, M + 10)
ipow2 = make_power((1 + MOD) // 2, M + 10)

def update(dp):
    B = dp.copy()
    C = dp * np.arange(M + 1) % MOD * ipow2[:M + 1] % MOD
    dp[1:] = np.cumsum(C[:-1]) % MOD
    dp[1:] *= pow2[:M]
    dp %= MOD
    dp += np.arange(1, M + 2) * B
    dp %= MOD

dp = pow2[:M + 1].copy()
for _ in range(N - 1):
    update(dp)

print(dp[-1])

Submission Info

Submission Time
Task F - Sorting Game
User maspy
Language Python (3.8.2)
Score 1000
Code Size 860 Byte
Status AC
Exec Time 1478 ms
Memory 27556 KiB

Judge Result

Set Name All Sample
Score / Max Score 1000 / 1000 0 / 0
Status
AC × 57
AC × 2
Set Name Test Cases
All sample_01.txt, sample_02.txt, testcase_1.txt, testcase_10.txt, testcase_11.txt, testcase_12.txt, testcase_13.txt, testcase_14.txt, testcase_15.txt, testcase_16.txt, testcase_17.txt, testcase_18.txt, testcase_19.txt, testcase_2.txt, testcase_20.txt, testcase_21.txt, testcase_22.txt, testcase_23.txt, testcase_24.txt, testcase_25.txt, testcase_26.txt, testcase_27.txt, testcase_28.txt, testcase_29.txt, testcase_3.txt, testcase_30.txt, testcase_31.txt, testcase_32.txt, testcase_33.txt, testcase_34.txt, testcase_35.txt, testcase_36.txt, testcase_37.txt, testcase_38.txt, testcase_39.txt, testcase_4.txt, testcase_40.txt, testcase_41.txt, testcase_42.txt, testcase_43.txt, testcase_44.txt, testcase_45.txt, testcase_46.txt, testcase_47.txt, testcase_48.txt, testcase_49.txt, testcase_5.txt, testcase_50.txt, testcase_51.txt, testcase_52.txt, testcase_53.txt, testcase_54.txt, testcase_55.txt, testcase_6.txt, testcase_7.txt, testcase_8.txt, testcase_9.txt
Sample sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
sample_01.txt AC 102 ms 26932 KiB
sample_02.txt AC 188 ms 26976 KiB
testcase_1.txt AC 102 ms 27016 KiB
testcase_10.txt AC 105 ms 27044 KiB
testcase_11.txt AC 98 ms 27004 KiB
testcase_12.txt AC 100 ms 26940 KiB
testcase_13.txt AC 104 ms 27308 KiB
testcase_14.txt AC 99 ms 27240 KiB
testcase_15.txt AC 106 ms 27044 KiB
testcase_16.txt AC 175 ms 27232 KiB
testcase_17.txt AC 177 ms 26736 KiB
testcase_18.txt AC 833 ms 27100 KiB
testcase_19.txt AC 1478 ms 27268 KiB
testcase_2.txt AC 100 ms 26704 KiB
testcase_20.txt AC 1475 ms 27340 KiB
testcase_21.txt AC 172 ms 27156 KiB
testcase_22.txt AC 170 ms 27004 KiB
testcase_23.txt AC 831 ms 27248 KiB
testcase_24.txt AC 1471 ms 27268 KiB
testcase_25.txt AC 1477 ms 27252 KiB
testcase_26.txt AC 153 ms 27320 KiB
testcase_27.txt AC 172 ms 27036 KiB
testcase_28.txt AC 265 ms 27100 KiB
testcase_29.txt AC 703 ms 27440 KiB
testcase_3.txt AC 99 ms 27104 KiB
testcase_30.txt AC 729 ms 27128 KiB
testcase_31.txt AC 671 ms 27152 KiB
testcase_32.txt AC 1177 ms 27300 KiB
testcase_33.txt AC 392 ms 27076 KiB
testcase_34.txt AC 582 ms 27248 KiB
testcase_35.txt AC 184 ms 27088 KiB
testcase_36.txt AC 513 ms 26824 KiB
testcase_37.txt AC 408 ms 27152 KiB
testcase_38.txt AC 503 ms 27100 KiB
testcase_39.txt AC 881 ms 27452 KiB
testcase_4.txt AC 101 ms 27104 KiB
testcase_40.txt AC 190 ms 26976 KiB
testcase_41.txt AC 548 ms 26884 KiB
testcase_42.txt AC 707 ms 27084 KiB
testcase_43.txt AC 445 ms 27128 KiB
testcase_44.txt AC 640 ms 27120 KiB
testcase_45.txt AC 237 ms 27036 KiB
testcase_46.txt AC 423 ms 27188 KiB
testcase_47.txt AC 372 ms 26936 KiB
testcase_48.txt AC 1044 ms 27076 KiB
testcase_49.txt AC 348 ms 27144 KiB
testcase_5.txt AC 102 ms 27208 KiB
testcase_50.txt AC 205 ms 27084 KiB
testcase_51.txt AC 1045 ms 27244 KiB
testcase_52.txt AC 199 ms 27156 KiB
testcase_53.txt AC 1104 ms 26956 KiB
testcase_54.txt AC 742 ms 27096 KiB
testcase_55.txt AC 1251 ms 27008 KiB
testcase_6.txt AC 102 ms 26920 KiB
testcase_7.txt AC 102 ms 26680 KiB
testcase_8.txt AC 100 ms 27420 KiB
testcase_9.txt AC 100 ms 27556 KiB