結果

問題 No.823 Many Shifts Easy
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:46:38
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 140 ms / 2,000 ms
コード長 1,204 bytes
コンパイル時間 564 ms
コンパイル使用メモリ 82,172 KB
実行使用メモリ 60,712 KB
最終ジャッジ日時 2025-06-12 21:53:35
合計ジャッジ時間 3,410 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read
    data = input().strip().split()
    N = int(data[0])
    K = int(data[1])
    
    if K == 0:
        print(0)
        return
    
    max_n = max(N, K)
    fact = [1] * (max_n + 1)
    for i in range(1, max_n + 1):
        fact[i] = fact[i-1] * i % MOD
    
    inv_fact = [1] * (max_n + 1)
    inv_fact[max_n] = pow(fact[max_n], MOD - 2, MOD)
    for i in range(max_n - 1, -1, -1):
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
    
    if N-1 < K:
        P = 0
    else:
        P = fact[N-1] * inv_fact[N-1 - K] % MOD
    
    inv2 = 500000004
    inv4 = 250000002
    
    part1 = P * N % MOD
    part1 = part1 * (N + 1) % MOD
    part1 = part1 * inv2 % MOD
    
    term2 = 0
    if K >= 2:
        if (N-2) < 0 or (K-2) < 0 or (N-2) < (K-2):
            C = 0
        else:
            C = fact[N-2] * inv_fact[K-2] % MOD
            C = C * inv_fact[N-2 - (K-2)] % MOD
        C = C * fact[K] % MOD
        
        term = C * (N-1) % MOD
        term = term * N % MOD
        term = term * inv4 % MOD
        term2 = term
    
    total = (part1 + term2) % MOD
    print(total)

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