[yukicoder] No. 1237 EXP Multiple!

2020年9月27日2020年12月12日

問題

方針

問題文を注意して読みます。\( a^{a!} \) は

\[ a^{a!} = a^{a \cdot (a-1) \cdot \cdots \cdot 2\cdot 1}\]

なので発散するスピードが速く、\( 4^{4!} > 10^9 + 7 \) となります。 したがって、\( A_i \geq 4 \) を満たすとき、答えは \( 10^9 + 7 \) となります。また、\( 2^{2!} = 1 \)、\( 3^{3!} = 729 \) をあらかじめ計算しておき、\( \prod_{k = 1}^{N}A_k^{A_k}\) の値が \( 10^{9} + 7 \) を超えた時、答えは \( 10^9 + 7 \) となり、そうでなければ、\( (10^9 + 7 \bmod \prod_{k = 1}^{N}A_k^{A_k})\) を出力します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll mod = 1000000007;

int main() {
    int N;
    cin >> N;
    ll A[N];
    bool flag0 = false;
    bool flag4 = false;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        if (A[i] == 0) flag0 = true;
        if (A[i] >= 4) flag4 = true;
    }
    if (flag0) {
        cout << "-1\n";
        return 0;
    }
    if (flag4) {
        cout << mod << "\n";
        return 0;
    }
    ll ans = 1;
    int cnt = 0;
    ll b[3] = {1, 4, 729};
    for (int i = 0; i < N; i++) {
        ans *= b[A[i] - 1];
        if (ans > mod) break;
    }
    cout << (mod % ans) << "\n";
    return 0;
}