QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#316727#8177. Sum is Integerucup-team008#WA 40ms8032kbC++208.4kb2024-01-28 02:41:182024-01-28 02:41:18

Judging History

你现在查看的是最新测评结果

  • [2024-01-28 02:41:18]
  • 评测
  • 测评结果:WA
  • 用时:40ms
  • 内存:8032kb
  • [2024-01-28 02:41:18]
  • 提交

answer

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

// BEGIN NO SAD
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
typedef vector<int> vi;
#define f first
#define s second
#define derr if(1) cerr

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << flush;
// END NO SAD

template<class Fun>
class y_combinator_result {
  Fun fun_;
public:
  template<class T>
  explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}

  template<class ...Args>
  decltype(auto) operator()(Args &&...args) {
    return fun_(std::ref(*this), std::forward<Args>(args)...);
  }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
  return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}

template<class T>
bool updmin(T& a, T b) {
  if(b < a) {
    a = b;
    return true;
  }
  return false;
}
template<class T>
bool updmax(T& a, T b) {
  if(b > a) {
    a = b;
    return true;
  }
  return false;
}
typedef int64_t ll;

struct barrett_reduction {
    unsigned mod;
    uint64_t div;
 
    barrett_reduction(unsigned m) : mod(m), div(-1LLU / m) {}
 
    unsigned operator()(uint64_t a) const {
#ifdef __SIZEOF_INT128__
        uint64_t q = uint64_t(__uint128_t(div) * a >> 64);
        uint64_t r = a - q * mod;
        return unsigned(r < mod ? r : r - mod);
#endif
        return unsigned(a % mod);
    }
};
 
template<const int &MOD, const barrett_reduction &barrett>
struct _b_int {
    int val;
 
    _b_int(int64_t v = 0) {
        if (v < 0) v = v % MOD + MOD;
        if (v >= MOD) v %= MOD;
        val = int(v);
    }
 
    _b_int(uint64_t v) {
        if (v >= uint64_t(MOD)) v %= MOD;
        val = int(v);
    }
 
    _b_int(int v) : _b_int(int64_t(v)) {}
    _b_int(unsigned v) : _b_int(uint64_t(v)) {}
 
    static int inv_mod(int a, int m = MOD) {
        // https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Example
        int g = m, r = a, x = 0, y = 1;
 
        while (r != 0) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        }
 
        return x < 0 ? x + m : x;
    }
 
    explicit operator int() const { return val; }
    explicit operator unsigned() const { return val; }
    explicit operator int64_t() const { return val; }
    explicit operator uint64_t() const { return val; }
    explicit operator double() const { return val; }
    explicit operator long double() const { return val; }
 
    _b_int& operator+=(const _b_int &other) {
        val -= MOD - other.val;
        if (val < 0) val += MOD;
        return *this;
    }
 
    _b_int& operator-=(const _b_int &other) {
        val -= other.val;
        if (val < 0) val += MOD;
        return *this;
    }
 
    static unsigned fast_mod(uint64_t x) {
#if !defined(_WIN32) || defined(_WIN64)
        return barrett(x);
#endif
        // Optimized mod for Codeforces 32-bit machines.
        // x must be less than 2^32 * MOD for this to work, so that x / MOD fits in an unsigned 32-bit int.
        unsigned x_high = unsigned(x >> 32), x_low = unsigned(x);
        unsigned quot, rem;
        asm("divl %4\n"
            : "=a" (quot), "=d" (rem)
            : "d" (x_high), "a" (x_low), "r" (MOD));
        return rem;
    }
 
    _b_int& operator*=(const _b_int &other) {
        val = fast_mod(uint64_t(val) * other.val);
        return *this;
    }
 
    _b_int& operator/=(const _b_int &other) {
        return *this *= other.inv();
    }
 
    friend _b_int operator+(const _b_int &a, const _b_int &b) { return _b_int(a) += b; }
    friend _b_int operator-(const _b_int &a, const _b_int &b) { return _b_int(a) -= b; }
    friend _b_int operator*(const _b_int &a, const _b_int &b) { return _b_int(a) *= b; }
    friend _b_int operator/(const _b_int &a, const _b_int &b) { return _b_int(a) /= b; }
 
    _b_int& operator++() {
        val = val == MOD - 1 ? 0 : val + 1;
        return *this;
    }
 
    _b_int& operator--() {
        val = val == 0 ? MOD - 1 : val - 1;
        return *this;
    }
 
    _b_int operator++(int) { _b_int before = *this; ++*this; return before; }
    _b_int operator--(int) { _b_int before = *this; --*this; return before; }
 
    _b_int operator-() const {
        return val == 0 ? 0 : MOD - val;
    }
 
    friend bool operator==(const _b_int &a, const _b_int &b) { return a.val == b.val; }
    friend bool operator!=(const _b_int &a, const _b_int &b) { return a.val != b.val; }
    friend bool operator<(const _b_int &a, const _b_int &b) { return a.val < b.val; }
    friend bool operator>(const _b_int &a, const _b_int &b) { return a.val > b.val; }
    friend bool operator<=(const _b_int &a, const _b_int &b) { return a.val <= b.val; }
    friend bool operator>=(const _b_int &a, const _b_int &b) { return a.val >= b.val; }
 
    _b_int inv() const {
        return inv_mod(val);
    }
 
    _b_int pow(int64_t p) const {
        if (p < 0)
            return inv().pow(-p);
 
        _b_int a = *this, result = 1;
 
        while (p > 0) {
            if (p & 1)
                result *= a;
 
            p >>= 1;
 
            if (p > 0)
                a *= a;
        }
 
        return result;
    }
 
    friend ostream& operator<<(ostream &os, const _b_int &m) {
        return os << m.val;
    }
 
    friend istream& operator>>(istream &is, _b_int &m) {
        int64_t x;
        is >> x;
        m = x;
        return is;
    }
};
 
