Theme Color [CODE FESTIVAL 2018 Final B]

https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_b

解説

https://beta.atcoder.jp/contests/code-festival-2018-final-open/submissions/3622296

まず、確率pの式を立てよう。
分母はM通りがN個分あるので、M^N
これはN個をM色で彩色した組み合わせとも言える。
分子は彩色されている色の個数が指定の個数である組み合わせなのだが、同じものがあるときの順列の要領で式を立てよう。
すると、確率pの式は
p=(N!/(R[0]! * R[1]! * ... * R[M-1]!))/(M^N)
となる。

p=(N!/(R[0]! * R[1]! * ... * R[M-1]!))/(M^N)であるので、
(N!/(R[0]! * R[1]! * ... * R[M-1]!))/(M^N)≧10^(-x)
N!/( (R[0]! * R[1]! * ... * R[M-1]!)*(M^N) )≧10^(-x)
10^x≧( (R[0]! * R[1]! * ... * R[M-1]!)*(M^N) )/N!
x≧log10( ( (R[0]! * R[1]! * ... * R[M-1]!)*(M^N) )/N! )

のように式変形をして、右辺を計算すると、ceilに書けたものが答えのxとなる。

int N, M; int R[101010];
double fact[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> R[i];
    fact[0] = 0;
    rep(i, 1, N + 1) fact[i] = fact[i - 1] + log10(i);

    double y = 0;
    rep(i, 0, M) y += fact[R[i]];
    y += log10(M) * N;
    y -= fact[N];

    int x = ceil(y);
    cout << x << endl;
}