QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#618145 | #2834. Nonsense | Milkcat2009 | TL | 201ms | 107556kb | C++14 | 4.2kb | 2024-10-06 19:09:25 | 2024-10-06 19:09:29 |
Judging History
answer
#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
using namespace std;
namespace Math {
template <typename T> T qpow(T b, long long k) { if (!k) return T(1); T r = b; k --; for (; k; b = b * b, k >>= 1) if (k & 1) r = r * b; return r; }
template <int P = 0> struct Mint {
typedef long long LL;
static int Mod; int x;
constexpr static int getMod() { return P > 0 ? P : Mod; }
constexpr static void setMod(int Mod_) { Mod = Mod_; }
#define mod getMod()
constexpr Mint(int x_ = 0) : x(normal(x_)) {}
constexpr Mint(LL x_) : x(normal(x_ % mod)) {}
constexpr int normal(int x) const { if (x >= mod) x -= mod; if (x < 0) x += mod; return x; }
explicit constexpr operator int() const { return x; }
constexpr static int Qpow(int x, int k) { int r = 1; for (; k; x = 1LL * x * x % mod, k >>= 1) if (k & 1) r = 1LL * r * x % mod; return r; }
constexpr Mint inv() const { assert(x != 0); return Mint(Qpow(x, mod - 2)); }
constexpr Mint operator - () const { return Mint(mod - x); }
constexpr Mint& operator += (const Mint &rhs) & { x = normal(x + rhs.x); return *this; }
constexpr Mint& operator -= (const Mint &rhs) & { x = normal(x - rhs.x); return *this; }
constexpr Mint& operator *= (const Mint &rhs) & { x = 1LL * x * rhs.x % mod; return *this; }
constexpr Mint& operator /= (const Mint &rhs) & { return *this *= rhs.inv(); }
friend constexpr Mint operator + (const Mint &lhs, const Mint &rhs) { Mint res = lhs; res += rhs; return res; }
friend constexpr Mint operator - (const Mint &lhs, const Mint &rhs) { Mint res = lhs; res -= rhs; return res; }
friend constexpr Mint operator * (const Mint &lhs, const Mint &rhs) { Mint res = lhs; res *= rhs; return res; }
friend constexpr Mint operator / (const Mint &lhs, const Mint &rhs) { Mint res = lhs; res /= rhs; return res; }
friend constexpr istream &operator >> (istream &is, Mint &a) { LL v; is >> v; a = Mint(v); return is; }
friend constexpr ostream &operator << (ostream &os, const Mint &a) { return os << a.x; }
#undef mod
};
using DMint = Mint<0>;
template <> int DMint::Mod = 998244353;
typedef long long LL;
template <typename MI>
struct Comb {
#define mod MI::getMod()
vector<MI> fac, inv, Finv;
void init(int n) {
fac.resize(n + 1), inv.resize(n + 1), Finv.resize(n + 1);
inv[1] = 1, fac[0] = Finv[0] = 1;
for (int i = 2; i <= n; i ++)
inv[i] = inv[mod % i] * (mod - mod / i);
for (int i = 1; i <= n; i ++)
fac[i] = fac[i - 1] * i, Finv[i] = Finv[i - 1] * inv[i];
}
MI operator () (LL n, LL m) {
if (m > n || m < 0 || n < 0) return 0;
if (n < mod && m < mod) return fac[n] * Finv[m] * Finv[n - m];
return n ? (*this)(n / mod, m / mod) * (*this)(n % mod, m % mod) : 1;
}
#undef mod
};
}
namespace Milkcat {
using namespace Math;
typedef long long LL;
typedef pair<LL, LL> pii;
const int N = 5005, M = 1e6 + 5, mod = 998244353;
typedef Mint<mod> MI;
int n, m, q, a, b; MI x, y, c[M], px[M], py[M], f[N][N];
void solve() {
m = min(n + 1, 5000);
c[0] = 1, px[0] = qpow(x, n + 1), py[0] = qpow(y, n + 1);
REP(i, 1, m * 2) {
c[i] = c[i - 1] * (n - i + 2) / i;
if (x.x > 0) px[i] = px[i - 1] / x;
if (y.x > 0) py[i] = py[i - 1] / y;
}
if (x.x == y.x) {
REP(test, 1, q) {
cin >> a >> b;
cout << c[a + b + 1] * (a + b < n ? px[a + b] : 1) << '\n';
}
return;
}
MI iv = (MI)1 / (x - y);
REP(a, 0, m) REP(b, 0, m) {
f[a][b] = 0;
f[a][b] += (b > 0 ? f[a][b - 1] : c[a] * px[a]);
f[a][b] -= (a > 0 ? f[a - 1][b] : c[b] * py[b]);
f[a][b] *= iv;
}
REP(test, 1, q) {
cin >> a >> b;
cout << f[a][b] << '\n';
}
}
int main() {
while (cin >> n >> x >> y >> q)
solve();
return 0;
}
}
int main() {
// freopen("count.in", "r", stdin);
// freopen("count.out", "w", stdout);
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
while (T --) Milkcat::main();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 12004kb
input:
3 1 2 2 1 1 1 2 100 2 3 1 1 1
output:
6 1 866021789
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 201ms
memory: 107556kb
input:
1000000000 0 1 1 1000 1000 2 0 0 1 1 1 2 998244352 998244352 1 1 1
output:
381781645 1 1
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 144ms
memory: 107156kb
input:
1000000000 998244351 998244352 1 5000 5000
output:
663228915
result:
ok single line: '663228915'
Test #4:
score: -100
Time Limit Exceeded
input:
105886041 9 3 200 4 3 5 1 1 1 4 1 3 3 1 5 2 1 1 5 2 1 1 5 3 3 4 4 2 1 4 4 1 2 5 2 5 2 2 5 4 5 3 3 4 3 1 4 3 1 5 4 5 3 5 2 5 3 3 3 1 3 4 3 2 3 3 5 1 3 3 5 2 3 4 4 3 4 5 5 2 3 1 1 3 3 4 2 1 4 4 5 2 3 1 5 2 2 4 2 5 5 2 1 4 3 3 3 3 1 2 1 2 5 1 1 4 4 1 5 1 5 3 1 3 2 2 2 4 1 5 5 3 4 2 2 2 1 5 3 5 3 2 2 1 ...
output:
721440251 764408668 442427888 914530150 115811774 360614503 666106268 360614503 666106268 360614503 115811774 166867820 666106268 166867820 985976063 717651702 717651702 405340273 435048189 115811774 721440251 719754512 660548079 998056822 165742634 717651702 165742634 115811774 407319461 721440251 ...