QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#317209#8177. Sum is Integertriple__a#TL 1860ms170800kbC++2010.3kb2024-01-28 17:52:142024-01-28 17:52:14

Judging History

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

  • [2024-01-28 17:52:14]
  • 评测
  • 测评结果:TL
  • 用时:1860ms
  • 内存:170800kb
  • [2024-01-28 17:52:14]
  • 提交

answer

#pragma GCC optimize("trapv")
#include<bits/stdc++.h>
#define int long long
#define i128 __int128_t
using namespace std;

constexpr int P = 998244353;
using i64 = long long;
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, i64 b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x%P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = i64(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        i64 v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};
std::vector<int> rev;
std::vector<Z> roots{0, 1};
void dft(std::vector<Z> &a) {
    int n = a.size();
    if ((int)(rev.size()) != n) {
        int k = __builtin_ctz(n) - 1;
        rev.resize(n);
        for (int i = 0; i < n; i++) {
            rev[i] = rev[i >> 1] >> 1 | (i & 1) << k;
        }
    }
    
    for (int i = 0; i < n; i++) {
        if (rev[i] < i) {
            std::swap(a[i], a[rev[i]]);
        }
    }
    if ((int)(roots.size()) < n) {
        int k = __builtin_ctz(roots.size());
        roots.resize(n);
        while ((1 << k) < n) {
            Z e = power(Z(3), (P - 1) >> (k + 1));
            for (int i = 1 << (k - 1); i < (1 << k); i++) {
                roots[2 * i] = roots[i];
                roots[2 * i + 1] = roots[i] * e;
            }
            k++;
        }
    }
    for (int k = 1; k < n; k *= 2) {
        for (int i = 0; i < n; i += 2 * k) {
            for (int j = 0; j < k; j++) {
                Z u = a[i + j];
                Z v = a[i + j + k] * roots[k + j];
                a[i + j] = u + v;
                a[i + j + k] = u - v;
            }
        }
    }
}
void idft(std::vector<Z> &a) {
    int n = a.size();
    std::reverse(a.begin() + 1, a.end());
    dft(a);
    Z inv = (1 - P) / n;
    for (int i = 0; i < n; i++) {
        a[i] *= inv;
    }
}
struct Poly {
    std::vector<Z> a;
    Poly() {}
    explicit Poly(int size, std::function<Z(int)> f = [](int) { return 0; }) : a(size) {
        for (int i = 0; i < size; i++) {
            a[i] = f(i);
        }
    }
    Poly(const std::vector<Z> &a) : a(a) {}
    Poly(const std::initializer_list<Z> &a) : a(a) {}
    int size() const {
        return a.size();
    }
    void resize(int n) {
        a.resize(n);
    }
    Z operator[](int idx) const {
        if (idx < size()) {
            return a[idx];
        } else {
            return 0;
        }
    }
    Z &operator[](int idx) {
        return a[idx];
    }
    Poly mulxk(int k) const {
        auto b = a;
        b.insert(b.begin(), k, 0);
        return Poly(b);
    }
    Poly modxk(int k) const {
        k = std::min(k, size());
        return Poly(std::vector<Z>(a.begin(), a.begin() + k));
    }
    Poly divxk(int k) const {
        if (size() <= k) {
            return Poly();
        }
        return Poly(std::vector<Z>(a.begin() + k, a.end()));
    }
    friend Poly operator+(const Poly &a, const Poly &b) {
        std::vector<Z> res(std::max(a.size(), b.size()));
        for (int i = 0; i < (int)(res.size()); i++) {
            res[i] = a[i] + b[i];
        }
        return Poly(res);
    }
    friend Poly operator-(const Poly &a, const Poly &b) {
        std::vector<Z> res(std::max(a.size(), b.size()));
        for (int i = 0; i < (int)(res.size()); i++) {
            res[i] = a[i] - b[i];
        }
        return Poly(res);
    }
    friend Poly operator-(const Poly &a) {
        std::vector<Z> res(a.size());
        for (int i = 0; i < (int)(res.size()); i++) {
            res[i] = -a[i];
        }
        return Poly(res);
    }
    friend Poly operator*(Poly a, Poly b) {
        if (a.size() == 0 || b.size() == 0) {
            return Poly();
        }
        if (a.size() < b.size()) {
            std::swap(a, b);
        }
        if (b.size() < 128) {
            Poly c(a.size() + b.size() - 1);
            for (int i = 0; i < a.size(); i++) {
                for (int j = 0; j < b.size(); j++) {
                    c[i + j] += a[i] * b[j];
                }
            }
            return c;
        }
        int sz = 1, tot = a.size() + b.size() - 1;
        while (sz < tot) {
            sz *= 2;
        }
        a.a.resize(sz);
        b.a.resize(sz);
        dft(a.a);
        dft(b.a);
        for (int i = 0; i < sz; ++i) {
            a.a[i] = a[i] * b[i];
        }
        idft(a.a);
        a.resize(tot);
        return a;
    }
    friend Poly operator*(Z a, Poly b) {
        for (int i = 0; i < (int)(b.size()); i++) {
            b[i] *= a;
        }
        return b;
    }
    friend Poly operator*(Poly a, Z b) {
        for (int i = 0; i < (int)(a.size()); i++) {
            a[i] *= b;
        }
        return a;
    }
    Poly &operator+=(Poly b) {
        return (*this) = (*this) + b;
    }
    Poly &operator-=(Poly b) {
        return (*this) = (*this) - b;
    }
    Poly &operator*=(Poly b) {
        return (*this) = (*this) * b;
    }
    Poly deriv() const {
        if (a.empty()) {
            return Poly();
        }
        std::vector<Z> res(size() - 1);
        for (int i = 0; i < size() - 1; ++i) {
            res[i] = (i + 1) * a[i + 1];
        }
        return Poly(res);
    }
    Poly integr() const {
        std::vector<Z> res(size() + 1);
        for (int i = 0; i < size(); ++i) {
            res[i + 1] = a[i] / (i + 1);
        }
        return Poly(res);
    }
    Poly inv(int m) const {
        Poly x{a[0].inv()};
        int k = 1;
        while (k < m) {
            k *= 2;
            x = (x * (Poly{2} - modxk(k) * x)).modxk(k);
        }
        return x.modxk(m);
    }
    Poly log(int m) const {
        return (deriv() * inv(m)).integr().modxk(m);
    }
    Poly exp(int m) const {
        Poly x{1};
        int k = 1;
        while (k < m) {
            k *= 2;
            x = (x * (Poly{1} - x.log(k) + modxk(k))).modxk(k);
        }
        return x.modxk(m);
    }
    Poly pow(int k, int m) const {
        int i = 0;
        while (i < size() && a[i].val() == 0) {
            i++;
        }
        if (i == size() || 1LL * i * k >= m) {
            return Poly(std::vector<Z>(m));
        }
        Z v = a[i];
        auto f = divxk(i) * v.inv();
        return (f.log(m - i * k) * k).exp(m - i * k).mulxk(i * k) * power(v, k);
    }
    Poly sqrt(int m) const {
        Poly x{1};
        int k = 1;
        while (k < m) {
            k *= 2;
            x = (x + (modxk(k) * x.inv(k)).modxk(k)) * ((P + 1) / 2);
        }
        return x.modxk(m);
    }
    Poly mulT(Poly b) const {
        if (b.size() == 0) {
            return Poly();
        }
        int n = b.size();
        std::reverse(b.a.begin(), b.a.end());
        return ((*this) * b).divxk(n - 1);
    }
    std::vector<Z> eval(std::vector<Z> x) const {
        if (size() == 0) {
            return std::vector<Z>(x.size(), 0);
        }
        const int n = std::max((int)(x.size()), size());
        std::vector<Poly> q(4 * n);
        std::vector<Z> ans(x.size());
        x.resize(n);
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                q[p] = Poly{1, -x[l]};
            } else {
                int m = (l + r) / 2;
                build(2 * p, l, m);
                build(2 * p + 1, m, r);
                q[p] = q[2 * p] * q[2 * p + 1];
            }
        };
        build(1, 0, n);
        std::function<void(int, int, int, const Poly &)> work = [&](int p, int l, int r, const Poly &num) {
            if (r - l == 1) {
                if (l < (int)(ans.size())) {
                    ans[l] = num[0];
                }
            } else {
                int m = (l + r) / 2;
                work(2 * p, l, m, num.mulT(q[2 * p + 1]).modxk(m - l));
                work(2 * p + 1, m, r, num.mulT(q[2 * p]).modxk(r - m));
            }
        };
        work(1, 0, n, mulT(q[1].inv(n)));
        return ans;
    }
};


const int N=200008;
const int mod[]={8338451794508203, 2328785515178189};
const int INF=LLONG_MAX/4;
const int EPS=1e-6;
const int K=20;
mt19937 rng(1234);

int n;
int p[N],q[N];
int pref[2][N];
i128 modpow(i128 u,i128 v,int mod){
    i128 ans=1, t=u;
    while (v){
        if (v&1) ans=ans*t%mod;
        t=t*t%mod, v>>=1;
    }
    return ans;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;++i) cin>>p[i]>>q[i];
    for (int _=0;_<2;++_){
        for (int i=1;i<=n;++i) pref[_][i] = p[i]*modpow(q[i],mod[_]-2,mod[_])%mod[_];
        for (int i=1;i<=n;++i) pref[_][i] = (pref[_][i-1]+pref[_][i])%mod[_];
    }
    unordered_map<int,int> cnt;
    for (int i=0;i<=n;++i) cnt[pref[0][i]-pref[1][i]]++;
    int ans=0;
    for (int a=-1;a<=1;++a){
        for (int b=-1;b<=1;++b){
            for (auto [x,y]:cnt) ans+=y*cnt[x+a*mod[0]+b*mod[1]];
        }
    }
    ans-=n+1;
    cout<<ans/2;
}


详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7696kb

