#647082 (Python3) No.1561 connect x connect

• 問題: No.1561 connect x connect
• ユーザー: maspy
• 提出日時: 2021-04-11 12:59:27
• 言語: Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
• 結果: RE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 20,408 bytes
• コンパイル時間: 263 ms
• コンパイル使用メモリ: 13,312 KB
• 実行使用メモリ: 45,172 KB
• 最終ジャッジ日時: 2024-06-25 07:58:03
• 合計ジャッジ時間: 23,340 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	525 ms; 44,792 KB
testcase_01	AC	522 ms; 44,536 KB
testcase_02	AC	542 ms; 44,408 KB
testcase_03	AC	524 ms; 44,664 KB
testcase_04	AC	530 ms; 44,664 KB
testcase_05	AC	526 ms; 44,656 KB
testcase_06	AC	525 ms; 44,536 KB
testcase_07	AC	526 ms; 44,536 KB
testcase_08	AC	525 ms; 44,404 KB
testcase_09	AC	530 ms; 44,792 KB
testcase_10	AC	523 ms; 44,676 KB
testcase_11	AC	522 ms; 45,048 KB
testcase_12	AC	535 ms; 44,920 KB
testcase_13	AC	545 ms; 44,540 KB
testcase_14	AC	534 ms; 44,528 KB
testcase_15	AC	543 ms; 44,664 KB
testcase_16	AC	550 ms; 44,408 KB
testcase_17	AC	547 ms; 44,400 KB
testcase_18	AC	538 ms; 44,408 KB
testcase_19	AC	553 ms; 44,920 KB
testcase_20	AC	541 ms; 44,408 KB
testcase_21	AC	534 ms; 44,528 KB
testcase_22	AC	557 ms; 44,532 KB
testcase_23	AC	537 ms; 44,660 KB
testcase_24	AC	565 ms; 44,788 KB
testcase_25	AC	536 ms; 44,404 KB
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	RE	-
testcase_31	AC	527 ms; 44,660 KB
testcase_32	AC	527 ms; 45,044 KB
testcase_33	AC	542 ms; 44,792 KB
testcase_34	AC	553 ms; 45,012 KB
testcase_35	RE	-
testcase_36	RE	-
testcase_37	RE	-

ソースコード

import sys
import numpy as np

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

MOD = 1_000_000_007

def to(H, A):
    """
    empty col
    """
    if A == 'begin':
        yield 'begin'
    elif A == 'end':
        yield 'end'
    elif len(set(x for x in A if x >= 0)) == 1:
        yield 'end'

    if A == 'end':
        return
    _A = A
    for s in range(1, 1 << H):
        if _A == 'begin' or _A == 'end':
            A = [-1] * H
        else:
            A = list(_A)
        for i in range(H):
            if A[i] >= 0:
                A[i] += H
        for i in range(H):
            if s & 1 << i:
                A.append(i)
            else:
                A.append(-1)
        """
        横にマージ
        """
        for i in range(H):
            j = i + H
            if A[i] >= 0 and A[j] >= 0 and A[i] != A[j]:
                before = max(A[i], A[j])
                after = min(A[i], A[j])
                for k in range(H + H):
                    if A[k] == before:
                        A[k] = after
        """
        縦にマージ
        """
        for i in range(H, H + H - 1):
            j = i + 1
            if A[i] >= 0 and A[j] >= 0 and A[i] != A[j]:
                before = max(A[i], A[j])
                after = min(A[i], A[j])
                for k in range(H + H):
                    if A[k] == before:
                        A[k] = after
        if any(x >= H for x in A[:H]):
            # 孤立した連結成分が残ってしまった場合
            continue
        yield tuple(A[H:])

def generate_graph(H):
    V = ['begin', 'end']
    ID = {'begin': 0, 'end': 1}
    G = []
    for i, v in enumerate(V):
        for w in to(H, v):
            if w not in ID:
                ID[w] = len(V)
                V.append(w)
            j = ID[w]
            G.append((i, j))
    return len(V), G

