#1007042 (C++23) No.125 悪の花弁

提出ソース
結果

問題	No.125 悪の花弁
ユーザー	AC2K
提出日時	2024-09-03 22:43:24
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	103 ms / 5,000 ms
コード長	15,102 bytes
コンパイル時間	3,346 ms
コンパイル使用メモリ	256,512 KB
実行使用メモリ	27,292 KB
最終ジャッジ日時	2024-09-03 22:43:28
合計ジャッジ時間	4,560 ms
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	53 ms 24,740 KB
testcase_01	AC	73 ms 24,892 KB
testcase_02	AC	86 ms 27,292 KB
testcase_03	AC	103 ms 27,248 KB
testcase_04	AC	59 ms 26,896 KB
testcase_05	AC	59 ms 26,868 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#line 1 "Library/src/debug.hpp"
#ifdef ONLINE_JUDGE
#define debug(x) void(0)
#else
#define _GLIBCXX_DEBUG
#define debug(x) std::cerr << __LINE__ << " : " << #x << " = " << (x) << std::endl
#endif

/**
 * @brief Debugger
*/
#line 2 "Library/src/math/combination.hpp"
#include <algorithm>
#include <cassert>
using namespace std;
namespace kyopro {

template <typename mint, int sz> class combination {
    const int M;
    mint fac[sz + 1], ifac[sz + 1];

public:
    combination() : M(std::min<int>(mint::mod(), sz)) {
        assert(mint::mod());
        fac[0] = mint(1), ifac[0] = mint(1), fac[1] = mint(1),
        ifac[1] = mint(1);

        for (int i = 2; i <= M; ++i) {
            fac[i] = fac[i - 1] * i;
        }

        ifac[M - 1] = mint(1) / fac[M - 1];
        for (int i = M - 2; i > 1; --i) {
            ifac[i] = ifac[i + 1] * (i + 1);
        }
    }

    constexpr mint fact(int n) const {
        assert(0 <= n && n <= sz);
        return fac[n];
    }
    constexpr mint ifact(int n) const {
        assert(0 <= n && n <= sz);
        return ifac[n];
    }

    constexpr mint binom(int n, int r) const {
        assert(n >= r);
        return fact(n) * ifact(r) * ifact(n - r);
    }
    constexpr mint perm(int n, int r) const {
        assert(n >= r);
        return fact(n) * ifact(n - r);
    }
};

};  // namespace kyopro

/**
 * @brief Combination
 */
#line 2 "Library/src/math/divisor-multiple-transform.hpp"
#include <vector>
namespace kyopro {

namespace internal {
std::vector<int> enumerate_primes(int n) {
    std::vector<int> primes;
    {
        std::vector<bool> f(n + 1);
        for (int i = 2; i <= n; ++i) {
            if (f[i]) continue;

            primes.emplace_back(i);
            for (int j = 2 * i; j <= n; j += i) f[j] = 1;
        }
    }
    return primes;
}
};  // namespace internal

namespace multiple {
template <typename T> void zeta(std::vector<T>& f) {
    std::vector primes = internal::enumerate_primes(f.size());
    for (auto p : primes) {
        for (int i = ((int)f.size() - 1) / p; i >= 1; --i) {
            f[i] += f[p * i];
        }
    }
    return;
}

template <typename T> void mobius(std::vector<T>& f) {
    std::vector primes = internal::enumerate_primes(f.size());

    for (auto p : primes) {
        for (int i = 1 / p; p * i < (int)f.size(); ++i) {
            f[i] -= f[p * i];
        }
    }
    return;
}
};  // namespace multiple

namespace divisor {
template <typename T> void zeta(std::vector<T>& f) {
    std::vector primes = internal::enumerate_primes(f.size());

    for (auto p : primes) {
        for (int i = 1; i * p < (int)f.size(); ++i) {
            f[i * p] += f[i];
        }
    }
};
template <typename T> void mobius(std::vector<T>& f) {
    std::vector primes = internal::enumerate_primes(f.size());
    for (auto p : primes) {
        for (int i = (int)(f.size() - 1) / p * p; i >= 1; i -= p) {
            f[i] -= f[i / p];
        }
    }
};
};  // namespace divisor

};  // namespace kyopro

/**
 * @brief Divisor・Multiple Transform
 * @docs docs/math/divisor-multiple-transform.md
 */
#line 3 "Library/src/math/static_modint.hpp"
#include <cstdint>
#include <iostream>

