QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#317207 | #8177. Sum is Integer | triple__a# | TL | 1753ms | 170768kb | C++20 | 10.3kb | 2024-01-28 17:51:02 | 2024-01-28 17:51:02 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7700kb
input:
4 1 6 1 3 1 2 1 2
output:
2
result:
ok "2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7796kb
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: 7756kb
input:
2 1 99999 99999 100000
output:
0
result:
ok "0"
Test #4:
score: 0
Accepted
time: 200ms
memory: 11808kb
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: 222ms
memory: 18852kb
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: 918ms
memory: 89032kb
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: 1753ms
memory: 170768kb
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...