QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#882967#9642. 冲刺hos_lyric#5 229ms121096kbC++145.6kb2025-02-05 14:04:182025-02-05 14:04:19

Judging History

This is the latest submission verdict.

  • [2025-02-05 14:04:19]
  • Judged
  • Verdict: 5
  • Time: 229ms
  • Memory: 121096kb
  • [2025-02-05 14:04:18]
  • Submitted

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
  static constexpr unsigned M = M_;
  unsigned x;
  constexpr ModInt() : x(0U) {}
  constexpr ModInt(unsigned x_) : x(x_ % M) {}
  constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
  constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
  constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
  ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
  ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
  ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
  ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
  ModInt pow(long long e) const {
    if (e < 0) return inv().pow(-e);
    ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
  }
  ModInt inv() const {
    unsigned a = M, b = x; int y = 0, z = 1;
    for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
    assert(a == 1U); return ModInt(y);
  }
  ModInt operator+() const { return *this; }
  ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
  ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
  ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
  ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
  ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
  template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
  template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
  template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
  template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
  explicit operator bool() const { return x; }
  bool operator==(const ModInt &a) const { return (x == a.x); }
  bool operator!=(const ModInt &a) const { return (x != a.x); }
  friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////

constexpr unsigned MO = 1004535809;
using Mint = ModInt<MO>;

constexpr int LIM_INV = 10'000'010;
Mint inv[LIM_INV], fac[LIM_INV], invFac[LIM_INV];

void prepare() {
  inv[1] = 1;
  for (int i = 2; i < LIM_INV; ++i) {
    inv[i] = -((Mint::M / i) * inv[Mint::M % i]);
  }
  fac[0] = invFac[0] = 1;
  for (int i = 1; i < LIM_INV; ++i) {
    fac[i] = fac[i - 1] * i;
    invFac[i] = invFac[i - 1] * inv[i];
  }
}
Mint binom(Int n, Int k) {
  if (n < 0) {
    if (k >= 0) {
      return ((k & 1) ? -1 : +1) * binom(-n + k - 1, k);
    } else if (n - k >= 0) {
      return (((n - k) & 1) ? -1 : +1) * binom(-k - 1, n - k);
    } else {
      return 0;
    }
  } else {
    if (0 <= k && k <= n) {
      assert(n < LIM_INV);
      return fac[n] * invFac[k] * invFac[n - k];
    } else {
      return 0;
    }
  }
}

////////////////////////////////////////////////////////////////////////////////


int N;
Mint P, Q;
vector<int> U, V;

// [z^m] ((1-P)z/(1-Pz))^(a+b-1) (1 + z/(1-Pz))
Mint brute(int u, int v) {
  if (u == 0 && v == 0) return 1;
  Mint ret = 0;
  for (int m = 0; ; ++m) {
    const int a = u - m, b = v - m;
    if (a+b <= 0) break;
    auto at = [&](int n) -> Mint {
      return (n >= a+b-1) ? (binom(n, a+b-1) * P.pow(n - (a+b-1))) : 0;
    };
    ret += binom(a+b, a) * Q.pow(a) * (1-Q).pow(b) * (1-P).pow(a+b-1) * (at(m) + (1-P) * at(m-1));
  }
  return ret;
}

int main() {
  prepare();
  
#ifdef LOCAL
P=Q=inv[2];
for(int u=0;u<=10;++u){
 for(int v=0;v<=10;++v){
  int q=1<<20;
  int p=(brute(u,v)*q).x;
  const int g=__gcd(p,q);p/=g;q/=g;
  cerr<<p<<"/"<<q<<" ";
 }
 cerr<<endl;
}
#endif
  
  for (; ~scanf("%d%u%u", &N, &P.x, &Q.x); ) {
    U.resize(N);
    V.resize(N);
    for (int n = 0; n < N; ++n) {
      scanf("%d%d", &U[n], &V[n]);
    }
    
    Mint ans = 0;
    for (int n = 0; n < N; ++n) ans += brute(U[n], V[n]);
    printf("%u\n", ans.x);
  }
  return 0;
}

詳細信息

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 221ms
memory: 121096kb

input:

4872 301135505 501969174
62 292
76 226
20 67
11 117
145 33
28 37
43 16
26 147
148 257
282 249
275 89
129 30
100 253
110 206
100 230
2 103
71 260
154 164
14 183
185 184
227 25
166 164
187 144
181 62
176 139
121 253
252 181
87 145
255 63
66 2
178 209
161 30
112 49
71 178
264 281
81 190
124 216
231 91
...

output:

354616342

result:

ok single line: '354616342'

Test #2:

score: 5
Accepted
time: 229ms
memory: 121096kb

input:

4868 135320924 895002559
284 240
284 300
259 42
233 262
209 165
50 294
80 300
300 110
288 4
6 145
65 55
3 167
6 160
120 150
104 280
227 253
105 33
203 262
294 263
295 187
91 255
300 99
188 86
294 90
230 117
96 33
86 255
192 260
86 180
197 13
71 0
65 300
201 21
97 253
168 157
292 64
293 72
41 189
24 ...

output:

871825364

result:

ok single line: '871825364'

Test #3:

score: 5
Accepted
time: 225ms
memory: 121052kb

input:

4859 596446395 415664961
2 2
151 224
107 217
257 82
260 287
63 174
115 93
185 58
58 75
142 289
11 164
149 248
217 186
124 290
70 257
233 107
149 195
213 128
283 258
194 80
110 284
30 173
228 11
296 134
67 85
229 255
127 39
168 257
282 90
52 290
182 114
259 248
236 133
273 81
226 174
51 153
175 58
27...

output:

536513995

result:

ok single line: '536513995'

Subtask #2:

score: 0
Time Limit Exceeded

Test #4:

score: 0
Time Limit Exceeded

input:

5000 732289608 658888527
232 5000
2921 5000
5000 3706
5000 4148
5000 2105
1771 5000
3970 5000
3729 5000
1614 5000
5000 151
5000 3553
5000 3405
5000 2869
5000 835
2673 5000
3238 5000
2853 5000
5000 999
5000 3
420 5000
5000 3025
5000 6
830 5000
723 5000
5000 851
5000 1210
1844 5000
5000 4389
2203 5000...

output:


result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #8:

score: 0
Time Limit Exceeded

input:

5000 0 454262500
3448016 3452435
2687053 2686221
8169887 8172208
9741693 9745191
2134360 2132632
2223989 2222297
6946537 6946296
2695577 2695329
1450857 1451876
8453241 8451200
9107846 9110910
8988968 8987572
9169892 9169540
7695546 7690794
5077074 5072683
7532989 7530319
7944119 7943232
2293369 229...

output:


result:


Subtask #4:

score: 0
Runtime Error

Test #12:

score: 0
Runtime Error

input:

5000 102882260 0
6819081 6816853
5149145 5145899
9892659 9895176
8631345 8627935
349191 353992
7035406 7036453
5912292 5916306
9657928 9662549
6200108 6198289
2101773 2106094
9309396 9307219
7369903 7374376
9787731 9790309
9108307 9103593
3772703 3768160
976239 977233
3825147 3825573
7626595 7626660...

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #16:

score: 0
Time Limit Exceeded

input:

4976 574513706 284978964
52150 52150
482959 482959
189922 189922
459237 459237
168102 168102
367208 367208
291040 291040
272705 272705
3179 3179
179983 179983
307014 307014
66641 66641
384965 384965
263794 263794
61297 61297
33430 33430
376221 376221
69803 69803
328604 328604
208254 208254
441178 44...

output:


result:


Subtask #6:

score: 0
Runtime Error

Test #19:

score: 0
Runtime Error

input:

5000 235325377 512694546
5854662 5854662
315229 315229
3137556 3137556
7608068 7608068
9583921 9583921
4958765 4958765
3109547 3109547
3431604 3431604
3400130 3400130
5073586 5073586
2742677 2742677
5111263 5111263
5485216 5485216
7602789 7602789
1522223 1522223
2264844 2264844
8283226 8283226
80915...

output:


result:


Subtask #7:

score: 0
Time Limit Exceeded

Test #22:

score: 0
Time Limit Exceeded

input:

5000 736097577 890228464
1825247 1825246
4650840 4650840
2234311 2234312
7343146 7343145
3787634 3787634
2656735 2656734
1463014 1463013
3322493 3322494
8952134 8952133
9554797 9554798
9938426 9938425
7324212 7324212
9852188 9852188
4135136 4135135
2970038 2970037
216167 216166
5330601 5330602
72371...

output:


result:


Subtask #8:

score: 0
Time Limit Exceeded

Test #25:

score: 0
Time Limit Exceeded

input:

5000 118468585 976109781
377801 381122
359413 364103
226131 224910
163598 165233
16964 20842
113098 111221
129456 130508
478339 478755
182926 179190
143979 142184
388264 390144
365026 366013
16759 19223
359155 361291
62049 57288
66890 63415
425143 423399
382820 384122
488899 485326
218034 220421
554...

output:


result:


Subtask #9:

score: 0
Time Limit Exceeded

Test #29:

score: 0
Time Limit Exceeded

input:

3000 177229351 510136745
179259 179695
2298716 2302777
4922758 4926164
3300268 3302823
1818638 1817659
4429564 4426586
3915685 3911287
2997695 2999804
459298 460850
52829 57660
4442042 4438650
1148083 1150580
4093935 4089443
2032081 2031185
1910400 1912395
3852021 3853590
1073219 1068243
1986701 198...

output:


result:


Subtask #10:

score: 0
Runtime Error

Test #33:

score: 0
Runtime Error

input:

5000 73170491 768796521
670558 670089
2958025 2960803
5414101 5416526
4699271 4699813
4561016 4565915
7035233 7030323
1378672 1378584
4964463 4966800
7242131 7240789
8247079 8245607
9279015 9283822
6727462 6723335
438898 443570
8300373 8299256
6811203 6810475
3356946 3358886
3697156 3698634
2948112 ...

output:


result: