Submission #13759276


Source Code Expand

Copy
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 KB

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