ARC 035 B - アットコーダー王国のコンテスト事情

問題

問題概要

省略

解法

解く時間が小さい順にといていけば、ペナルティーが最小になる。何通りあるかは、同じもののなかで並び替えてもペナルティーが最小であることに違いはないので、同じ数字がx個あれば、x!通り存在することになるので、それらをかけ合わせればよい。

ミス

階乗を計算するのに、逆元を使う練習もできた。
参考

http://hos.ac/slides/20130319_enumeration.pdf

コード

#include <iostream>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

ll inv[10010];
ll fac[10010], facInv[10010];
const ll P = 1e9 + 7;
void fuctorialmod(void){
    inv[1] = 1;
    for (int i = 2; i <= 10000; ++i)
    {
        inv[i] = P - (P / i) * inv[P % i] % P;
    }

    fac[0] = facInv[0] = 1;
    for (int i = 1; i <= 10000; ++i)
    {
        fac[i] = (fac[i - 1] * i) % P;
        facInv[i] = (facInv[i - 1] * inv[i]) % P;
    }
}

int n;
int buket[10010];
int main(void){
    cin >> n;
    vector<int> t;
    rep(i, 10010) buket[i] = 0;
    rep(i, n){
        int d; cin >> d;
        t.push_back(d);
        buket[d]++;
    }
    sort(t.begin(), t.end());
    ll time = 0;
    ll ans = 0;
    rep(i, t.size()){
        time += t[i];
        ans += time;
    }
    
    fuctorialmod();
    ll narabi = 1;
    for (int i = 1; i <= 10000; ++i){
        int num = buket[i];
        narabi *= fac[num];
        narabi %= P;
    }
    printf("%lld\n", ans);
    printf("%lld\n", narabi % P);
    return 0;
}