結果
| 問題 | No.1844 Divisors Sum Sum |
| ユーザー |
 YFuka86
|
| 提出日時 | 2022-07-04 11:25:11 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 173 ms / 3,000 ms |
| コード長 | 9,835 bytes |
| コンパイル時間 | 2,651 ms |
| コンパイル使用メモリ | 200,284 KB |
| 実行使用メモリ | 11,720 KB |
| 最終ジャッジ日時 | 2024-11-30 21:02:34 |
| 合計ジャッジ時間 | 7,963 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 38 |
ソースコード
#pragma GCC optimize("Ofast")#include <bits/stdc++.h>#define rep(i,n) for(ll i=0;i<(ll)(n);i++)#define rep_r(i,n) for(ll i=(ll)(n)-1;i>=0;i--)#define rep2(i,sta,n) for(ll i=sta;i<(ll)(n);i++)#define rep2_r(i,sta,n) for(ll i=(ll)(n)-1;i>=sta;i--)#define all(v) (v).begin(),(v).end()#define vlin(name,sz,offset) vl name(sz); rep(i,sz){cin>>name[i]; name[i]-=offset;}#define pb push_back#define mp make_pair#define fi first#define se secondusing namespace std;typedef long long ll; typedef unsigned long long ull; typedef long double ld;typedef pair<int, int> P; typedef pair<ll, ll> LP; typedef map<ll, ll> LM; typedef tuple<ll, ll, ll> LT; typedef tuple<ll, ll, ll, ll> LT4;typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<vvl> v3l; typedef vector<v3l> v4l;typedef vector<v4l> v5l;typedef vector<LP> vlp; typedef vector<vlp> vvlp; typedef vector<string> vs; typedef vector<vs> vvs;typedef vector<ld> vd; typedef vector<vd> vvd; typedef vector<bool> vb;const int INF = numeric_limits<int>::max() / 2 - 1e6; const ll LINF = LLONG_MAX / 2 - 1e6; const double DINF = numeric_limits<double>::infinity();struct RandGen {using ud = uniform_int_distribution<ll>; mt19937 mt; RandGen() : mt(chrono::steady_clock::now().time_since_epoch().count()) {}ll l(ll a, ll b) { ud d(a, b - 1); return d(mt); }LP lp(ll a, ll b, bool rng = true) { ll x = l(a, b - 1), y = l(rng ? x + 1 : a, b - 1); return {x, y}; }vl vecl(ll l, ll a, ll b) { ud d(a, b - 1); vl ret(l); rep(i, l) ret[i] = d(mt); return ret; }vl vecperm(ll l, ll from = 0) { vl perm(l); iota(all(perm), from); shuffle(perm); return perm; }string str(ll l, string op) { vl fig = vecl(l, 0, op.size()); string s; rep(i, l) s.pb(op[fig[i]]); return s; }string straz(ll l, ll a = 0, ll z = 26) { vl az = vecl(l, a, z); string s; rep(i, l) s.pb('a' + az[i]); return s; }string strnum(ll l, ll zero = 0, ll ten = 10) { vl zt = vecl(l, zero, ten); string s; rep(i, l) s.pb('0' + zt[i]); return s; }void shuffle(vl &a) { std::shuffle(all(a), mt); }};template<typename T> void coutarray(vector<T>& v, int offset = 0, string sep = " ") { rep(i, v.size()) { if (i > 0) cout << sep; if (offset) cout <<v[i] + offset; else cout << v[i]; } cout << "\n"; }template<typename T> void coutmatrix(vector<vector<T>>& v, int offset = 0) { rep(i, v.size()) { coutarray(v[i], offset); } }template<typename T> void coutset(set<T> & s) { for (const auto& a : s) { cout << a << " "; } cout << "\n"; }template<typename K, typename V> void coutmap(map<K, V> & m) { for (const auto& kv : m) { cout << kv.first << ":" << kv.second << " "; } cout << "\n"; }template<typename T, typename S> void coutpair(pair<T, S> & p, string sep = " ") { cout << p.first << ":" << p.second << sep; }template<typename T> void coutbin(T &a, int d) { for (int i = d - 1; i >= 0; i--) cout << ((a >> i) & (T)1); cout << "\n"; }template<typename Q, typename A> void iquery(initializer_list<Q> q, A &a, string str = "? ") { cout << str; vector<Q> v(q); coutarray(v); cout.flush(); cin >> a; }// template<typename Q, typename A> void iquery(initializer_list<Q> q, A &a, string str = "? ") { vector<Q> query(q); RandGen rg;// a = query[0] ? A() : A();// }template<typename A> void ianswer(A a, string str = "! ") { cout << str << a << "\n"; cout.flush(); }int ceil_pow2(ll n) { int x = 0; while ((1ULL << x) < (unsigned long long)(n)) x++; return x; }int floor_pow2(ll n) { int x = 0; while ((1ULL << (x + 1)) <= (unsigned long long)(n)) x++; return x; }ll digits(ll n) { ll ret = 0; while(n > 0) { ret++; n /= 10; } return ret; }ll POW(ll x, int n) { assert(n >= 0); ll res = 1; for(; n; n >>= 1, x *= x) if(n & 1) res *= x; return res; }ll sqrt_ceil(ll x) { ll l = -1, r = x; while (r - l > 1) { ll m = (l + r) / 2; if (m * m >= x) r = m; else l = m; } return r; }template<typename T, typename S> T ceil(T x, S y) { assert(y); return (y < 0 ? ceil(-x, -y) : (x > 0 ? (x + y - 1) / y : x / y)); }template<typename T, typename S> T floor(T x, S y) { assert(y); return (y < 0 ? floor(-x, -y) : (x > 0 ? x / y : (x - y + 1) / y)); }template<typename T> void uniq(vector<T>&a){ sort(all(a)); a.erase(unique(all(a)), a.end()); }template<typename T> void comp(vector<T>&a){ vector<T> b = a; uniq(b); rep(i, a.size()) a[i] = lower_bound(all(b), a[i]) - b.begin(); }template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1;} return 0; }template<class T> bool chmax(T &a, const T &b) { if (b > a) { a = b; return 1;} return 0; }template<class T> int lbs(vector<T> &a, const T &b) { return lower_bound(all(a), b) - a.begin(); };template<class T> int ubs(vector<T> &a, const T &b) { return upper_bound(all(a), b) - a.begin(); };ll binary_search(function<bool(ll)> check, ll ok, ll ng) { assert(check(ok)); while (abs(ok - ng) > 1) { auto x = (ng + ok) / 2; if (check(x)) ok = x; else ng = x; } return ok; }template<class T> vector<T> csum(vector<T> &a) { vl ret(a.size() + 1, 0); rep(i, a.size()) ret[i + 1] = ret[i] + a[i]; return ret; }template<class S> vector<pair<S, int>> RLE(const vector<S> &v) { vector<pair<S, int>> res; for(auto &e : v) if(res.empty() or res.back().first != e)res.emplace_back(e, 1); else res.back().second++; return res; }vector<pair<char, int>> RLE(const string &v) { vector<pair<char, int>> res; for(auto &e : v) if(res.empty() or res.back().first != e) res.emplace_back(e, 1); else res.back().second++; return res; }const string drul = "DRUL"; vl dx = {1, 0, -1, 0}; vl dy = {0, 1, 0, -1};const ll 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.inv();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 inv() 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 mint = ModInt< mod >; typedef vector<mint> vmi; typedef vector<vmi> vvmi; typedef vector<vvmi> v3mi; typedef vector<v3mi> v4mi;//------------------------------------------------------------------------------const int max_n = 1 << 20;mint fact[max_n], factinv[max_n];void init_f() { fact[0] = 1; for (int i = 0; i < max_n - 1; i++) { fact[i + 1] = fact[i] * (i + 1); } factinv[max_n - 1] = mint(1) / fact[max_n - 1];for (int i = max_n - 2; i >= 0; i--) { factinv[i] = factinv[i + 1] * (i + 1); } }mint comb(int a, int b) { assert(fact[0] != 0); if (a < 0 || b < 0 || a < b) return 0; return fact[a] * factinv[b] * factinv[a - b]; }mint combP(int a, int b) { assert(fact[0] != 0); if (a < 0 || b < 0 || a < b) return 0; return fact[a] * factinv[a - b]; }//------------------------------------------------------------------------------ll mod_pow(ll x, ll n, const ll &p = mod) { ll ret = 1; while(n > 0) { if(n & 1) (ret *= x) %= p; (x *= x) %= p; n >>= 1; } return ret; }ll mod_inv(ll x, ll m) { ll a = x, b = m, u = 1, v = 0, t; while(b) { t = a / b; swap(a -= t * b, b); swap(u -= t * v, v); } if (u < 0) u += m;return u % m; }//------------------------------------------------------------------------------vl divisor(ll n) {vl ret; for (ll i = 1; i * i <= n; i++) { if (n % i == 0) { ret.pb(i); if (i * i != n) ret.pb(n / i); } }sort(all(ret)); return ret; }map<long long, long long> prime_factorize(long long N) {map<long long, long long> res;for (long long a = 2; a * a <= N; ++a) { if (N % a != 0) continue; long long ex = 0; while (N % a == 0) { ++ex; N /= a; } res[a]= ex; }if (N != 1) res[N] = 1; return res; }ll solve(ll N, vl a) {ll ans = -1; return ans;}ll naive(ll N, vl a) {ll ans = 1; return ans;}void compare(bool check = true) { RandGen rg; ll c = 0, loop = 10;while (++c) { if (c % loop == 0) cout << "reached " << c / loop << "loop" << "\n", cout.flush();ll N = 10;vl a = rg.vecl(N, 1, 1e2);auto s = solve(N, a); auto n = naive(N, a);if (!check || n != s) { cout << c << "times tried" << "\n";cout << N << "\n"; coutarray(a);cout << "solve: " << s << "\n";cout << "naive: " << n << "\n";if (check || (!check && c > loop)) break; }}}void solve() {ll l; cin >> l;mint ans = 1;rep(i, l) {ll p, n; cin >> p >> n;mint sum = mint(p).pow(n + 2) + mint(1 - p) * n + mint(1 - p * 2);sum = sum / (p - 1) / (p - 1);ans *= sum;}cout << ans << "\n";}signed main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr); cout << fixed << setprecision(15);int t = 1; // cin >> t;while (t--) solve();// while (t--) compare();}