#806085 (C++17) No.125 悪の花弁

• 問題: No.125 悪の花弁
• ユーザー: ytqm3
• 提出日時: 2022-10-11 16:29:57
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 407 ms / 5,000 ms
• コード長: 10,575 bytes
• コンパイル時間: 5,110 ms
• コンパイル使用メモリ: 283,292 KB
• 実行使用メモリ: 31,072 KB
• 最終ジャッジ日時: 2024-06-25 11:44:42
• 合計ジャッジ時間: 6,998 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	92 ms; 29,440 KB
testcase_01	AC	407 ms; 29,920 KB
testcase_02	AC	198 ms; 31,072 KB
testcase_03	AC	195 ms; 31,052 KB
testcase_04	AC	117 ms; 30,632 KB
testcase_05	AC	120 ms; 30,684 KB

ソースコード

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
#endif

namespace ttl {

    using namespace std;
    using f80 = long double;
    using i64 = int64_t;
    using u64 = uint64_t;

    template<int mod> struct mymodint {
        i64 vl;
        static constexpr i64 get_mod() { return mod; }
        i64 val() { return vl; }
        mymodint(i64 vl_ = 0) :vl(vl_% mod) {}
        mymodint operator-() { return (vl == 0) ? 0 : mod - vl; }
        mymodint operator+(mymodint rhs) { return mymodint(*this) += rhs; }
        mymodint operator-(mymodint rhs) { return mymodint(*this) -= rhs; }
        mymodint operator*(mymodint rhs) { return mymodint(*this) *= rhs; }
        mymodint operator/(mymodint rhs) { return mymodint(*this) /= rhs; }
        mymodint pow(i64 rhs) {
            mymodint res = 1, now = (*this);
            while (rhs) {
                res *= ((rhs & 1) ? now : 1), now *= now, rhs >>= 1;
            }
            return res;
        }
        mymodint& operator+=(mymodint rhs) {
            vl += rhs.vl, vl -= ((vl >= mod) ? mod : 0);
            return (*this);
        }
        mymodint& operator-=(mymodint rhs) {
            vl += ((vl < rhs.vl) ? mod : 0), vl -= rhs.vl;
            return (*this);
        }
        mymodint& operator*=(mymodint rhs) {
            vl = vl * rhs.vl % mod;
            return (*this);
        }
        mymodint& operator/=(mymodint rhs) { return (*this) *= rhs.pow(mod - 2); }
        bool operator==(mymodint rhs) { return vl == rhs.vl; }
        bool operator!=(mymodint rhs) { return vl != rhs.vl; }
    };

    template<u64 mod> using modint =
#if __has_include(<atcoder/all>)
        atcoder::static_modint<mod>;
#else
        mymodint<mod>;
#endif

    template<int mod> std::ostream& operator<<(std::ostream& os, modint<mod> x) {
        return os << (x.val());
    }
    template<int mod> std::istream& operator>>(std::istream& is, modint<mod>& x) {
        i64 t;
        is >> t, x = t;
        return is;
    }

    template<class T> void scn_(T& a) { cin >> a; }
    template<class T, class U> void scn_(pair<T, U>& a) { scn_(a.first), scn_(a.second); }
    template<class T> void scn_(vector<T>& a) {
        for (auto& v : a) {
            scn_(v);
        }
    }
    template<class T> void scn_(vector<vector<T>>& a) {
        for (auto& v : a) {
            for (auto& u : v) {
                cin >> u;
            }
        }
    }
    void scn() {}
    template<class T, class... Args> void scn(T& n, Args&... args) { scn_(n), scn(args...); }
    template<class T> void prt_(T a) { cout << a; }
    template<class T, class U> void prt_(pair<T, U> a) { cout << "{" << a.first << ", " << a.second << "}"; }
    void prt_(f80 a) { printf("%.15Lf", a); }
    template<class T> void prt(vector<T> a) {
        for (size_t i = 0; i < a.size(); ++i) {
            prt_(a[i]);
            cout << " \n"[i == a.size() - 1];
        }
    }
    template<class T> void prt(vector<vector<T>> a) {
        for (auto& v : a) {
            for (size_t i = 0; i < v.size(); ++i) {
                cout << v[i] << " \n"[i == v.size() - 1];
            }
        }
    }
    template<class T> void prt(T a) { prt_(a), cout << "\n"; }
    template<class T, class... Args> void prt(T a, Args... args) { prt_(a), cout << " ", prt(args...); }