# generate_graph(8)
# V = 836, E = 121246 が分かる
# 辺密度 1/6 程度なので、わりと dense

def flip(A):
    H = len(A)
    A = list(A[::-1])
    for i in range(H):
        if A[i] != -1:
            A[i] = H - 1 - A[i]
    for i in range(H):
        if A[i] > i:
            before = A[i]
            after = i
            for j in range(H):
                if A[j] == before:
                    A[j] = after
    return tuple(A)

def generate_graph_compress(H):
    """
    mirror reflection を同一視して、状態を圧縮する
    """
    V = ['begin', 'end']
    ID = {'begin': 0, 'end': 1}
    G = []
    for i, v in enumerate(V):
        for w in to(H, v):
            if w == 'begin' or w == 'end':
                pass
            else:
                w = min(w, flip(w))
            if w not in ID:
                ID[w] = len(V)
                V.append(w)
            j = ID[w]
            G.append((i, j))
    return len(V), G

"""
N = 436 に対して
(N,N) 行列の 10^18 乗あたりを求めることになる。厳しい。
線形漸化式を、前計算することにする。
"""

def find_generating_function(A):
    N = len(A)
    B = np.ones(1, np.int64)
    C = np.ones(1, np.int64)
    l, m, p = 0, 1, 1
    for i in range(N):
        d = A[i]
        for j in range(1, l + 1):
            d += C[j] * A[i - j]
            d %= MOD
        if d == 0:
            m += 1
            continue
        T = C.copy()
        q = mpow(p, MOD - 2) * d % MOD
        if len(C) < len(B) + m:
            C = np.concatenate((C, np.zeros(len(B) + m - len(C), np.int64)))
        for j in range(len(B)):
            C[j + m] -= q * B[j]
            C[j + m] %= MOD
        if l + l <= i:
            B = T
            l, m, p = i + 1 - l, 1, d
        else:
            m += 1
    Q = C
    P = fft_convolve(A[:len(Q)], Q)[:len(Q) - 1]
    return P, Q

def solve_small(H):
    N, G = generate_graph_compress(H)
    MAX = N + N + 10
    ans = [0] * MAX
    dp = [0] * N
    dp[0] = 1
    ans[0] = 0
    for i in range(MAX):
        newdp = [0] * N
        for a, b in G:
            newdp[b] += dp[a]
        dp = [x % MOD for x in newdp]
        ans[i] = dp[1]
    return ans

"""with open('memo.txt', 'w') as FILE:
    for H in range(1,9):
        A = np.array(solve_small(H), np.int64)
        P, Q = find_generating_function(A)
        print(H, file=FILE)
        print(*P, file=FILE)
        print(*Q, file=FILE)"""

txt = """1
0 1 0
1 1000000004 3 1000000006
2
0 3 1 0
1 1000000003 4 0 1000000006
3
0 6 999999993 14 1000000001 999999999 2 0
1 999999998 26 999999972 22 3 999999991 9 1000000006
4
0 10 999999945 190 999999791 999999791 450 999999881 999999815 999999983 999999897 38 2 0
1 999999990 90 999999777 272 75 999999384 632 999999942 999999752 198 999999845 96 999999996 1000000006
5
0 15 999999667 3841 999975377 89727 999843888 999933616 853474 998688719 999764725 1921386 169082 909226 990472660 4399320 16536564 989535207 923739 995900973 996974943 13301314 997485893 995412107 1954996 62879 999763340 89685 999984969 335 106 1000000004 0
1 999999966 626 999994795 26632 999916042 135637 57937 999199739 1620135 999093191 998485993 2551590 997377220 7154119 991457770 993019186 21987911 983996162 6152683 999036138 990231089 13699534 997404693 994521618 3355642 999776210 999597590 189183 999956725 4214 198 999999956 1
6
0 21 999998819 33693 999436429 5860073 962266040 133514102 929136360 431241967 654250836 839086547 445006449 590028056 825532221 685389183 704462583 427249983 541666783 926820421 764709524 582516343 909412365 900017668 785675119 180011121 496192818 209757910 674600534 76330199 452857958 668200755 169118335 388777677 904740474 887916382 671938205 879345481 832206907 566669394 702582218 457203893 148622722 829977850 269842066 287478868 575104063 840890499 102988330 691692129 537130174 803473826 274435539 754464000 914140557 505651188 329169310 35974660 877155902 299783640 139456757 527551741 76782422 936102085 7612545 2363009 164652 495 999999575 1000000004 0
1 999999918 3110 999939541 742664 993958208 31995434 906653130 979867988 450143629 57940041 51719115 329658325 705040706 38479371 724108123 810715054 484591080 77586872 13495283 20514139 279183132 513975810 178497912 771592522 295194475 776332021 223981658 58083192 17050708 16230911 494464705 476519393 189155785 937991413 54201070 63313885 20151946 118575609 776692687 610711296 884756831 128167752 845202278 735369307 206268113 525852836 826291169 922972595 693304349 776356265 548131137 141958987 152522485 798387263 987311741 558683120 404633960 238042460 920984885 675315088 341916115 676073373 221240708 211895609 29348012 576165 999444951 999942165 999998535 107 1
7
0 28 999995343 390302 979261277 765350670 389595025 297013369 530956970 440079916 457973561 899537123 825800282 703121040 654230148 502085672 892816515 640622006 583228763 804764150 703759762 938543462 185882577 402604156 171488342 7462404 141973244 310361697 495237514 866198903 712829335 496235025 522429112 354484819 804734437 192361128 910590072 172180831 424019738 97206678 64016054 414857175 382112898 166193241 622316133 94457460 393387894 266775036 907085865 882256066 34569154 869338941 35588897 568298331 466901464 150047457 870209299 851010037 256319672 77561341 856394015 812308257 830391254 358822957 479553206 577938473 920986090 578861286 89108042 180785680 548053826 926404015 751651737 655635405 649170381 366650300 470321403 772262409 949270786 179741227 789412451 612706225 918409853 186491917 687548020 572614072 334437580 393522144 542232669 33148162 440785714 656234828 695927320 534932291 919813629 656249689 108682588 845019557 31016981 739003736 73533070 746696925 327018783 178996830 58430801 731966165 782774329 789594531 66720678 995946423 296830922 101355418 355936134 253159216 687163430 557588716 788640596 743319856 742577239 646682538 107391328 608990040 5023871 258031351 246406033 562878343 247651901 689494357 474923474 950620096 857913174 475379552 883453689 633959790 384522779 8988799 369679392 560783897 861847106 812496660 659132944 16146166 994884039 925025591 670144907 293137433 44723512 964136526 184163424 156783034 97712113 348673282 267569258 948080352 358711970 636896269 539259823 560117745 766536909 369883765 965992377 680852959 84142292 493962194 964718724 50594957 629001208 480589591 838932136 568266480 40972662 772421316 893912167 326105433 540978462 993134663 999976667 1154 1000000003 0
1 999999781 22133 998708004 51265818 517360108 546845912 149828812 946233573 211651202 232405750 811285267 401128294 116600453 290384294 677300925 13623411 155729746 111188901 452410975 117842397 332838981 970845792 94569547 820027654 200913625 890068520 67908380 76368293 461783299 774230873 809781530 66759279 19585253 349823801 504256321 826122746 84252359 578059214 341123611 323641562 621647519 633413775 635711110 932952837 35095443 981566491 537648957 564758649 706798990 100000385 128921008 717726991 383849221 750895077 470510190 554514183 475290790 79252471 926030996 307209159 522079494 32775585 101415276 271705401 266458448 606062420 260120971 123407489 837735148 245028769 821505999 329034147 44511599 943629170 138511469 145790140 346792223 395988572 925480272 909141629 573883305 305237182 934272686 724968146 362587964 615079501 821387966 307899471 611914183 219979031 157062462 192214867 530161994 276049689 109370078 332843953 437308315 752536534 225262744 767746693 118820492 659915009 148956346 342326029 932826231 121257500 190435414 682932862 93801129 679311932 391327856 174721612 371261815 658110054 823002334 293616027 350408100 31341195 162686635 380434359 514468457 464117410 565005604 56215077 112578061 257377860 902941141 918227775 565229996 757086971 827775747 329062828 480907436 157361700 70022425 878622562 520826406 187978351 283088291 593161595 117585205 327508906 663456512 92016231 699721310 209521382 807714963 131675232 261081137 577438817 42318841 923821258 380930212 199917502 581730944 726241975 812221768 292515948 848519168 545507143 238738168 216060021 879877364 711496839 917027319 282174451 185267082 643028099 857050431 163144958 546075680 193151642 893859690 268322266 377828077 871297985 1077829 18317 999999639 1
8
0 36 999985327 3019112 597822563 186642870 370836457 670855183 122074887 834105310 160387753 624576679 503452864 181006113 23412787 587229898 89408622 57554267 671498086 384876386 683044289 745751734 400213235 202305814 732681805 729017292 851925366 725161022 49280101 196410500 288460709 562677227 617920014 165464079 913307512 353537630 142984468 350516448 525868392 930444685 636260122 363682682 174259463 797092860 934542827 907339773 443249574 261304515 139870434 702803811 756190456 790705234 44633988 182763636 318162316 530828477 543142737 564178085 781690467 880903860 156123065 462608527 331873943 895495296 593119596 8607887 602127688 901873005 663134217 358491959 585649591 262166323 454482774 333981707 962053752 496046996 643159739 29744351 405676926 109944118 828246237 355124372 845223518 225659698 308395011 180131589 241514521 962990744 195879716 666006140 617317456 633268143 989402509 69979257 586926761 150523639 857367260 723580184 401184227 873809768 198741621 114603094 546762471 961556424 98132256 451012436 814509913 328606913 238995752 571942562 27331717 146434911 384029139 181830050 540772710 973337193 44277340 349573637 703485948 174809332 236503422 832993472 321894472 788413021 229986514 954585720 281091454 428830909 78048473 512851571 639302590 146461291 816457140 354515017 153748653 262225533 47259993 132133552 621204934 585730606 399402828 239852680 245091000 836361166 876442997 738812393 867701700 799824340 250796343 678381006 584015081 73798975 54230031 505727905 985894064 778525897 881297691 611045144 626048351 906453788 896564341 590965593 684276913 346884013 804291808 722293273 741859051 597857591 268973892 369599157 467170669 517801398 666343629 385122665 518496167 862071595 176137330 465708789 674124053 647657685 105124490 279759849 876352078 852590618 152651842 905223524 17560606 178698282 957646212 106714187 154149933 362973314 800767349 251223752 369929024 64528446 24658765 425651539 833986977 239719351 857996503 623658574 990374822 392297408 457069880 730631483 480611396 612264597 225576642 54977849 667477418 851505643 216995723 515141242 387081483 332588962 855836121 746725559 808314323 354895712 676482253 583403977 621524609 420580003 427893585 211613467 588725722 174617018 229897644 236407451 382005598 902545173 414335157 367581778 989304253 414283685 355092066 939716976 216787303 690016408 927181463 501468935 28392513 806313981 414869401 727165057 73965114 238087273 633885624 586103017 871285538 867338734 885979453 574496812 553371296 51502126 471130479 518793425 131667170 830935447 969302137 959975133 272256930 352114620 27169699 178038326 192300426 577509535 516872930 488661868 864023570 357352798 411013417 310391367 272822673 394000569 312756867 553782931 805544865 448083394 811053951 85414277 580961437 649503866 496296854 949260200 382127126 980410064 274062103 433880664 749376817 269558635 863270269 392703006 507444549 341235042 179957819 175616345 887355771 754547778 6046773 35491390 651186185 951482399 673728551 858605803 370093520 238193481 39974574 454597472 406962812 882844627 965143879 184283439 179907122 393727606 354613939 23224130 414708319 776245792 84576130 196618530 618891432 363049153 672028682 871626104 804230586 963060235 640023702 915815418 590799280 546175292 436656799 381276245 290578128 318605244 579868087 268039778 533991413 64250946 294455984 606889661 685116497 867076232 67822206 985249818 342670934 78200978 851952695 25142160 833604476 897336623 311877935 415072607 277482359 189647611 240971465 414038744 644193362 30897680 97463063 731469545 994021441 905523609 128429207 612631685 68756021 738175680 542282020 695075060 10642957 228902358 471505375 964045744 274465755 390312142 717991618 752361876 463421871 351479678 718344578 701076920 894897784 836091984 485653840 866330329 429921925 977729334 841381548 251060088 396245001 582645135 812625177 363911800 615558109 456672835 969656038 223766883 634549138 458780506 479236862 430793826 280675210 532639366 188569065 943104545 211544802 595858789 204102674 934731032 855265433 646181647 305993505 689138617 530633605 208039749 723691211 115896542 37733797 48094676 492774605 235189807 352675893 854199481 155991107 549691504 505839639 481490492 151073549 949969439 114428523 63416758 999570253 999995747 1000000003 0
1 999999487 121621 982609880 728058965 987778989 174829068 53727628 7205002 429985264 238803947 725474573 741291920 842076511 80566125 630047723 243273237 704919909 467750756 898645900 284015712 120666140 525076163 502048647 41285713 236154320 944501774 488500488 710436225 929390983 946198532 360474668 349764997 546341165 947196857 642988951 368966218 168715782 469670802 231397888 68229010 683271338 664890364 139880593 745193967 857773494 996357368 296985699 387800445 999535757 347864702 663192692 941229752 652195017 974804757 617212988 303782980 637798607 506484052 240297013 25400671 836103437 265982407 689584959 996104694 900416203 918296796 522286080 187612087 362933090 864532307 302981624 112204968 54400905 784706585 26473224 668712640 375257376 41403686 733299902 290472213 417704505 968163964 206305019 642117922 452197323 528501014 758704660 723789950 861488883 186442869 911469844 189585922 385531334 883639965 340445857 803030761 906058405 283729103 556838458 207205455 236582603 332247614 512751191 978031986 933348343 439583198 259555183 667111524 134423267 627265370 1218547 652309453 774086416 819442729 303725740 362324759 808079315 666491770 170076746 67455926 981783870 962127145 308555979 63650406 671285897 392101680 496994999 356899672 113429770 530326097 799630760 988646538 838587591 155025630 192022364 334997493 224438207 150157191 926202557 508901327 384387352 201600983 922499010 934485700 211414346 320838066 944419484 970282204 759269994 379210257 366839751 849660169 369564163 397878810 842191624 914513850 81262954 512817858 699572773 73984848 652395150 274641274 19567651 313454866 517733797 732834732 683830859 851387499 41462608 755742719 327386893 146422653 280719585 245862381 75849368 400405900 623426624 323900502 995684701 649837950 712790652 689384867 712068630 251496879 603708479 652192881 830106386 434833194 562491712 7093190 794371622 230556813 346620116 863101446 583807218 349090587 349434449 580680839 164857387 858407370 420826464 111043596 706255236 828752073 486821786 945421669 334275891 7749670 469804619 531998487 577456543 437330438 192802364 339161210 79451038 697562910 762676651 378714174 136277270 612489667 226816771 18447731 814031151 302415632 895311508 826637650 480121030 72644533 104253907 526628766 785779519 212194261 162176985 229171858 660299181 405518105 475658895 271893670 153602347 227044504 493230361 220368386 2456839 278002827 509864003 579236359 144720094 69430502 353996002 902690656 738366048 18491633 902501522 549399509 522545766 557160850 294333309 944294748 733035016 521453600 654630136 355163957 83445555 446062789 602883516 58164724 907889336 968279122 486960845 6092978 488051217 239187866 500350824 446413026 364867970 293570497 437561632 546514652 353147020 184699732 342059370 90908034 203706709 419444183 495246668 590236228 529826205 783503620 543077435 389342496 300468224 737345482 593103076 962272241 268050333 700208604 630238783 377190644 663585254 531081907 562207598 560055481 462273498 340097385 577843235 438543318 542695407 240460506 85696197 852960749 708243855 357474416 35233189 886404820 783773695 580663937 979996091 54888582 153040947 805904119 560313486 116387497 794826272 896287073 767874291 430061171 754591084 641547207 599926992 982019810 84811201 545913874 673760737 565719119 887158365 542060632 884307697 809680891 644419759 749572988 894828730 645628517 789681045 397480957 690692127 925108787 631439798 221405719 420992738 823536228 850184166 686938582 561412994 694931701 590472721 857763370 547795108 908024031 163676569 93224809 952424240 603702399 777896391 615989257 387932407 947630136 596984018 844375184 408007263 527596252 126707118 904693720 637968858 181854776 988697472 216218687 884035973 801361388 871033102 799464827 419251246 860180888 670516234 13638879 174702108 43525788 380590669 150639864 155316288 473919774 213510789 852837503 258472507 369947189 718610519 657211677 950407319 309727757 488494822 113764870 952317721 323855947 982056241 119995213 903306923 573858592 335915859 665953195 729432528 421470818 444041677 440431099 828648704 521790123 730000703 609341909 439574410 852276450 76946971 58248143 435433334 803096862 777840536 960372939 89722122 328721511 305873657 57219747 566132089 355343950 589824792 224852426 977308292 38843 850 1"""

