QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#103227#2834. NonsenseLeasierTL 20ms64476kbC++144.2kb2023-05-04 20:19:392023-05-04 20:19:42

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-04 20:19:42]
  • 评测
  • 测评结果:TL
  • 用时:20ms
  • 内存:64476kb
  • [2023-05-04 20:19:39]
  • 提交

answer

#include <stdio.h>

typedef long long ll;

const int N = 2e5 + 7, M = 1e4, K = 5e3 + 1, mod = 998244353;
int a[N], b[N];
ll inv[M + 7], c[K + 7][K + 7], power[M + 7], val[M + 7], ans[K + 7][K + 7];

inline void init(){
	inv[0] = inv[1] = 1;
	for (register int i = 2; i <= M; i++){
		inv[i] = mod - (mod / i) * inv[mod % i] % mod;
	}
}

inline int max(int a, int b){
	return a > b ? a : b;
}

inline ll quick_pow(ll x, ll p, ll mod){
	ll ans = 1;
	while (p){
		if (p & 1) ans = ans * x % mod;
		x = x * x % mod;
		p >>= 1;
	}
	return ans;
}

int main(){
	int n, x, y, q;
	init();
	while (scanf("%d %d %d %d", &n, &x, &y, &q) != EOF){
		int maxa = 0, maxb = 0, maxab, sum;
		for (register int i = 1; i <= q; i++){
			scanf("%d %d", &a[i], &b[i]);
			maxa = max(maxa, a[i]);
			maxb = max(maxb, b[i]);
		}
		maxab = max(maxa, maxb);
		sum = maxa + maxb;
		for (register int i = 0; i <= maxab; i++){
			c[i][0] = 1;
			for (register int j = 1; j <= maxab; j++){
				c[i][j] = c[i][j - 1] * (n - i - j + 1) % mod * inv[j] % mod;
			}
		}
		if (x == 0){
			power[sum] = quick_pow(y, n - sum, mod);
			for (register int i = sum - 1; i >= 0; i--){
				power[i] = power[i + 1] * y % mod;
			}
			for (register int i = 0; i <= maxa; i++){
				for (register int j = 0; j <= maxb; j++){
					ans[i][j] = c[i][j] * power[i + j] % mod;
				}
			}
		} else if (y == 0){
			power[sum] = quick_pow(x, n - sum, mod);
			for (register int i = sum - 1; i >= 0; i--){
				power[i] = power[i + 1] * x % mod;
			}
			for (register int i = 0; i <= maxa; i++){
				for (register int j = 0; j <= maxb; j++){
					ans[i][j] = c[j][i] * power[i + j] % mod;
				}
			}
		} else {
			if (x == y){
				int sum_i = sum + 1;
				val[0] = 1;
				for (register int i = 1; i <= sum_i; i++){
					val[i] = val[i - 1] * (n - i + 2) % mod * inv[i] % mod;
				}
				power[sum] = quick_pow(x, n - sum, mod);
				for (register int i = sum - 1; i >= 0; i--){
					power[i] = power[i + 1] * x % mod;
				}
				for (register int i = 0; i <= maxa; i++){
					for (register int j = 0; j <= maxb; j++){
						ans[i][j] = val[i + j + 1] * power[i + j] % mod;
					}
				}
			} else {
				ll q = x * quick_pow(y, mod - 2, mod) % mod, invqd = quick_pow(q - 1, mod - 2, mod), r = quick_pow(q, mod - 2, mod), invrd = quick_pow(r - 1, mod - 2, mod), inv_val = quick_pow(((y - x) % mod + mod) % mod, mod - 2, mod);
				if (q == 1){
					ll temp = 1;
					for (register int i = 0; i <= maxa; i++){
						if (i > 0) temp = temp * (n - i + 1) % mod * inv[i + 1] % mod;
						ans[i][0] = temp * quick_pow(x, n - i, mod) % mod;
					}
				} else {
					ll full = quick_pow(y, n, mod);
					power[maxa] = quick_pow(q, n - maxa, mod);
					for (register int i = maxa - 1; i >= 0; i--){
						power[i] = power[i + 1] * q % mod;
					}
					for (register int i = 0; i <= maxa; i++){
						ll val = (quick_pow(q, n - i + 1, mod) - 1) * invqd % mod;
						for (register int j = 1; j <= i; j++){
							val = ((power[i - j] * c[i - j][j] % mod - val) * q % mod * invqd % mod + mod) % mod;
						}
						ans[i][0] = val * full % mod * quick_pow(x, mod - i - 1, mod) % mod;
					}
				}
				if (r == 1){
					ll temp = 1;
					for (register int i = 0; i <= maxb; i++){
						if (i > 0) temp = temp * (n - i + 1) % mod * inv[i + 1] % mod;
						ans[i][0] = temp * quick_pow(y, n - i, mod) % mod;
					}
				} else {
					ll full = quick_pow(x, n, mod);
					power[maxb] = quick_pow(r, n - maxb, mod);
					for (register int i = maxb - 1; i >= 0; i--){
						power[i] = power[i + 1] * r % mod;
					}
					for (register int i = 1; i <= maxb; i++){
						ll val = (quick_pow(r, n - i + 1, mod) - 1) * invrd % mod;
						for (register int j = 1; j <= i; j++){
							val = ((power[i - j] * c[i - j][j] % mod - val) * r % mod * invrd % mod + mod) % mod;
						}
						ans[0][i] = val * full % mod * quick_pow(y, mod - i - 1, mod) % mod;
					}
				}
				for (register int i = 1; i <= maxa; i++){
					for (register int j = 1; j <= maxb; j++){
						ans[i][j] = ((ans[i - 1][j] - ans[i][j - 1]) * inv_val % mod + mod) % mod;
					}
				}
			}
		}
		for (register int i = 1; i <= q; i++){
			printf("%lld\n", ans[a[i]][b[i]]);
		}
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 7696kb

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: 20ms
memory: 64476kb

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: -100
Time Limit Exceeded

input:

1000000000 998244351 998244352 1
5000 5000

output:


result: