bouzuya.hatenablog.com

ぼうずやのにっき

リングフィットアドベンチャーの再開 / ABC151 A, B, C, D, E を解いた

昨日からリングフィットアドベンチャーを再開している。フィットボクシング 2 よりも負荷が高い。

頭が痛いので寝る。

ABC151 : AtCoder Beginner Contest 151

use modint::ModInt1000000007 as ModInt;
use proconio::input;

fn main() {
    input! {
        n: usize,
        k: usize,
        mut a: [i64; n],
    };

    let (fact, finv) = {
        let maxn = n;
        let mut fact = vec![ModInt::new(1); maxn + 1];
        for i in 1..=maxn {
            fact[i] = fact[i - 1] * ModInt::new(i);
        }
        let mut finv = vec![ModInt::new(1); maxn + 1];
        finv[maxn] = fact[maxn].inv();
        for i in (1..=maxn).rev() {
            finv[i - 1] = finv[i] * ModInt::new(i);
        }
        (fact, finv)
    };
    let binom = |n: usize, k: usize| -> ModInt {
        if n < k {
            ModInt::new(0)
        } else {
            fact[n] * finv[k] * finv[n - k]
        }
    };

    let mut ans = ModInt::new(0);
    a.sort();
    for (i, a_i) in a.iter().copied().enumerate() {
        ans += binom(i, k - 1) * a_i;
    }
    a.reverse();
    for (i, a_i) in a.iter().copied().enumerate() {
        ans -= binom(i, k - 1) * a_i;
    }

    println!("{}", ans);
}

// modint

今日のコミット。