結果

問題 No.1706 Many Bus Stops (hard)
ユーザー qwewe
提出日時 2025-05-14 13:23:10
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 45 ms / 2,000 ms
コード長 2,537 bytes
コンパイル時間 154 ms
コンパイル使用メモリ 82,236 KB
実行使用メモリ 61,956 KB
最終ジャッジ日時 2025-05-14 13:25:20
合計ジャッジ時間 3,447 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

def mat_mul(A, B, mod):
    C = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
    for i in range(4):
        for j in range(4):
            sum_val = 0
            for k_loop in range(4): # Renamed k to k_loop to avoid conflict if debugging outer scope k
                sum_val = (sum_val + A[i][k_loop] * B[k_loop][j]) % mod
            C[i][j] = sum_val
    return C

def mat_pow(A, n, mod):
    # Identity matrix
    res = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
    for i in range(4):
        res[i][i] = 1
    
    base = A
    while n > 0:
        if n % 2 == 1:
            res = mat_mul(res, base, mod)
        base = mat_mul(base, base, mod)
        n //= 2
    return res

def power(base, exp, mod):
    res = 1
    base %= mod
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp //= 2
    return res

def inv(n, mod):
    return power(n, mod - 2, mod)

def solve():
    C_val, N_val, M_val = map(int, input().split())
    MOD = 10**9 + 7

    invC = inv(C_val, MOD)
    
    # Matrix T definition
    # V_k = (p_k, s_k, p_{k-1}, s_{k-1})^T
    # V_{k+1} = T V_k
    T_matrix = [[0]*4 for _ in range(4)]
    
    # Constraints: C >= 2. So C-1 >= 1 and C-2 >= 0.
    # No need for (C-1+MOD)%MOD type of expressions.
    
    T_matrix[0][0] = invC
    T_matrix[0][3] = ((C_val - 1) * invC) % MOD
    
    T_matrix[1][1] = invC
    T_matrix[1][2] = invC
    T_matrix[1][3] = ((C_val - 2) * invC) % MOD # if C_val=2, this term is 0.
    
    T_matrix[2][0] = 1
    T_matrix[3][1] = 1

    # We need V_N = T^(N-1) V_1
    # p_N is the first component of V_N.
    # V_1 = (p_1, s_1, p_0, s_0)^T = (invC, 0, 1, 0)^T
    # p_N = (T_pow[0][0]*p_1 + T_pow[0][1]*s_1 + T_pow[0][2]*p_0 + T_pow[0][3]*s_0) % MOD
    # p_N = ((T_pow[0][0] * invC) % MOD + T_pow[0][2]) % MOD
        
    # N_val >= 1. So N_val-1 >= 0.
    # mat_pow(T, 0, MOD) correctly returns Identity matrix for N_val=1.
    T_pow_N_minus_1 = mat_pow(T_matrix, N_val - 1, MOD)
    
    term_p1_contribution = (T_pow_N_minus_1[0][0] * invC) % MOD
    term_p0_contribution = T_pow_N_minus_1[0][2] # This is T_pow[0][2] * p_0 where p_0=1
    
    p_N = (term_p1_contribution + term_p0_contribution) % MOD

    # Final probability calculation
    prob_not_at_stop1_single_bus = (1 - p_N + MOD) % MOD
    prob_all_buses_not_at_stop1 = power(prob_not_at_stop1_single_bus, M_val, MOD)
    
    ans = (1 - prob_all_buses_not_at_stop1 + MOD) % MOD
    
    print(ans)

solve()
0