結果

問題 No.1706 Many Bus Stops (hard)
ユーザー LyricalMaestro
提出日時 2024-02-09 01:33:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,344 bytes
コンパイル時間 376 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 64,768 KB
最終ジャッジ日時 2024-09-28 12:56:10
合計ジャッジ時間 4,081 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1706

MOD = 10 ** 9 + 7

def main():
    C, N, M = map(int, input().split())

    # バス1台について「N時点でバス停1にいない」確率を求める
    # 0: バス停1にいる組み合わせ
    # 1: バス停x(x>=2)にいる組み合わせ
    # 2: バス停1に向かっている最中の組み合わせ
    # 3: バス停x(x>=2)に向かっている最中の組み合わせ
    dp = [0] * 4
    dp[0] = 1
    inv_c = pow(C, MOD - 2, MOD)
    inv_c1 = ((C - 1) * inv_c) % MOD
    inv_c2 = ((C - 2) * inv_c) % MOD

    for _ in range(N):
        next_dp = [0] * 4
        
        next_dp[0] += (dp[0] * inv_c) % MOD
        next_dp[0] %= MOD
        next_dp[3] += (dp[0] *inv_c1) % MOD
        next_dp[3] %= MOD

        next_dp[1] += (dp[1] * inv_c) % MOD
        next_dp[1] %= MOD
        next_dp[2] += (dp[1] * inv_c) % MOD
        next_dp[2] %= MOD
        next_dp[3] += (dp[1] * inv_c2) % MOD
        next_dp[3] %= MOD

        next_dp[0] += dp[2]
        next_dp[0] %= MOD
    
        next_dp[1] += dp[3]
        next_dp[1] %= MOD
        dp = next_dp

    ans = 0
    for i in range(1, 4):
        ans += dp[i]
        ans %= MOD

    # Mのバスの分だけかける
    ans = pow(ans, M, MOD)
    answer = (1 - ans) % MOD
    print(answer)


if __name__ == "__main__":
    main()
0