結果
| 問題 |
No.2046 Ans Mod? Mod Ans!
|
| コンテスト | |
| ユーザー |
 asaringo
|
| 提出日時 | 2023-11-08 02:36:39 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 12,512 bytes |
| コンパイル時間 | 2,150 ms |
| コンパイル使用メモリ | 217,332 KB |
| 最終ジャッジ日時 | 2025-02-17 20:02:09 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 5 WA * 13 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
#define overload2(a, b, c, ...) c
#define overload3(a, b, c, d, ...) d
#define overload4(a, b, c, d, e ...) e
#define overload5(a, b, c, d, e, f ...) f
#define overload6(a, b, c, d, e, f, g ...) g
#define fast_io ios::sync_with_stdio(false); cin.tie(nullptr);
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
typedef long long ll;
typedef long double ld;
#define chmin(a,b) a = min(a,b);
#define chmax(a,b) a = max(a,b);
#define bit_count(x) __builtin_popcountll(x)
#define leading_zero_count(x) __builtin_clz(x)
#define trailing_zero_count(x) __builtin_ctz(x)
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) a / gcd(a,b) * b
#define rep(...) overload3(__VA_ARGS__, rrep, rep1)(__VA_ARGS__)
#define rep1(i,n) for(int i = 0 ; i < n ; i++)
#define rrep(i,a,b) for(int i = a ; i < b ; i++)
#define repi(it,S) for(auto it = S.begin() ; it != S.end() ; it++)
#define pt(a) cout << a << endl;
#define print(...) printall(__VA_ARGS__);
#define debug(a) cout << #a << " " << a << endl;
#define all(a) a.begin(), a.end()
#define endl "\n";
#define v1(T,n,a) vector<T>(n,a)
#define v2(T,n,m,a) vector<vector<T>>(n,v1(T,m,a))
#define v3(T,n,m,k,a) vector<vector<vector<T>>>(n,v2(T,m,k,a))
#define v4(T,n,m,k,l,a) vector<vector<vector<vector<T>>>>(n,v3(T,m,k,l,a))
template<typename T,typename U>istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<typename T,typename U>ostream &operator<<(ostream&os,const pair<T,U>&p){os<<p.first<<" "<<p.second;return os;}
template<typename T>istream &operator>>(istream&is,vector<T>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>istream &operator>>(istream&is,vector<vector<T>>&v){for(T &in:v){is>>in;}return is;}
template<typename T>ostream &operator<<(ostream&os,const vector<vector<T>>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?"\n":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const set<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<typename T>ostream &operator<<(ostream&os,const multiset<T>&v){for(auto it=v.begin();it!=v.end();){os<<*it<<((++it)!=v.end()?" ":"");}return os;}
template<class... Args> void printall(Args... args){for(auto i:initializer_list<common_type_t<Args...>>{args...}) cout<<i<<" ";cout<<endl;}
const int mod = 1000000007 ;
template< int mod >
struct ModInt {
int x;
ModInt() : x(0) {}
ModInt(int64_t y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
ModInt &operator+=(const ModInt &p) {
if((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int) (1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while(b > 0) {
t = a / b;
swap(a -= t * b, b);
swap(u -= t * v, v);
}
return ModInt(u);
}
ModInt pow(int64_t n) const {
ModInt ret(1), mul(x);
while(n > 0) {
if(n & 1) ret *= mul;
mul *= mul;
n >>= 1;
}
return ret;
}
friend ostream &operator<<(ostream &os, const ModInt &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ModInt &a) {
int64_t t;
is >> t;
a = ModInt< mod >(t);
return (is);
}
static int get_mod() { return mod; }
};
using modint = ModInt< mod >;
template<typename S, S (*op)(S, S), S (*e)(), typename M, S (*mapping)(M, S), M (*composition)(M, M), M (*id)()> struct LazySegmentTree{
private:
int size, log, _n;
vector<S> d;
vector<M> lz;
void init_(S ev, M idv, int size) { d = {}; lz = {}; d.resize(2*size,ev); lz.resize(size,idv); }
void build(vector<S> V){
size = 1;
log = 0;
while(size < _n) size *= 2, log++;
d = std::vector<S>(2 * size, e());
lz = std::vector<M>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = V[i];
for (int i = size - 1; i >= 1; i--) update(i);
}
// 与えられたMの値をapplyし、遅延配列にcompositionする
void all_apply(int k, M f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
// 自身の遅延配列を子要素に振り分け、自身の遅延配列をMの単位元にする
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
// 親のノード = 子ノード同士のop演算結果となる
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void set_(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get_(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
void apply_(int p, M f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply_(int l, int r, M f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
// l, rが葉から登っていく際に、現在自分がいるノードの遅延配列をmappingする必要がある。
// しかし、遅延セグメント木のアルゴリズムの関係上、本来格納されているはずの遅延配列上の値が自分のノードにはなく、親がもっていることがある。
// そのため、親から前もって自身のノードが持べき遅延配列の値をもらっておく必要がある。
// よって、このapply_関数上では、l, rの繊維先ノードで必要となる遅延配列の値（必要となる値のみ）を前もって子ノードに振り分けておく
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
S prod_(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod_() { return d[1]; }
template <bool (*g)(S)> int max_right_(int l) {
return max_right_(l, [](S x) { return g(x); });
}
template <class G> int max_right_(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left_(int r) {
return min_left_(r, [](S x) { return g(x); });
}
template <class G> int min_left_(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
public:
LazySegmentTree(int n): LazySegmentTree(vector<S>(n, e())) {}
LazySegmentTree(const vector<S>& V): _n((int)V.size()) { build(V); }
void init(S ev = e(), M idv = id()) { init_(ev, idv); }
void set(int p, S x) { set_(p,x); }
void apply(int k, M x) { apply_(k, x); }
void apply(int l, int r, M x) { apply_(l, r, x); }
S get(int k) { return get_(k); }
S prod(int l, int r) { return prod_(l, r); }
S all_prod() { return all_prod_(); }
template<bool (*f)(S)> int max_right(int l) { return max_right_<f>(l); }
template<bool (*f)(S)> int min_left(int r) { return min_left_<f>(r); }
};
// 区間和を取るときはSにsizeを持たせる(以下のmonoidのmappingの箇所を参考にする)
namespace monoid{
struct S{ modint sum; int size; };
S e() { return S{(modint)0, 0}; }
S op(S x , S y) { return S{ x.sum + y.sum, x.size + y.size }; }
struct M{ modint a; };
M id() { return M{0}; }
S mapping(M x , S y) { return S{ x.a * y.size + y.sum, y.size }; }
M composition(M x, M y) { return M{ x.a + y.a }; }
} using namespace monoid;
int n;
void solve(){
cin >> n;
vector<ll> A(n);
vector<modint> I(202020);
cin >> A;
rep(i,n) I[A[i]] += 1;
sort(all(A));
modint res = 0;
rep(i,n) {
auto it = upper_bound(all(A), A[i]);
int id = it - A.begin();
res += A[i] * (n - id);
}
vector<S> vec(202020);
rep(i,202020) vec[i] = {0,1};
LazySegmentTree<S, op, e, M, mapping, composition, id> segtree(vec);
rep(i,n) segtree.apply(A[i],A[i]+1,{A[i]});
rep(i,1,202020){
if(I[i] == 0) continue;
for(ll x = i; x < 202020; x += i){
modint cnt = upper_bound(all(A),x+i-1) - lower_bound(all(A),x);
res -= segtree.prod(x,min(x+i,(ll)202020)).sum * I[i] - cnt * x * I[i];
}
}
pt(res)
}
int main(){
fast_io
int t = 1;
// cin >> t;
rep(i,t) solve();
}