#line 3 "Library/src/internal/type_traits.hpp"
#include <limits>
#include <numeric>
#include <typeinfo>
#line 7 "Library/src/internal/type_traits.hpp"

namespace kyopro {
namespace internal {
template <typename... Args> struct first_enabled {};

template <typename T, typename... Args>
struct first_enabled<std::enable_if<true, T>, Args...> {
    using type = T;
};
template <typename T, typename... Args>
struct first_enabled<std::enable_if<false, T>, Args...>
    : first_enabled<Args...> {};
template <typename T, typename... Args> struct first_enabled<T, Args...> {
    using type = T;
};

template <typename... Args>
using first_enabled_t = typename first_enabled<Args...>::type;

template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct int_least {
    using type = first_enabled_t<std::enable_if<dgt <= 8, std::int8_t>,
                                 std::enable_if<dgt <= 16, std::int16_t>,
                                 std::enable_if<dgt <= 32, std::int32_t>,
                                 std::enable_if<dgt <= 64, std::int64_t>,
                                 std::enable_if<dgt <= 128, __int128_t>>;
};

template <int dgt, std::enable_if_t<dgt <= 128>* = nullptr> struct uint_least {
    using type = first_enabled_t<std::enable_if<dgt <= 8, std::uint8_t>,
                                 std::enable_if<dgt <= 16, std::uint16_t>,
                                 std::enable_if<dgt <= 32, std::uint32_t>,
                                 std::enable_if<dgt <= 64, std::uint64_t>,
                                 std::enable_if<dgt <= 128, __uint128_t>>;
};

template <int dgt> using int_least_t = typename int_least<dgt>::type;
template <int dgt> using uint_least_t = typename uint_least<dgt>::type;

template <typename T>
using double_size_uint_t = uint_least_t<2 * std::numeric_limits<T>::digits>;

template <typename T>
using double_size_int_t = int_least_t<2 * std::numeric_limits<T>::digits>;

struct modint_base {};
template <typename T> using is_modint = std::is_base_of<modint_base, T>;
template <typename T> using is_modint_t = std::enable_if_t<is_modint<T>::value>;


// is_integral
template <typename T>
using is_integral_t =
    std::enable_if_t<std::is_integral_v<T> || std::is_same_v<T, __int128_t> ||
                   std::is_same_v<T, __uint128_t>>;
};  // namespace internal
};  // namespace kyopro

/**
 * @brief Type Traits
 * @see https://qiita.com/kazatsuyu/items/f8c3b304e7f8b35263d8
 */
#line 3 "Library/src/math/gcd.hpp"
#include <cmath>
#include <tuple>
namespace kyopro {
template <typename T> constexpr inline T _gcd(T a, T b) noexcept {
    assert(a >= 0 && b >= 0);
    if (a == 0 || b == 0) return a + b;
    int d = std::min<T>(__builtin_ctzll(a), __builtin_ctzll(b));
    a >>= __builtin_ctzll(a), b >>= __builtin_ctzll(b);
    while (a != b) {
        if (!a || !b) {
            return a + b;
        }
        if (a >= b) {
            a -= b;
            a >>= __builtin_ctzll(a);
        } else {
            b -= a;
            b >>= __builtin_ctzll(b);
        }
    }

    return a << d;
}

template <typename T>
constexpr inline T ext_gcd(T a, T b, T& x, T& y) noexcept {
    x = 1, y = 0;
    T nx = 0, ny = 1;
    while (b) {
        T q = a / b;
        std::tie(a, b) = std::pair<T, T>{b, a % b};
        std::tie(x, nx) = std::pair<T, T>{nx, x - nx * q};
        std::tie(y, ny) = std::pair<T, T>{ny, y - ny * q};
    }
    return a;
}
};  // namespace kyopro

/**
 * @brief gcd
*/
#line 8 "Library/src/math/static_modint.hpp"
namespace kyopro {
template <int _mod, std::enable_if_t<_mod >= 0>* = nullptr>
class modint : internal::modint_base {
    using mint = modint<_mod>;
    using i32 = std::int32_t;
    using u32 = std::uint32_t;
    using i64 = std::int64_t;
    using u64 = std::uint64_t;