    template<class Head, class... Tail> struct multi_dim_vector { using type = vector<typename multi_dim_vector<Tail...>::type>; };
    template<class T> struct multi_dim_vector<T> { using type = T; };
    template<class T, class Arg> vector<T> mvec(int n, Arg&& arg) { return vector<T>(n, arg); }
    template<class T, class... Args> class multi_dim_vector<Args..., T>::type mvec(int n, Args&&... args) {
        return typename multi_dim_vector<Args..., T>::type(n, mvec<T>(args...));
    }

    template<class T> void rev(T& a) { reverse(a.begin(), a.end()); }
    template<class T> void srt(T& a) { sort(a.begin(), a.end()); }
    template<class T> void rsrt(T& a) { sort(a.rbegin(), a.rend()); }
    template<class T> T revd(T a) {
        reverse(a.begin(), a.end());
        return a;
    }
    template<class T> T srtd(T a) {
        sort(a.begin(), a.end());
        return a;
    }
    template<class T> T rsrtd(T a) {
        sort(a.rbegin(), a.rend());
        return a;
    }
    template<class T> T summ(vector<T> a) { return accumulate(a.begin(), a.end(), T(0)); }
    template<class T> T maxi(vector<T> a) { return *max_element(a.begin(), a.end()); }
    template<class T> T mini(vector<T> a) { return *min_element(a.begin(), a.end()); }
    template<class T> void chmx(T& a, T b) { a = max(a, b); }
    template<class T> void chmn(T& a, T b) { a = min(a, b); }
    i64 ppcnt(u64 k) { return __builtin_popcountll(k); }
    template<class T> T powe(T a, i64 n) {
        T res = 1;
        while (n) {
            if (n & 1) { res *= a; }
            a *= a;
            n /= 2;
        }
        return res;
    }
    i64 powe(i64 a, i64 n, i64 m) {
        i64 res = 1;
        while (n) {
            if (n & 1) { res = res * a % m; }
            a = a * a % m;
            n /= 2;
        }
        return res;
    }
    template<class T> void zip(vector<T>& a) {
        auto b = srtd(a);
        b.erase(unique(b.begin(), b.end()), b.end());
        map<T, int> mp;
        for (int i = 0; i < b.size(); ++i) {
            mp[b[i]] = i;
        }
        for (auto& v : a) {
            v = mp[v];
        }
    }
    i64 sqrf(i64 n) {
        i64 ok = 0, ng = 1e9 + 5;
        while (std::abs(ok - ng) > 1) {
            i64 mid = (ok + ng) / 2;
            (mid * mid <= n ? ok : ng) = mid;
        }
        return ok;
    }
    i64 sqrc(i64 n) {
        i64 ok = 1e9 + 5, ng = 0;
        while (std::abs(ok - ng) > 1) {
            i64 mid = (ok + ng) / 2;
            (mid * mid >= n ? ok : ng) = mid;
        }
        return ok;
    }
    i64 dvf(i64 a, i64 b) {
        if (b < 0) { a *= -1, b *= -1; }
        if (a < 0) { return -(-a + b - 1) / b; }
        return a / b;
    }
    i64 dvc(i64 a, i64 b) {
        if (b < 0) { a *= -1, b *= -1; }
        if (a < 0) { return -(-a) / b; }
        return (a + b - 1) / b;
    }
    vector<int> bfs(vector<vector<int>> G, int v) {
        int N = G.size();
        vector<int> dst(N, -1);
        queue<int> q;
        dst[v] = 0;
        q.emplace(v);
        while (q.size()) {
            int t = q.front();
            q.pop();
            for (auto u : G[t]) {
                if (dst[u] == -1) {
                    dst[u] = dst[t] + 1;
                    q.emplace(u);
                }
            }
        }
        return dst;
    }
    vector<i64> dijkstra(vector<vector<pair<int, i64>>>& G, int s) {
        int N = G.size();
        vector<i64> dst(N, 1e18);
        dst[s] = 0;
        priority_queue<pair<i64, int>, vector<pair<i64, int>>, greater<pair<i64, int>>> pq;
        pq.emplace(0, s);
        vector<int> f(N);
        while (pq.size()) {
            auto [t, u] = pq.top();
            pq.pop();
            if (f[u]) { continue; }
            f[u] = 1;
            for (auto [v, w] : G[u]) {
                if (dst[v] > dst[u] + w) {
                    dst[v] = dst[u] + w;
                    pq.emplace(dst[v], v);
                }
            }
        }
        return dst;
    }
    vector<pair<i64, i64>> pfct(i64 n) {
        vector<pair<i64, i64>> res;
        for (i64 i = 2; i * i <= n; ++i) {
            if (n % i != 0) { continue; }
            i64 ex = 0;
            while (n % i == 0) { ex++, n /= i; }
            res.emplace_back(i, ex);
        }
        if (n != 1) { res.emplace_back(n, 1); }
        return res;
    }
    vector<i64> ediv(i64 n) {
        vector<i64> res;
        for (i64 i = 1; i * i <= n; ++i) {
            if (n % i != 0) { continue; }
            res.emplace_back(i);
            if (i * i != n) { res.emplace_back(n / i); }
        }
        srt(res);
        return res;
    }
    template<class T> struct csm2d {
        int n, m;
        vector<vector<T>> a, c;
        csm2d(vector<vector<T>> a_) :n(a_.size()), m(a_[0].size()), a(a_) {
            auto b = mvec<T>(n, m + 1, 0);
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    b[i][j + 1] = b[i][j] + a[i][j];
                }
            }
            c = mvec<T>(n + 1, m + 1, 0);
            for (int j = 0; j < m + 1; ++j) {
                for (int i = 0; i < n; ++i) {
                    c[i + 1][j] = c[i][j] + b[i][j];
                }
            }
        }
        T operator()(int p, int q, int r, int s) {
            return c[p][r] - c[p][s] - c[q][r] + c[q][s];
        }
    };
    template<class T> auto runlng(T a) -> vector<pair<typename decltype(a)::value_type, i64>> {
        int n = a.size();
        vector<pair<typename decltype(a)::value_type, i64>> res;
        typename decltype(a)::value_type now = a[0];
        i64 l = 1;
        for (int i = 1; i < n; ++i) {
            if (a[i - 1] == a[i]) { l++; }
            else {
                res.emplace_back(now, l);
                now = a[i], l = 1;
            }
        }
        res.emplace_back(now, l);
        return res;
    }
    template<class T> struct cmb {
        vector<T> fac, ifac;
        cmb(int mx = 3000000) :fac(mx + 1, 1), ifac(mx + 1, 1) {
            for (int i = 1; i <= mx; ++i) { fac[i] = fac[i - 1] * i; }
            ifac[mx] /= fac[mx];
            for (int i = mx; i > 0; --i) { ifac[i - 1] = ifac[i] * i; }
        }
        T operator()(i64 n, i64 k) {
            if (n < 0 || k < 0 || n < k) { return 0; }
            return fac[n] * ifac[k] * ifac[n - k];
        }
        T f(i64 n) {
            return n < 0 ? T(0) : fac[n];
        }
        T fi(i64 n) {
            return n < 0 ? T(0) : ifac[n];
        }
    };

}

using namespace ttl;

int main() {
    constexpr int mod = 1000000007;
    using mint = modint<mod>;
    cmb<mint> Cb;
    int K;
    scn(K);
    vector<int> C(K);
    scn(C);
    /*
    * すべての k について、条件 ai = a{i+k} 下で数え上げ
    */
    int S = summ(C);
    mint ans = 0;
    auto v = ediv(S);
    vector<mint> tb(S + 1);
    for (auto u : v) {
        //構造の個数が u
        tb[u] = Cb.f(u);
        for (int i = 0; i < K; ++i) {
            if (C[i] % (S / u) != 0) {
                tb[u] = 0;
            }
            tb[u] *= Cb.fi(C[i] / (S / u));
        }
    }
    for (int k = 0; k < S; ++k) {
        int l = gcd(S, k);
        ans += tb[l];
    }
    prt(ans / S);
}