結果

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

ソースコード

diff # 

MOD = 10**9 + 7

max_n = 10**5 + 10
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

def comb(n, k):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

def perm(a, b):
    if b > a:
        return 0
    return fact[a] * inv_fact[a - b] % MOD

def main():
    import sys
    input = sys.stdin.read
    data = input().strip().split()
    N = int(data[0])
    K = int(data[1])
    
    inv2 = (MOD + 1) // 2  # Modular inverse of 2
    
    if N == 0:
        print(0)
        return
    
    # Compute X for j < N
    if N >= 2:
        n = N - 2
        term1 = comb(n, K)
        term2 = comb(n, K-1)
        term3 = comb(n, K-2) * inv2 % MOD
        sum_terms = (term1 + term2 + term3) % MOD
        X = sum_terms * fact[K] % MOD
    else:
        X = 0
    
    # Compute Y for j = N
    Y = perm(N-1, K)  # Y = P(N-1, K)
    
    # Compute sum_j = (N-1)*N // 2 mod MOD
    sum_j = (N-1) * N % MOD
    sum_j = sum_j * inv2 % MOD
    
    # Compute total
    total = (X * sum_j % MOD + Y * N % MOD) % MOD
    
    print(total)

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