input:

4
1 6
1 3
1 2
1 2

output:

2

result:

ok "2"

Test #2:

score: 0
Accepted
time: 1ms
memory: 7692kb

input:

5
1 1
2 2
3 3
4 4
5 5

output:

15

result:

ok "15"

Test #3:

score: 0
Accepted
time: 1ms
memory: 7700kb

input:

2
1 99999
99999 100000

output:

0

result:

ok "0"

Test #4:

score: 0
Accepted
time: 201ms
memory: 12036kb

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:

10603308211

result:

ok "10603308211"

Test #5:

score: 0
Accepted
time: 226ms
memory: 18792kb

input:

200000
50741 50741
86798 95775
51104 51104
29372 29372
43295 43295
55065 55065
68947 68947
35282 35282
62467 62467
68481 68481
82613 82613
95921 95921
46302 46302
53806 53806
61244 61244
16078 16078
33476 33476
9084 9084
99273 99273
11678 11678
36816 36816
30311 30311
51479 51479
2667 2667
57043 570...

output:

20066919

result:

ok "20066919"

Test #6:

score: 0
Accepted
time: 1022ms
memory: 89020kb

input:

200000
98235 98235
67434 96040
49102 49102
16569 16569
1095 1095
23901 23901
6143 6143
78285 78285
9853 9853
46454 46454
52131 52131
72378 72378
53983 53983
91453 91453
38655 83910
6455 6455
80993 80993
66871 66871
45005 45005
72124 72124
17949 17949
34378 34378
81399 81399
89147 89147
72892 72892
8...

output:

1808373

result:

ok "1808373"

Test #7:

score: 0
Accepted
time: 1860ms
memory: 170800kb

input:

200000
64364 74993
65425 91573
10305 10305
31901 31901
90499 95090
13337 47707
32342 38531
75909 93251
95924 95924
12789 12789
77190 77190
82753 99616
33824 79787
48159 48159
32648 32648
90698 98365
89028 89028
36982 36982
11377 11377
79190 88165
23457 23457
24114 24114
55183 71128
65165 65165
4196 ...

output:

593601

result:

ok "593601"

Test #8:

score: -100
Time Limit Exceeded

input:

200000
42985 42985
30472 30472
4697 50160
91745 95118
77209 77209
32676 32676
96375 96550
18636 18636
93176 93202
27039 27039
2001 85497
74148 94045
82232 92935
71481 80579
99738 99977
90865 90865
93800 99894
11923 64394
29930 29930
40659 40659
12932 24625
47502 47502
34808 52414
37132 37132
78333 8...

output:


result: