結果

問題 No.1561 connect x connect
コンテスト
ユーザー maspy
提出日時 2021-04-11 13:31:43
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,148 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,264 KB
実行使用メモリ 173,192 KB
最終ジャッジ日時 2024-06-25 07:57:37
合計ジャッジ時間 9,361 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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_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 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_compress(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