    u32 v;
    constexpr u32 normalize(i64 v_) const noexcept {
        v_ %= _mod;
        if (v_ < 0) {
            v_ += _mod;
        }
        return v_;
    }

public:
    static constexpr u32 mod() noexcept { return _mod; }
    constexpr modint() noexcept : v(0) {}
    constexpr modint(i64 v_) noexcept : v(normalize(v_)) {}

    static mint raw(u32 a) {
        mint m;
        m.v = a;
        return m;
    }
    constexpr u32 val() const noexcept { return v; }
    constexpr mint& operator+=(const mint& rhs) noexcept {
        v += rhs.val();
        if (v >= _mod) {
            v -= _mod;
        }
        return (*this);
    }
    constexpr mint& operator-=(const mint& rhs) noexcept {
        v += _mod - rhs.val();
        if (v >= _mod) {
            v -= _mod;
        }
        return (*this);
    }
    constexpr mint& operator*=(const mint& rhs) noexcept {
        v = (u64)v * rhs.val() % _mod;
        return (*this);
    }

    constexpr mint operator+(const mint& r) const noexcept {
        return mint(*this) += r;
    }
    constexpr mint operator-(const mint& r) const noexcept {
        return mint(*this) -= r;
    }
    constexpr mint operator*(const mint& r) const noexcept {
        return mint(*this) *= r;
    }

    constexpr mint& operator+=(i64 rhs) noexcept {
        (*this) += mint(rhs);
        return (*this);
    }
    constexpr mint& operator-=(i64 rhs) noexcept {
        (*this) -= mint(rhs);
        return (*this);
    }
    constexpr mint& operator*=(i64 rhs) noexcept {
        (*this) *= mint(rhs);
        return (*this);
    }
    constexpr friend mint operator+(i64 l, const mint& r) noexcept {
        return mint(l) += r;
    }
    constexpr friend mint operator-(i64 l, const mint& r) noexcept {
        return mint(l) -= r;
    }
    constexpr friend mint operator*(i64 l, const mint& r) noexcept {
        return mint(l) *= r;
    }

    constexpr mint operator+(i64 r) const noexcept { return mint(*this) += r; }
    constexpr mint operator-(i64 r) const noexcept { return mint(*this) -= r; }
    constexpr mint operator*(i64 r) const noexcept { return mint(*this) *= r; }

    constexpr mint& operator=(i64 r) noexcept { return (*this) = mint(r); }

    constexpr bool operator==(const mint& r) const noexcept {
        return (*this).val() == r.val();
    }

    template <typename T, internal::is_integral_t<T>* = nullptr>
    constexpr mint pow(T e) const noexcept {
        mint ans(1), base(*this);
        while (e) {
            if (e & 1) {
                ans *= base;
            }
            base *= base;
            e >>= 1;
        }
        return ans;
    }

    constexpr mint inv() const noexcept {
        long long x, y;
        auto d = ext_gcd((long long)_mod, (long long)v, x, y);
        assert(d == 1);
        return mint(y);
    }

    constexpr mint& operator/=(const mint& r) noexcept {
        return (*this) *= r.inv();
    }
    constexpr mint operator/(const mint& r) const noexcept {
        return mint(*this) *= r.inv();
    }
    constexpr friend mint operator/(const mint& l, i64 r) noexcept {
        return mint(l) /= mint(r);
    }
    constexpr friend mint operator/(i64 l, const mint& r) noexcept {
        return mint(l) /= mint(r);
    }
};
};  // namespace kyopro

/**
 * @brief static modint
 */
#line 2 "Library/src/stream.hpp"
#include <ctype.h>
#include <stdio.h>
#include <string>
#line 6 "Library/src/stream.hpp"

namespace kyopro {

inline void single_read(char& c) {
    c = getchar_unlocked();
    while (isspace(c)) c = getchar_unlocked();
}
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_read(T& a) {
    a = 0;
    bool is_negative = false;
    char c = getchar_unlocked();
    while (isspace(c)) {
        c = getchar_unlocked();
    }
    if (c == '-') is_negative = true, c = getchar_unlocked();
    while (isdigit(c)) {
        a = 10 * a + (c - '0');
        c = getchar_unlocked();
    }
    if (is_negative) a *= -1;
}
template <typename T, internal::is_modint_t<T>* = nullptr>
inline void single_read(T& a) {
    long long x;
    single_read(x);
    a = T(x);
}
inline void single_read(std::string& str) noexcept {
    char c = getchar_unlocked();
    while (isspace(c)) c = getchar_unlocked();
    while (!isspace(c)) {
        str += c;
        c = getchar_unlocked();
    }
}
template<typename T>
inline void read(T& x) noexcept {single_read(x);}
template <typename Head, typename... Tail>
inline void read(Head& head, Tail&... tail) noexcept {
    single_read(head), read(tail...);
}

inline void single_write(char c) noexcept { putchar_unlocked(c); }
template <typename T, internal::is_integral_t<T>* = nullptr>
inline void single_write(T a) noexcept {
    if (!a) {
        putchar_unlocked('0');
        return;
    }
    if constexpr (std::is_signed_v<T>) {
        if (a < 0) putchar_unlocked('-'), a *= -1;
    }
    constexpr int d = std::numeric_limits<T>::digits10;
    char s[d + 1];
    int now = d + 1;
    while (a) {
        s[--now] = (char)'0' + a % 10;
        a /= 10;
    }
    while (now <= d) putchar_unlocked(s[now++]);
}
template <typename T, internal::is_modint_t<T>* = nullptr>
inline void single_write(T a) noexcept {
    single_write(a.val());
}
inline void single_write(const std::string& str) noexcept {
    for (auto c : str) {
        putchar_unlocked(c);
    }
}
template <typename T> inline void write(T x) noexcept { single_write(x); }
template <typename Head, typename... Tail>
inline void write(Head head, Tail... tail) noexcept {
    single_write(head);
    putchar_unlocked(' ');
    write(tail...);
}
template <typename... Args> inline void put(Args... x) noexcept {
    write(x...);
    putchar_unlocked('\n');
}
};  // namespace kyopro

/**
 * @brief Fast IO(高速入出力)
 */
#line 2 "Library/src/template.hpp"
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) std::begin(x), std::end(x)
#define popcount(x) __builtin_popcountll(x)
using i128 = __int128_t;
using ll = long long;
using ld = long double;
using graph = std::vector<std::vector<int>>;
using P = std::pair<int, int>;
constexpr int inf = std::numeric_limits<int>::max() / 2;
constexpr ll infl = std::numeric_limits<ll>::max() / 2;
const long double pi = acosl(-1);
constexpr int dx[] = {1, 0, -1, 0, 1, -1, -1, 1, 0};
constexpr int dy[] = {0, 1, 0, -1, 1, 1, -1, -1, 0};
template <typename T1, typename T2> constexpr inline bool chmax(T1& a, T2 b) {
    return a < b && (a = b, true);
}
template <typename T1, typename T2> constexpr inline bool chmin(T1& a, T2 b) {
    return a > b && (a = b, true);
}

/**
 * @brief Template
*/
#line 7 "a.cpp"

using namespace std;
using namespace kyopro;

using mint = modint<(int)1e9 + 7>;
combination<mint, (int)2e6> com;

int main() {
    int n;
    read(n);

    vector c(n, 0);
    rep(i, n) read(c[i]);

    int cs = accumulate(all(c), 0);

    debug(cs);

    vector<mint> f(cs + 1);  // xを周期に持つような並べ方

    for (int l = 1; l <= cs; ++l) {
        if (cs % l != 0) continue;

        debug(l);
        debug(cs / l);
        f[l] = com.fact(l);

        rep(i, n) {
            if (c[i] % (cs / l) != 0) {
                f[l] = 0;
                break;
            }
            f[l] /= com.fact(c[i] / (cs / l));
        }
        debug(f[l].val());
    }

    // rep(i, (int)f.size()) cout << f[i].val() << " \n"[i == f.size() - 1];

    // 最小周期がλ→kλも周期のひとつ

    // f(x) := xを周期にもつような塗り方
    // g(x) := 最小周期がxとなるような塗り方
    // → f(x) := Σ g(y) (x = ky i.e. y divides x)

    divisor::mobius(f);  // 最小周期に直す

    // rep(i, (int)f.size()) cout << f[i].val() << " \n"[i == (int)f.size() - 1];

    vector answer(cs, mint());
    for (int i = 1; i <= cs; ++i) {
        if (cs % i != 0) continue;
        for (int j = 0; j < cs; j += i) {
            answer[j] += f[i];
        }
    }

    // rep(i, (int)answer.size()) {
    //     cout << answer[i].val() << " \n"[i == (int)answer.size() - 1];
    // }

    put(accumulate(all(answer), mint()) / cs);
}
yukicoder

結果

テストケース

ソースコード