def fft_convolve(f, g):
    """
    数列 (多項式) f, g の畳み込みの計算．上下 15 bitずつ分けて計算することで，
    30 bit以下の整数，長さ 250000 程度の数列での計算が正確に行える．
    """
    Lf, Lg = f.shape[-1], g.shape[-1]
    L = Lf + Lg - 1
    fft_len = 1 << L.bit_length()
    fh, fl = f >> 15, f & (1 << 15) - 1
    gh, gl = g >> 15, g & (1 << 15) - 1

    def conv(f, g):
        Ff = np.fft.rfft(f, fft_len)
        Fg = np.fft.rfft(g, fft_len)
        h = np.fft.irfft(Ff * Fg)
        return np.rint(h)[..., :L].astype(np.int64) % MOD

    x = conv(fl, gl)
    z = conv(fh, gh)
    y = conv(fl + fh, gl + gh) - x - z
    return (x + (y << 15) + (z << 30)) % MOD


def coef_of_generating_function(P, Q, N):
    """compute the coefficient [x^N] P/Q of rational power series.

    Parameters
    ----------
    P : np.ndarray
        Numerator.
    Q : np.ndarray
        Denominator
        Q[0] == 1 and len(Q) == len(P) + 1 is assumed.
    N : int
        The coefficient to compute.
    """
    assert Q[0] == 1 and len(Q) == len(P) + 1

    def convolve(f, g):
        return fft_convolve(f, g)

    while N:
        Q1 = np.empty_like(Q)
        Q1[::2] = Q[::2]
        Q1[1::2] = MOD - Q[1::2]
        P = convolve(P, Q1)[N & 1::2]
        Q = convolve(Q, Q1)[::2]
        N >>= 1
    return P[0]

lines = txt.split('\n')
data = {}
for H in range(1, 9):
    P = lines[3*H-2]
    Q = lines[3*H-1]
    P = np.array(P.split(), np.int64)
    Q = np.array(Q.split(), np.int64)
    data[H] = (P, Q)

H, W = map(int, read().split())
P, Q = data[H]
ans = coef_of_generating_function(P, Q, W)
print(ans)