結果

問題 No.1561 connect x connect
ユーザー maspymaspy
提出日時 2021-04-11 13:32:42
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 3,851 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 82,792 KB
実行使用メモリ 111,360 KB
最終ジャッジ日時 2024-06-25 07:58:43
合計ジャッジ時間 12,220 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
61,760 KB
testcase_01 AC 119 ms
77,056 KB
testcase_02 AC 329 ms
80,980 KB
testcase_03 AC 39 ms
54,384 KB
testcase_04 AC 43 ms
59,408 KB
testcase_05 AC 59 ms
66,692 KB
testcase_06 AC 40 ms
53,428 KB
testcase_07 AC 41 ms
54,056 KB
testcase_08 AC 48 ms
60,116 KB
testcase_09 AC 46 ms
60,048 KB
testcase_10 AC 60 ms
67,424 KB
testcase_11 AC 121 ms
77,432 KB
testcase_12 AC 184 ms
77,880 KB
testcase_13 AC 303 ms
80,816 KB
testcase_14 AC 1,331 ms
110,976 KB
testcase_15 AC 1,349 ms
110,984 KB
testcase_16 AC 334 ms
80,812 KB
testcase_17 AC 124 ms
77,036 KB
testcase_18 AC 62 ms
68,000 KB
testcase_19 AC 1,430 ms
111,360 KB
testcase_20 AC 183 ms
77,880 KB
testcase_21 AC 45 ms
60,768 KB
testcase_22 AC 184 ms
77,976 KB
testcase_23 AC 47 ms
62,296 KB
testcase_24 AC 1,436 ms
110,976 KB
testcase_25 AC 49 ms
61,432 KB
testcase_26 TLE -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 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(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 not in ID:
                ID[w] = len(V)
                V.append(w)
            j = ID[w]
            G.append((i, j))
    return len(V), G


def conv(A, B):
    C = [0] * (len(A) + len(B) - 1)
    for i in range(len(A)):
        for j in range(len(B)):
            C[i + j] += A[i] * B[j]
            C[i + j] %= MOD
    return C

def coef_of_generating_function(P, Q, N):
    assert Q[0] == 1 and len(Q) == len(P) + 1

    while N:
        Q1 = Q.copy()
        for i in range(len(Q)):
            if i & 1:
                Q1[i] = -Q1[i]
        P = conv(P, Q1)[N & 1::2]
        Q = conv(Q, Q1)[::2]
        N >>= 1
    return P[0]

def find_generating_function(A):
    N = len(A)
    B = [1]
    C = [1]
    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 = pow(p, MOD - 2, MOD) * d % MOD
        if len(C) < len(B) + m:
            C += [0] * (len(B) + m - len(C))
        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 = conv(A, Q)[:len(Q) - 1]
    return P, Q

def solve_small(H):
    N, G = generate_graph(H)
    FRM, TO = map(list, zip(*G))
    MAX = N + N + 10
    ans = [0] * MAX
    dp = [0] * N
    dp[0] = 1
    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

H, W = map(int, input().split())
A = solve_small(H)
P, Q = find_generating_function(A)

print(coef_of_generating_function(P, Q, W))
0