int MOD1 = int(1e9) + 7;
barrett_reduction barrett1(MOD1);
using mnum1 = _b_int<MOD1, barrett1>;
int MOD2 = 998244353;
barrett_reduction barrett2(MOD2);
using mnum2 = _b_int<MOD2, barrett2>;

mt19937 g1(0x14004);
void solve() {
  int n;
  cin >> n;
  vector<int> p(n), q(n);
  for(int i = 0; i < n; i++) cin >> p[i] >> q[i];
  vector<long double> psum(n+1);
  psum[0] = uniform_real_distribution<double>(0, 1)(g1);
  for(int i = 1; i <= n; i++) {
    psum[i] = psum[i-1] + double(p[i-1]) / q[i-1];
  }
  map<array<int, 2>, int> dp;
  ll ret = 0;
  dp[{0, 0}] = 1;
  array<int, 2> curr = {0, 0};
  for(int i = 0; i < n; i++) {
    int lhs = (int)(mnum1(p[i]) / q[i]);
    int rhs = (int)(mnum2(p[i]) / q[i]);
    curr[0] += lhs; if(curr[0] >= MOD1) curr[0] -= MOD1;
    curr[1] += rhs; if(curr[1] >= MOD2) curr[1] -= MOD2;
    ll shift = ll(psum[i+1]) - ll(psum[i]);
    curr[0] -= shift; if(curr[0] < 0) curr[0] += MOD1;
    curr[1] -= shift; if(curr[1] < 0) curr[1] += MOD2;
    ret += dp[curr]++;
  }
  cout << ret << "\n";
}

// what would chika do
// are there edge cases (N=1?)
// are array sizes proper (scaled by proper constant, for example 2* for koosaga tree)
// integer overflow?
// DS reset properly between test cases
// are you doing geometry in floating points
// are you not using modint when you should

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3568kb

input:

4
1 6
1 3
1 2
1 2

output:

2

result:

ok "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3872kb

input:

5
1 1
2 2
3 3
4 4
5 5

output:

15

result:

ok "15"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

2
1 99999
99999 100000

output:

0

result:

ok "0"

Test #4:

score: -100
Wrong Answer
time: 40ms
memory: 8032kb

input:

200000
82781 82781
86223 86223
16528 16528
84056 84056
94249 94249
54553 54553
25943 25943
10415 10415
52417 52417
46641 46641
70298 70298
84228 84228
55441 55441
49326 49326
11753 11753
89499 89499
58220 58220
71482 71482
32373 32373
7251 7251
78573 78573
74268 74268
46682 46682
20314 20314
85519 8...

output:

19799405515

result:

wrong answer 1st words differ - expected: '10603308211', found: '19799405515'