結果
問題 | No.2235 Line Up Colored Balls |
ユーザー |
|
提出日時 | 2023-03-04 20:53:04 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 12 ms / 2,000 ms |
コード長 | 7,865 bytes |
コンパイル時間 | 2,094 ms |
コンパイル使用メモリ | 195,608 KB |
最終ジャッジ日時 | 2025-02-11 05:26:11 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 55 |
ソースコード
#line 1 "modint_static.test.cpp"#define PROBLEM "https://yukicoder.me/problems/no/2235"// 提出時にassertはオフ#ifndef DEBUG#ifndef NDEBUG#define NDEBUG#endif#endif#include <bits/stdc++.h>#line 2 "/home/cocojapanpan/Procon_CPP/proconLibrary/myLibrary/modint_static.hpp"#line 2 "/home/cocojapanpan/Procon_CPP/proconLibrary/myLibrary/innermath_modint.hpp"#line 4 "/home/cocojapanpan/Procon_CPP/proconLibrary/myLibrary/innermath_modint.hpp"#ifdef _MSC_VER#include <intrin.h>#endifnamespace innermath_modint{using ll = long long;using ull = unsigned long long;using u128 = __uint128_t;// xのmodを[0, mod)で返すconstexpr ll safe_mod(ll x, ll mod) {x %= mod;if (x < 0) x += mod;return x;}constexpr ll pow_mod_constexpr(ll x, ll n, ll mod) {if (mod == 1) return 0;ll ret = 1;ll beki = safe_mod(x, mod);while (n) {// LSBから順に見るif (n & 1) {ret = (ret * beki) % mod;}beki = (beki * beki) % mod;n >>= 1;}return ret;}// int型(2^32以下)の高速な素数判定constexpr bool is_prime_constexpr(int n) {if (n <= 1) return false;if (n == 2 || n == 7 || n == 61) return true;if (n % 2 == 0) return false;// ミラーラビン判定 int型ならa={2,7,61}で十分constexpr ll bases[] = {2, 7, 61};// n-1 = 2^r * dll d = n - 1;while (d % 2 == 0) d >>= 1;// 素数modは1の平方根として非自明な解を持たない// つまり非自明な解がある→合成数for (ll a : bases) {ll t = d;ll y = pow_mod_constexpr(a, t, n);// yが1またはn-1になれば抜けるwhile (t != n - 1 && y != 1 && y != n - 1) {y = (y * y) % n;t <<= 1;}// 1の平方根として1と-1以外の解(非自明な解)が存在if (y != n - 1 && t % 2 == 0) {return false;}}return true;}// 拡張ユークリッドの互除法 g = gcd(a,b)と、ax = g (mod b)なる0 <= x <// b/gのペアを返すconstexpr std::pair<ll, ll> inv_gcd(ll a, ll b) {a = safe_mod(a, b);// aがbの倍数if (a == 0) return {b, 0};// 以下 0 <= a < b// [1] s - m0 * a = 0 (mod b)// [2] t - m1 * a = 0 (mod b)// [3] s * |m1| + t * |m0| <= bll s = b, t = a;ll m0 = 0, m1 = 1;while (t) {// s → s mod t// m0 → m0 - m1 * (s / t)ll u = s / t;s -= t * u;m0 -= m1 * u;std::swap(s, t);std::swap(m0, m1);}// s = gcd(a, b)// 終了の直前のステップにおいて// [1] k * s - m0 * a = 0 (mod b)// [2] s - m1 * a = 0 (mod b)// [3] (k * s) * |m1| + s * |m0| <= b// |m0| < b / sif (m0 < 0) m0 += b / s;return {s, m0};}// barret reduction 掛け算のmodの定数倍高速化(modが定数でない場合に使用)struct barretReduction {public:explicit barretReduction(uint _mod): mod(_mod),imod((ull)(-1) / mod + 1) {} // unsignedの場合、負で巡回するuint get_mod() const { return mod; }uint mul(int a, int b) const {ull z = a;z *= b;#ifdef _MSC_VERull x;_umul128(z, imod, &x)#else// x = z / mod またはその +1// 割り算をビットシフトにすることで高速化ull x = (ull)(((u128)z * imod) >> 64);#endif// z - x * mod = z % mod - mod の場合、uintなので 2^32 - (mod -// z % mod) つまりmodを足せば 2^32 + z %// modとなり、求めるmodになるuint v = (uint)(z - x * mod);if (v >= mod) v += mod;return v;}private:uint mod;ull imod; // ceil(2^64 / mod)};}#line 5 "/home/cocojapanpan/Procon_CPP/proconLibrary/myLibrary/modint_static.hpp"template <const int MOD>struct modint_static {using ll = long long;public:constexpr modint_static(ll x = 0) noexcept : value(x % MOD) {if (value < 0) value += MOD;}constexpr int get_mod() const noexcept { return MOD; }constexpr ll val() const noexcept { return value; }constexpr modint_static operator-() const noexcept {return modint_static(-value);}constexpr modint_static& operator++() noexcept {++value;if(value == MOD) value = 0;return *this;}constexpr modint_static& operator--() noexcept {if(value == 0) value = MOD;--value;return *this;}constexpr modint_static operator++(int) noexcept {modint_static cpy(*this);++(*this);return cpy;}constexpr modint_static operator--(int) noexcept {modint_static cpy(*this);--(*this);return cpy;}constexpr modint_static& operator+=(const modint_static& rhs) noexcept {value += rhs.value;if (value >= MOD) value -= MOD;return *this;}constexpr modint_static& operator-=(const modint_static& rhs) noexcept {value += (MOD - rhs.value);if (value >= MOD) value -= MOD;return *this;}constexpr modint_static& operator*=(const modint_static& rhs) noexcept {(value *= rhs.value) %= MOD; // 定数だとコンパイラ最適化がかかるreturn *this;}constexpr modint_static operator+(const modint_static& rhs) const noexcept {modint_static cpy(*this);return cpy += rhs;}constexpr modint_static operator-(const modint_static& rhs) const noexcept {modint_static cpy(*this);return cpy -= rhs;}constexpr modint_static operator*(const modint_static& rhs) const noexcept {modint_static cpy(*this);return cpy *= rhs;}constexpr modint_static pow(ll beki) const noexcept {modint_static curbekimod(*this);modint_static ret(1);while (beki > 0) {if (beki & 1) ret *= curbekimod;curbekimod *= curbekimod;beki >>= 1;}return ret;}// valueの逆元を求めるconstexpr modint_static inv() const noexcept {// 拡張ユークリッドの互除法auto [gcd_value_mod, inv_value] = innermath_modint::inv_gcd(value, MOD);assert(gcd_value_mod == 1);return modint_static(inv_value);}constexpr modint_static& operator/=(const modint_static& rhs) noexcept {return (*this) *= rhs.inv();}constexpr modint_static operator/(const modint_static& rhs) const noexcept {modint_static cpy(*this);return cpy /= rhs;}private:ll value;};using mint998244353 = modint_static<998244353>;using mint1000000007 = modint_static<1000000007>;#line 12 "modint_static.test.cpp"using namespace std;using ll = long long;using mint = mint1000000007;#define ALL(x) (x).begin(), (x).end()template <class T> using vec = vector<T>;int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int N;cin >> N;vec<ll> x(N);for(ll &num : x) cin >> num;// ((Σx)^2 - Σx^2) / Σx + 1mint sum = 0, sum_square = 0;for(int i = 0; i < N; i++){sum += x[i];sum_square += x[i] * x[i];}mint ans = sum.pow(2) - sum_square;ans /= sum;ans++;cout << ans.val() << "\n";}