結果

問題 No.1879 How many matchings?
コンテスト
ユーザー qwewe
提出日時 2025-05-14 13:19:12
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 5,276 bytes
コンパイル時間 176 ms
コンパイル使用メモリ 82,592 KB
実行使用メモリ 62,444 KB
最終ジャッジ日時 2025-05-14 13:19:53
合計ジャッジ時間 1,645 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

# Set the modulo value as required by the problem
MOD = 10**9 + 7

# Matrix multiplication function for 6x6 matrices
def mat_mul(A, B):
    """
    Performs matrix multiplication for two 6x6 matrices A and B modulo MOD.
    Returns the resulting 6x6 matrix C = A * B.
    """
    # Initialize the result matrix C with zeros
    C = [[0] * 6 for _ in range(6)]
    # Perform matrix multiplication
    for i in range(6):
        for j in range(6):
            # Use a temporary variable for the sum to avoid repeated modulo operations inside the inner loop
            sum_val = 0 
            for k in range(6):
                sum_val = (sum_val + A[i][k] * B[k][j]) % MOD
            C[i][j] = sum_val
    return C

# Matrix exponentiation function (A^p) for 6x6 matrix
def mat_pow(A, p):
    """
    Computes A^p for a 6x6 matrix A and non-negative integer p using binary exponentiation (exponentiation by squaring) modulo MOD.
    Returns the resulting 6x6 matrix.
    """
    # Initialize the result matrix as the 6x6 Identity matrix
    res = [[0] * 6 for _ in range(6)]
    for i in range(6):
        res[i][i] = 1
    
    # Use standard binary exponentiation algorithm
    base = A
    while p > 0:
        # If p is odd, multiply the result by the current base
        if p % 2 == 1:
            res = mat_mul(res, base)
        # Square the base for the next iteration
        base = mat_mul(base, base)
        # Integer division of p by 2
        p //= 2
    return res

# Matrix-vector multiplication function (6x6 matrix * 6x1 vector)
def mat_vec_mul(A, V):
    """
    Performs matrix-vector multiplication for a 6x6 matrix A and a 6x1 vector V modulo MOD.
    Returns the resulting 6x1 vector.
    """
    # Initialize the result vector with zeros
    res = [0] * 6
    for i in range(6):
        # Use a temporary variable for the sum
        sum_val = 0
        for j in range(6):
            sum_val = (sum_val + A[i][j] * V[j]) % MOD
        res[i] = sum_val
    return res

def solve():
    """
    Solves the problem: finds the number of maximum matchings in the graph G for a given N.
    Reads N from standard input and prints the result modulo 10^9 + 7.
    """
    # Read the input N
    N = int(sys.stdin.readline())

    # Handle base cases explicitly for N=1 to N=6
    if N == 1:
        print(1)
        return
    if N == 2:
        print(1)
        return
    if N == 3:
        print(3)
        return
    if N == 4:
        print(2)
        return
    if N == 5:
        print(7)
        return
    if N == 6:
        print(3)
        return

    # For N >= 7, we use matrix exponentiation based on derived linear recurrences.
    # The state vector contains the last 6 values of the sequence N_k:
    # V_k = [N_k, N_{k-1}, N_{k-2}, N_{k-3}, N_{k-4}, N_{k-5}]^T
    # The initial state vector V_6 is based on the known values N1..N6:
    V6 = [3, 7, 2, 3, 1, 1] # This corresponds to [N6, N5, N4, N3, N2, N1]^T

    # Define the transition matrices M_odd and M_even based on the recurrences:
    # For odd N >= 3: N_N = N_{N-1} + N_{N-2} + N_{N-3} + N_{N-4}
    M_odd = [[1, 1, 1, 1, 0, 0],
             [1, 0, 0, 0, 0, 0],
             [0, 1, 0, 0, 0, 0],
             [0, 0, 1, 0, 0, 0],
             [0, 0, 0, 1, 0, 0],
             [0, 0, 0, 0, 1, 0]]

    # For even N >= 4: N_N = N_{N-2} + N_{N-4}
    # This translates to V_N[1] = V_{N-1}[2] + V_{N-1}[4] in terms of the previous state vector
    M_even = [[0, 1, 0, 1, 0, 0], 
              [1, 0, 0, 0, 0, 0],
              [0, 1, 0, 0, 0, 0],
              [0, 0, 1, 0, 0, 0],
              [0, 0, 0, 1, 0, 0],
              [0, 0, 0, 0, 1, 0]]

    # Precompute the matrix M_pair = M_even * M_odd.
    # This matrix transforms the state vector V_{k-1} to V_{k+1} when k is odd.
    # It essentially advances the state by two steps, from an odd index k-1 to the next odd index k+1.
    M_pair = mat_mul(M_even, M_odd)
    
    # Compute the final result based on the parity of N
    if N % 2 == 0: # N is even
        # We need to compute V_N. Starting from V_6, we need to apply (N-6)/2 pairs of transitions (even then odd).
        # V_N = M_pair^((N-6)/2) * V_6
        power = (N - 6) // 2
        # Calculate M_pair raised to the required power
        M_total = mat_pow(M_pair, power)
        # Apply the resulting matrix to the initial vector V6
        Vn = mat_vec_mul(M_total, V6)
        # The answer is the first component of the final state vector Vn, which is N_N
        print(Vn[0])
    else: # N is odd
        # We need to compute V_N. Starting from V_6, we first apply (N-7)/2 pairs of transitions to reach V_{N-1}.
        # Then apply M_odd once to get V_N.
        # V_N = M_odd * M_pair^((N-7)/2) * V_6
        power = (N - 7) // 2
        # Calculate M_pair raised to the required power
        M_total_intermediate = mat_pow(M_pair, power)
        # Apply this matrix to V6 to get the state V_{N-1}
        V_intermediate = mat_vec_mul(M_total_intermediate, V6) 
        # Apply M_odd to V_{N-1} to get the final state V_N
        Vn = mat_vec_mul(M_odd, V_intermediate) 
        # The answer is the first component of the final state vector Vn, which is N_N
        print(Vn[0])

# Call the solve function to execute the program logic
solve()
0