結果

問題 No.42 貯金箱の溜息
ユーザー mkawa2mkawa2
提出日時 2023-03-17 01:28:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,559 ms / 5,000 ms
コード長 16,672 bytes
コンパイル時間 316 ms
コンパイル使用メモリ 81,860 KB
実行使用メモリ 80,460 KB
最終ジャッジ日時 2023-10-18 13:22:52
合計ジャッジ時間 6,272 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 449 ms
77,948 KB
testcase_01 AC 2,559 ms
80,460 KB
testcase_02 AC 2,029 ms
80,220 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# sys.setrecursionlimit(200005)
int1 = lambda x: int(x)-1
pDB = lambda *x: print(*x, end="\n", file=sys.stderr)
p2D = lambda x: print(*x, sep="\n", end="\n\n", file=sys.stderr)
def II(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI1(rows_number): return [LI1() for _ in range(rows_number)]
def SI(): return sys.stdin.readline().rstrip()

dij = [(0, 1), (-1, 0), (0, -1), (1, 0)]
# dij = [(0, 1), (-1, 0), (0, -1), (1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
inf = (1 << 63)-1
# inf = (1 << 31)-1
# md = 10**9+7
# md = 998244353

def dot(aa, bb):
    h = len(aa)
    w = len(bb[0])
    res = [[0]*w for _ in range(h)]
    for i, row in enumerate(aa):
        for j, col in enumerate(zip(*bb)):
            v = 0
            # for a, b in zip(row, col): v += a*b
            # res[i][j] = v
            for a, b in zip(row, col): v += a*b%md
            res[i][j] = v%md
    return res

def matpow(mat, e):
    n = len(mat)
    while e:
        if e & 1: res = dot(res, mat)
        mat = dot(mat, mat)
        e >>= 1
    return res

cn = 6
coin = [1, 5, 10, 50, 100, 500]
md = 10**9+9
cc = [[[1, 100, 2500, 7585, 8975, 1], [0, 1, 50, 235, 375, 1], [0, 0, 1, 10, 25, 1], [0, 0, 0, 1, 5, 1],
       [0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 1]],
      [[1, 200, 10000, 63670, 155875, 19162], [0, 1, 100, 970, 3175, 662], [0, 0, 1, 20, 100, 37], [0, 0, 0, 1, 10, 7],
       [0, 0, 0, 0, 1, 2], [0, 0, 0, 0, 0, 1]],
      [[1, 400, 40000, 521340, 2583450, 1298164], [0, 1, 200, 3940, 26050, 18164], [0, 0, 1, 40, 400, 414],
       [0, 0, 0, 1, 20, 34], [0, 0, 0, 0, 1, 4], [0, 0, 0, 0, 0, 1]],
      [[1, 800, 160000, 4218680, 42013700, 54481288], [0, 1, 400, 15880, 210900, 357288], [0, 0, 1, 80, 1600, 3788],
       [0, 0, 0, 1, 40, 148], [0, 0, 0, 0, 1, 8], [0, 0, 0, 0, 0, 1]],
      [[1, 1600, 640000, 33941360, 677494600, 961347207], [0, 1, 800, 63760, 1697000, 6267216],
       [0, 0, 1, 160, 6400, 32216], [0, 0, 0, 1, 80, 616], [0, 0, 0, 0, 1, 16], [0, 0, 0, 0, 0, 1]],
      [[1, 3200, 2560000, 272298720, 881497910, 316270798], [0, 1, 1600, 255520, 13614800, 104735392],
       [0, 0, 1, 320, 25600, 265392], [0, 0, 0, 1, 160, 2512], [0, 0, 0, 0, 1, 32], [0, 0, 0, 0, 0, 1]],
      [[1, 6400, 10240000, 181461422, 434149634, 411618213], [0, 1, 3200, 1023040, 109072800, 711637815],
       [0, 0, 1, 640, 102400, 2153824], [0, 0, 0, 1, 320, 10144], [0, 0, 0, 0, 1, 64], [0, 0, 0, 0, 0, 1]],
      [[1, 12800, 40960000, 463978727, 577858063, 992997468], [0, 1, 6400, 4094080, 873198400, 673889165],
       [0, 0, 1, 1280, 409600, 17353408], [0, 0, 0, 1, 640, 40768], [0, 0, 0, 0, 1, 128], [0, 0, 0, 0, 0, 1]],
      [[1, 25600, 163840000, 760980509, 257367138, 802915628], [0, 1, 12800, 16380160, 988047946, 86434651],
       [0, 0, 1, 2560, 1638400, 139318656], [0, 0, 0, 1, 1280, 163456], [0, 0, 0, 0, 1, 256], [0, 0, 0, 0, 0, 1]],
      [[1, 51200, 655360000, 284449458, 50551060, 441429573], [0, 1, 25600, 65528320, 914220305, 827330821],
       [0, 0, 1, 5120, 6553600, 116515063], [0, 0, 0, 1, 2560, 654592], [0, 0, 0, 0, 1, 512], [0, 0, 0, 0, 0, 1]],
      [[1, 102400, 621439982, 62022517, 628248073, 441037147], [0, 1, 51200, 262128640, 353096777, 834698928],
       [0, 0, 1, 10240, 26214400, 939984312], [0, 0, 0, 1, 5120, 2619904], [0, 0, 0, 0, 1, 1024], [0, 0, 0, 0, 0, 1]],
      [[1, 204800, 485759910, 641897869, 38944418, 88737047], [0, 1, 102400, 48545271, 982086198, 303105286],
       [0, 0, 1, 20480, 104857600, 551330689], [0, 0, 0, 1, 10240, 10482688], [0, 0, 0, 0, 1, 2048],
       [0, 0, 0, 0, 0, 1]],
      [[1, 409600, 943039631, 718074319, 243943898, 384236994], [0, 1, 204800, 194242524, 485886312, 105959947],
       [0, 0, 1, 40960, 419430400, 536472548], [0, 0, 0, 1, 20480, 41936896], [0, 0, 0, 0, 1, 4096],
       [0, 0, 0, 0, 0, 1]],
      [[1, 819200, 772158497, 76201088, 767739617, 76037306], [0, 1, 409600, 777092976, 403775242, 433529658],
       [0, 0, 1, 81920, 677721591, 795092732], [0, 0, 0, 1, 40960, 167759872], [0, 0, 0, 0, 1, 8192],
       [0, 0, 0, 0, 0, 1]],
      [[1, 1638400, 88633961, 936116975, 788517466, 12992491], [0, 1, 819200, 108617637, 296736219, 586482097],
       [0, 0, 1, 163840, 710886346, 373999512], [0, 0, 0, 1, 81920, 671064064], [0, 0, 0, 0, 1, 16384],
       [0, 0, 0, 0, 0, 1]],
      [[1, 3276800, 354535844, 795132652, 995489250, 186530233], [0, 1, 1638400, 434962068, 639617374, 547897743],
       [0, 0, 1, 327680, 843545366, 45043293], [0, 0, 0, 1, 163840, 684305390], [0, 0, 0, 0, 1, 32768],
       [0, 0, 0, 0, 0, 1]],
      [[1, 6553600, 418143367, 586176493, 311265124, 260756546], [0, 1, 3276800, 740831303, 179030298, 907429651],
       [0, 0, 1, 655360, 374181437, 572568008], [0, 0, 0, 1, 327680, 737319846], [0, 0, 0, 0, 1, 65536],
       [0, 0, 0, 0, 0, 1]],
      [[1, 13107200, 672573459, 590528583, 412365963, 704414570], [0, 1, 6553600, 965291274, 678969379, 899964890],
       [0, 0, 1, 1310720, 496725739, 429496211], [0, 0, 0, 1, 655360, 949475974], [0, 0, 0, 0, 1, 131072],
       [0, 0, 0, 0, 0, 1]],
      [[1, 26214400, 690293818, 330006048, 444538329, 872273523], [0, 1, 13107200, 865097229, 415386194, 342813090],
       [0, 0, 1, 2621440, 986902947, 831909474], [0, 0, 0, 1, 1310720, 798297085], [0, 0, 0, 0, 1, 262144],
       [0, 0, 0, 0, 0, 1]],
      [[1, 52428800, 761175254, 65779495, 307214677, 834090243], [0, 1, 26214400, 468253209, 251060753, 379399016],
       [0, 0, 1, 5242880, 947611761, 239297116], [0, 0, 0, 1, 2621440, 193974745], [0, 0, 0, 0, 1, 524288],
       [0, 0, 0, 0, 0, 1]],
      [[1, 104857600, 44700989, 234403374, 881546045, 653805538], [0, 1, 52428800, 888741467, 707263727, 152638406],
       [0, 0, 1, 10485760, 790447017, 250986728], [0, 0, 0, 1, 5242880, 777471844], [0, 0, 0, 0, 1, 1048576],
       [0, 0, 0, 0, 0, 1]],
      [[1, 209715200, 178803956, 718382408, 920322022, 751834866], [0, 1, 104857600, 586423121, 427006228, 883952995],
       [0, 0, 1, 20971520, 161788041, 355381645], [0, 0, 0, 1, 10485760, 113033077], [0, 0, 0, 0, 1, 2097152],
       [0, 0, 0, 0, 0, 1]],
      [[1, 419430400, 715215824, 140652439, 495612504, 875994662], [0, 1, 209715200, 408607026, 439206834, 962287406],
       [0, 0, 1, 41943040, 647152164, 235101632], [0, 0, 0, 1, 20971520, 458423764], [0, 0, 0, 0, 1, 4194304],
       [0, 0, 0, 0, 0, 1]],
      [[1, 838860800, 860863278, 741535450, 874580320, 85430619], [0, 1, 419430400, 760257215, 501425193, 390065105],
       [0, 0, 1, 83886080, 588608638, 453201329], [0, 0, 0, 1, 41943040, 846277959], [0, 0, 0, 0, 1, 8388608],
       [0, 0, 0, 0, 0, 1]],
      [[1, 677721591, 443453085, 481433396, 271900708, 331155984], [0, 1, 838860800, 292687073, 752768509, 554623020],
       [0, 0, 1, 167772160, 354434534, 923552359], [0, 0, 0, 1, 83886080, 410277633], [0, 0, 0, 0, 1, 16777216],
       [0, 0, 0, 0, 0, 1]],
      [[1, 355443173, 773812331, 215838674, 652791288, 118577910], [0, 1, 677721591, 674064763, 568185604, 48504746],
       [0, 0, 1, 335544320, 417738127, 596963032], [0, 0, 0, 1, 167772160, 691442171], [0, 0, 0, 0, 1, 33554432],
       [0, 0, 0, 0, 0, 1]],
      [[1, 710886346, 95249297, 519739853, 541441029, 740513852], [0, 1, 355443173, 702891985, 890774331, 240900721],
       [0, 0, 1, 671088640, 670952499, 643435535], [0, 0, 0, 1, 335544320, 866431962], [0, 0, 0, 0, 1, 67108864],
       [0, 0, 0, 0, 0, 1]],
      [[1, 421772683, 380997188, 1129308, 916109448, 625864000], [0, 1, 710886346, 824833824, 829631134, 657123296],
       [0, 0, 1, 342177271, 683809978, 685518368], [0, 0, 0, 1, 671088640, 667054413], [0, 0, 0, 0, 1, 134217728],
       [0, 0, 0, 0, 0, 1]],
      [[1, 843545366, 523988743, 724053824, 133104792, 34292760], [0, 1, 421772683, 325867073, 95352014, 892085810],
       [0, 0, 1, 684354542, 735239894, 770501141], [0, 0, 0, 1, 342177271, 70870809], [0, 0, 0, 0, 1, 268435456],
       [0, 0, 0, 0, 0, 1]],
      [[1, 687090723, 95954954, 336862493, 807610866, 134188701], [0, 1, 843545366, 356531891, 885141777, 363883460],
       [0, 0, 1, 368709075, 940959558, 577861489], [0, 0, 0, 1, 684354542, 88789595], [0, 0, 0, 0, 1, 536870912],
       [0, 0, 0, 0, 0, 1]],
      [[1, 374181437, 383819816, 241336794, 988437805, 56915077], [0, 1, 687090723, 532254771, 148664130, 288501551],
       [0, 0, 1, 737418150, 763838205, 815172430], [0, 0, 0, 1, 368709075, 965771107], [0, 0, 0, 0, 1, 73741815],
       [0, 0, 0, 0, 0, 1]],
      [[1, 748362874, 535279255, 853859974, 206626301, 49969895], [0, 1, 374181437, 341273498, 615887582, 275799416],
       [0, 0, 1, 474836291, 55352793, 364243408], [0, 0, 0, 1, 737418150, 84309837], [0, 0, 0, 0, 1, 147483630],
       [0, 0, 0, 0, 0, 1]],
      [[1, 496725739, 141117002, 998378553, 443324670, 397344343], [0, 1, 748362874, 789602847, 946308092, 325806093],
       [0, 0, 1, 949672582, 221411172, 432886964], [0, 0, 0, 1, 474836291, 779690238], [0, 0, 0, 0, 1, 294967260],
       [0, 0, 0, 0, 0, 1]],
      [[1, 993451478, 564468008, 606696185, 351141143, 289301923], [0, 1, 496725739, 7429080, 273113124, 895173706],
       [0, 0, 1, 899345155, 885644688, 833821835], [0, 0, 0, 1, 949672582, 3662696], [0, 0, 0, 0, 1, 589934520],
       [0, 0, 0, 0, 0, 1]],
      [[1, 986902947, 257872014, 231585895, 604271682, 314218887], [0, 1, 993451478, 727751767, 247135922, 971357140],
       [0, 0, 1, 798690301, 542578725, 743413728], [0, 0, 0, 1, 899345155, 784454335], [0, 0, 0, 0, 1, 179869031],
       [0, 0, 0, 0, 0, 1]],
      [[1, 973805885, 31488047, 163443265, 814980199, 151930361], [0, 1, 986902947, 307077926, 729285420, 847325544],
       [0, 0, 1, 597380593, 170314882, 418535209], [0, 0, 0, 1, 798690301, 677424406], [0, 0, 0, 0, 1, 359738062],
       [0, 0, 0, 0, 0, 1]],
      [[1, 947611761, 125952188, 147951178, 384372568, 778110213], [0, 1, 973805885, 20453456, 849624067, 181083137],
       [0, 0, 1, 194761177, 681259528, 592921445], [0, 0, 0, 1, 597380593, 788911783], [0, 0, 0, 0, 1, 719476124],
       [0, 0, 0, 0, 0, 1]],
      [[1, 895223513, 503808752, 739990869, 869005581, 479671001], [0, 1, 947611761, 666097355, 871452552, 26323190],
       [0, 0, 1, 389522354, 725038094, 441406830], [0, 0, 0, 1, 194761177, 314075459], [0, 0, 0, 0, 1, 438952239],
       [0, 0, 0, 0, 0, 1]],
      [[1, 790447017, 15234990, 534975050, 52636324, 313182305], [0, 1, 895223513, 832956455, 295654757, 849230308],
       [0, 0, 1, 779044708, 900152358, 762348085], [0, 0, 0, 1, 389522354, 573158535], [0, 0, 0, 0, 1, 877904478],
       [0, 0, 0, 0, 0, 1]],
      [[1, 580894025, 60939960, 519037653, 715474916, 925570718], [0, 1, 790447017, 668959899, 713763893, 284876588],
       [0, 0, 1, 558089407, 600609405, 901062983], [0, 0, 0, 1, 779044708, 926347538], [0, 0, 0, 0, 1, 755808947],
       [0, 0, 0, 0, 0, 1]],
      [[1, 161788041, 243759840, 667339742, 373920865, 499261667], [0, 1, 580894025, 350107781, 208990997, 602945022],
       [0, 0, 1, 116178805, 402437602, 173426140], [0, 0, 0, 1, 558089407, 972816948], [0, 0, 0, 0, 1, 511617885],
       [0, 0, 0, 0, 0, 1]],
      [[1, 323576082, 975039360, 515050894, 553814827, 454092134], [0, 1, 161788041, 748967530, 877000569, 629048606],
       [0, 0, 1, 232357610, 609750399, 758716352], [0, 0, 0, 1, 116178805, 426121402], [0, 0, 0, 0, 1, 23235761],
       [0, 0, 0, 0, 0, 1]],
      [[1, 647152164, 900157413, 58096729, 872921298, 930909342], [0, 1, 323576082, 692942923, 255400872, 916547831],
       [0, 0, 1, 464715220, 439001578, 578195478], [0, 0, 0, 1, 232357610, 774192882], [0, 0, 0, 0, 1, 46471522],
       [0, 0, 0, 0, 0, 1]],
      [[1, 294304319, 600629625, 680247504, 437208323, 358899780], [0, 1, 647152164, 165917316, 839004449, 476419016],
       [0, 0, 1, 929430440, 756006303, 705894156], [0, 0, 0, 1, 464715220, 236186067], [0, 0, 0, 0, 1, 92943044],
       [0, 0, 0, 0, 0, 1]],
      [[1, 588608638, 402518482, 233305097, 465555157, 56941059], [0, 1, 294304319, 451960557, 571649393, 130139336],
       [0, 0, 1, 858860871, 24025185, 61417710], [0, 0, 0, 1, 929430440, 223573391], [0, 0, 0, 0, 1, 185886088],
       [0, 0, 0, 0, 0, 1]],
      [[1, 177217267, 610073919, 890602078, 446386044, 220797016], [0, 1, 588608638, 384424805, 364498373, 246999862],
       [0, 0, 1, 717721733, 96100740, 334285814], [0, 0, 0, 1, 858860871, 451951819], [0, 0, 0, 0, 1, 371772176],
       [0, 0, 0, 0, 0, 1]],
      [[1, 354434534, 440295658, 939183538, 884723616, 273314408], [0, 1, 177217267, 690864392, 786895716, 788262795],
       [0, 0, 1, 435443457, 384402960, 417835206], [0, 0, 0, 1, 717721733, 923123786], [0, 0, 0, 0, 1, 743544352],
       [0, 0, 0, 0, 0, 1]],
      [[1, 708869068, 761182623, 206379570, 785245028, 135026301], [0, 1, 354434534, 69787903, 190192045, 568616347],
       [0, 0, 1, 870886914, 537611831, 60420821], [0, 0, 0, 1, 435443457, 923128155], [0, 0, 0, 0, 1, 487088695],
       [0, 0, 0, 0, 0, 1]],
      [[1, 417738127, 44730465, 293568781, 636862289, 659071298], [0, 1, 708869068, 891812336, 924424577, 202096166],
       [0, 0, 1, 741773819, 150447306, 841412072], [0, 0, 0, 1, 870886914, 153778660], [0, 0, 0, 0, 1, 974177390],
       [0, 0, 0, 0, 0, 1]],
      [[1, 835476254, 178921860, 660452978, 472621415, 572903035], [0, 1, 417738127, 792570756, 652514914, 654729182],
       [0, 0, 1, 483547629, 601789224, 137655901], [0, 0, 0, 1, 741773819, 537646783], [0, 0, 0, 0, 1, 948354771],
       [0, 0, 0, 0, 0, 1]],
      [[1, 670952499, 715687440, 14782382, 735448479, 716545262], [0, 1, 835476254, 620925875, 539723643, 745542711],
       [0, 0, 1, 967095258, 407156878, 675039504], [0, 0, 0, 1, 483547629, 995651409], [0, 0, 0, 0, 1, 896709533],
       [0, 0, 0, 0, 0, 1]],
      [[1, 341904989, 862749742, 9988726, 26349665, 704846535], [0, 1, 670952499, 384989229, 178468476, 791295352],
       [0, 0, 1, 934190507, 628627503, 592194713], [0, 0, 0, 1, 967095258, 672734181], [0, 0, 0, 0, 1, 793419057],
       [0, 0, 0, 0, 0, 1]],
      [[1, 683809978, 450998941, 581018995, 434493930, 365119877], [0, 1, 341904989, 342528401, 34989026, 580440092],
       [0, 0, 1, 868381005, 514509994, 298491611], [0, 0, 0, 1, 934190507, 71193850], [0, 0, 0, 0, 1, 586838105],
       [0, 0, 0, 0, 0, 1]],
      [[1, 367619947, 803995755, 520969650, 723120537, 970990844], [0, 1, 683809978, 975256592, 37924635, 128825823],
       [0, 0, 1, 736762001, 58039958, 218506756], [0, 0, 0, 1, 868381005, 45289697], [0, 0, 0, 0, 1, 173676201],
       [0, 0, 0, 0, 0, 1]],
      [[1, 735239894, 215982993, 395790069, 231759066, 404242366], [0, 1, 367619947, 111312317, 993541817, 549352253],
       [0, 0, 1, 473523993, 232159832, 244025784], [0, 0, 0, 1, 736762001, 702187391], [0, 0, 0, 0, 1, 347352402],
       [0, 0, 0, 0, 0, 1]],
      [[1, 470479779, 863931972, 551976129, 611135714, 130266216], [0, 1, 735239894, 865821238, 25103416, 345387479],
       [0, 0, 1, 947047986, 928639328, 283445654], [0, 0, 0, 1, 473523993, 850806743], [0, 0, 0, 0, 1, 694704804],
       [0, 0, 0, 0, 0, 1]],
      [[1, 940959558, 455727861, 905479380, 715462322, 90841619], [0, 1, 470479779, 304428856, 140283189, 845134937],
       [0, 0, 1, 894095963, 714557285, 287227600], [0, 0, 0, 1, 947047986, 487341339], [0, 0, 0, 0, 1, 389409599],
       [0, 0, 0, 0, 0, 1]],
      [[1, 881919107, 822911435, 96612449, 359149224, 301255903], [0, 1, 940959558, 900003286, 144849062, 106071202],
       [0, 0, 1, 788191917, 858229122, 765879925], [0, 0, 0, 1, 894095963, 117594126], [0, 0, 0, 0, 1, 778819198],
       [0, 0, 0, 0, 0, 1]],
      [[1, 763838205, 291645713, 972201397, 814026985, 433249387], [0, 1, 881919107, 964588850, 778646953, 579630653],
       [0, 0, 1, 576383825, 432916461, 778095098], [0, 0, 0, 1, 788191917, 806834080], [0, 0, 0, 0, 1, 557638387],
       [0, 0, 0, 0, 0, 1]],
      [[1, 527676401, 166582843, 151202140, 899884958, 496004153], [0, 1, 763838205, 587506830, 767633867, 341740049],
       [0, 0, 1, 152767641, 731665835, 386622098], [0, 0, 0, 1, 576383825, 900251445], [0, 0, 0, 0, 1, 115276765],
       [0, 0, 0, 0, 0, 1]]]

def solve():
    m = II()
    e, r = divmod(m, 500)
    dp = [1]+[0]*r
    aa = [0]*cn
    for ci, c in enumerate(coin):
        for i in range(r+1-c):
            dp[i+c] += dp[i]
            dp[i+c] %= md
        aa[ci] = dp[-1]
    for i in range(cn-1)[::-1]:
        aa[i+1] -= aa[i]
        aa[i+1] %= md

    mat = [[1 if i == j else 0 for j in range(cn)] for i in range(cn)]
    i = 0
    while e:
        if e & 1: mat = dot(mat, cc[i])
        e >>= 1
        i += 1
    aa = dot([aa], mat)
    print(sum(aa[0])%md)

for _ in range(II()):
    solve()
0