QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#103213#2834. NonsenseLeasierWA 42ms28760kbC++143.3kb2023-05-04 19:36:092023-05-04 19:36:12

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 19:36:12]
  • 评测
  • 测评结果:WA
  • 用时:42ms
  • 内存:28760kb
  • [2023-05-04 19:36:09]
  • 提交

answer

#include <stdio.h>

typedef long long ll;

const int N = 2e5 + 7, M = 5e3 + 1, K = 1e4 + 7, mod = 998244353;
int a[N], b[N];
ll inv[M + 7], c[M + 7][M + 7], val[K], power[M + 7], ans[M + 7][M + 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;
			}
		}
		val[0] = 1;
		for (register int i = 1; i <= sum; i++){
			val[i] = val[i - 1] * (n - i + 1) % mod * inv[i] % mod;
		}
		if (x == y){
			for (register int i = 0; i <= maxa; i++){
				for (register int j = 0; j <= maxb; j++){
					ans[i][j] = val[i + j] * quick_pow(x, n - i - j, mod) % 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(((x - y) % 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 {
				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 * quick_pow(y, n, mod) % 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 {
				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 * quick_pow(x, n - i, mod) % 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][j - 1] - x * ans[i - 1][j] % mod) * inv_val % mod + mod) % mod;
				}
			}
		}
		for (register int i = 1; i <= q; i++){
			printf("%lld\n", ans[a[i]][b[i]]);
		}
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3628kb

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: 42ms
memory: 28760kb

input:

1000000000 0 1 1
1000 1000
2 0 0 1
1 1
2 998244352 998244352 1
1 1

output:

0
1
1

result:

wrong answer 1st lines differ - expected: '381781645', found: '0'