QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#22030#2834. NonsenseQingyuRE 162ms103520kbC++202.8kb2022-03-09 00:58:002022-04-30 00:41:54

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:54]
  • 评测
  • 测评结果:RE
  • 用时:162ms
  • 内存:103520kb
  • [2022-03-09 00:58:00]
  • 提交

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));
		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: 7ms
memory: 5512kb

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: 12ms
memory: 9576kb

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: 162ms
memory: 103520kb

input:

1000000000 998244351 998244352 1
5000 5000

output:

663228915

result:

ok single line: '663228915'

Test #4:

score: -100
Dangerous Syscalls

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:


result: