QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#22031#2834. NonsenseQingyuRE 176ms103696kbC++202.8kb2022-03-09 01:01:582022-04-30 00:41:58

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 00:41:58]
  • 评测
  • 测评结果:RE
  • 用时:176ms
  • 内存:103696kb
  • [2022-03-09 01:01:58]
  • 提交

answer

#include <bits/stdc++.h>

const int mod = 998244353;

inline int inc(int x, int y) { x += y - mod; return x + (x >> 31 & mod); }
inline int dec(int x, int y) { x -= y; return x + (x >> 31 & mod); }
inline int mul(int x, int y) { return 1ll * x * y % mod; }
inline void upd(int &x, int y) { x = inc(x, y); }
inline void dpu(int &x, int y) { x = dec(x, y); }
inline void pud(int &x, int y) { x = mul(x, y); }
inline int fastpow(int x, int p) {
	int r = 1;
	while (p) {
		if (p & 1) r = mul(r, x);
		x = mul(x, x);
		p >>= 1;
	}
	return r;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	int n, x, y, q;
	const int lim = 2e5 + 50;
	std::vector<int> inv(lim), fact(lim), factinv(lim);
	fact[0] = 1;
	for (int i = 1; i < lim; ++i)
		fact[i] = mul(i, fact[i - 1]);
	factinv[lim - 1] = fastpow(fact[lim - 1], mod - 2);
	for (int i = lim - 2; i >= 0; --i) {
		factinv[i] = mul(i + 1, factinv[i + 1]);
	}
	for (int i = 1; i < lim; ++i) {
		assert(mul(fact[i], factinv[i]) == 1);
	}
	for (int i = 1; i < lim; ++i)
		inv[i] = mul(factinv[i], fact[i - 1]);
	auto comb = [&](int n, int m) {
		if (n < m) return 0;
		return mul(mul(fact[n], factinv[m]), factinv[n - m]);
	};
	while (std::cin >> n >> x >> y >> q) {
		if (std::cin.eof()) break;
		std::vector<int> a(q), b(q);
		int mx = 0, prod = 1;
		for (int i = 0; i < q; ++i) {
			std::cin >> a[i] >> b[i];
		}
		mx = std::max(*std::max_element(a.begin(), a.end()), *std::max_element(b.begin(), b.end())) + 1;
		std::vector<std::vector<int>> f(mx + 1, std::vector<int>(mx + 1));
		std::vector<int> binom(2 * mx + 1);
		// C(n + 1, i)
		binom[0] = 1;
		for (int i = 1; i <= 2 * mx; ++i) {
			binom[i] = mul(binom[i - 1], mul(inv[i], n + 2 - i));
		}
		if (x == y) {
			std::vector<int> power(lim);
			power[0] = 1;
			for (int i = 0; i < q; ++i) {
				int z = binom[a[i] + b[i] + 1];
				std::cout << mul(z, fastpow(x, n - a[i] - b[i])) << '\n';
			}	
		}
		else {
			f[0][0] = fastpow(inc(x, y), n);
			int d = (x > y) ? inv[x - y] : mod - inv[y - x];
			std::vector<int> pa(mx), pb(mx);
			for (int i = 0; i < mx; ++i) {
				pa[i] = fastpow(x, n + 1 - i);
				pb[i] = fastpow(y, n + 1 - i);
			}
			f[0][0] = mul(d, dec(pa[0], pb[0]));
			for (int i = 1; i < mx; ++i) {
				int A = 0;
				int B = mul(binom[i], pb[i]);
				f[0][i] = dec(A, B);
				A = mul(binom[i], pa[i]);
				B = 0;
				f[i][0] = dec(A, B);
			}
			for (int i = 1; i < mx; ++i) {
				upd(f[0][i], f[0][i - 1]);
				pud(f[0][i], d);
				dpu(f[i][0], f[i - 1][0]);
				pud(f[i][0], d);
			}
			for (int i = 1; i <= mx; ++i)
				for (int j = 1; j <= mx; ++j) {
					dpu(f[i][j], f[i - 1][j]);
					upd(f[i][j], f[i][j - 1]);
					pud(f[i][j], d);
				}
			for (int i = 0; i < q; ++i) {
				std::cout << f[a[i]][b[i]] << '\n';
			}
		}
	}
}

详细

Test #1:

score: 100
Accepted
time: 6ms
memory: 5448kb

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: 8ms
memory: 9484kb

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: 176ms
memory: 103696kb

input:

1000000000 998244351 998244352 1
5000 5000

output:

663228915

result:

ok single line: '663228915'

Test #4:

score: 0
Accepted
time: 50ms
memory: 6460kb

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:

ok 200000 lines

Test #5:

score: 0
Accepted
time: 30ms
memory: 6392kb

input:

405229773 25 79 200
3 3
5 5
5 5
1 5
2 4
2 4
3 1
3 3
5 4
1 5
2 1
3 1
4 1
2 5
1 4
4 4
4 1
5 5
5 3
2 2
1 1
2 1
4 2
4 4
2 3
5 1
4 3
2 3
3 4
4 3
2 2
3 3
1 4
5 3
2 2
3 1
1 1
3 3
3 5
1 3
5 2
1 1
1 4
5 5
5 5
4 1
2 5
2 5
1 4
1 1
3 3
5 4
1 2
1 1
2 5
4 3
5 4
3 3
5 2
3 3
4 1
2 3
2 5
1 3
4 3
4 4
4 2
5 1
2 5
3 5
...

output:

52820293
692687559
692687559
899722361
150221007
150221007
570819646
52820293
9962865
899722361
594892845
570819646
90708097
161767707
25275214
680941576
90708097
692687559
142946866
827907378
868929596
594892845
73037078
680941576
897540013
658419918
202971687
897540013
38775730
202971687
827907378...

result:

ok 200000 lines

Test #6:

score: -100
Runtime Error

input:

205514256 631068448 638301474 200
2 5
2 4
1 4
1 5
4 2
1 5
4 2
1 2
5 4
3 2
3 5
4 3
2 4
4 5
3 2
5 5
1 1
3 2
3 2
5 2
4 2
4 3
4 2
3 5
2 4
5 1
2 1
2 3
3 1
5 1
3 1
1 3
2 5
5 4
4 5
2 1
5 4
5 1
2 3
5 3
5 2
1 2
2 2
5 2
2 4
1 1
3 1
1 3
4 4
2 3
1 2
2 4
1 1
1 5
3 5
2 2
2 2
1 5
2 5
5 2
2 5
3 1
1 3
5 1
5 3
2 3
3 ...

output:


result: