QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#618141 | #2834. Nonsense | Milkcat2009 | WA | 188ms | 106436kb | C++14 | 4.1kb | 2024-10-06 19:06:42 | 2024-10-06 19:06:42 |
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, 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] * px[a + b];
}
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: 3ms
memory: 12208kb
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: -100
Wrong Answer
time: 188ms
memory: 106436kb
input:
1000000000 0 1 1 1000 1000 2 0 0 1 1 1 2 998244352 998244352 1 1 1
output:
381781645 0998244352
result:
wrong answer 2nd lines differ - expected: '1', found: '0998244352'