QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#618145#2834. NonsenseMilkcat2009TL 201ms107556kbC++144.2kb2024-10-06 19:09:252024-10-06 19:09:29

Judging History

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

  • [2024-10-06 19:09:29]
  • 评测
  • 测评结果:TL
  • 用时:201ms
  • 内存:107556kb
  • [2024-10-06 19:09:25]
  • 提交

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
...

result: