QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#617396#2834. NonsenseYuJiaheWA 128ms99468kbC++231.5kb2024-10-06 15:21:132024-10-06 15:21:14

Judging History

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

  • [2024-10-06 15:21:14]
  • 评测
  • 测评结果:WA
  • 用时:128ms
  • 内存:99468kb
  • [2024-10-06 15:21:13]
  • 提交

answer

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#define mod 998244353
using namespace std;
const int N = 5005, M = N << 1;
int n, q, X, Y, iv, inv[M], g[M], Fx[M], Fy[M], f[N][N];
inline void add(int& x, int y){x += y;if (x >= mod) x -= mod;}
inline void mul(int& x, int y){x = 1ll * x * y % mod;}
inline int qpow(int bse, int p){int ans = 1;for (;p;p >>= 1, mul(bse, bse)) if (p & 1) mul(ans, bse);return ans;}
inline int F(int a, int b){if (a == -1) return Fy[b];if (b == -1) return Fx[a];return f[a][b];}
int main(){inv[1] = 1;
	for (int i = 2;i <= M - 9;i ++)
	inv[i] = 1ll * inv[mod % i] * (mod - mod / i) % mod;
	while (~scanf("%d%d%d%d", &n, &X, &Y, &q)){
		if (X == Y){g[0] = (n + 1ll) * qpow(X, n) % mod, X = qpow(X, mod - 2);
			for (int i = 1;i <= M - 10 && i <= n;i ++)
			mul(g[i] = g[i - 1], n - i + 1), mul(g[i], inv[i + 1]), mul(g[i], X);
			for (int a, b;q --;) scanf("%d%d", &a, &b), printf("%d\n", g[a + b]);continue;
		}iv = qpow((X - Y + mod) % mod, mod - 2);
		Fx[0] = qpow(X, n + 1), Fy[0] = qpow(Y, n + 1), X = qpow(X, mod - 2), Y = qpow(Y, mod - 2);
		for (int i = 1;i <= N - 5 && i <= n;i ++)
		mul(Fx[i] = Fx[i - 1], X), mul(Fx[i], n - i + 2), mul(Fx[i], inv[i]),
		mul(Fy[i] = Fy[i - 1], Y), mul(Fy[i], n - i + 2), mul(Fy[i], inv[i]);
		for (int a = 0;a <= n && a <= N - 5;a ++)
		for (int b = 0;b <= n && b <= N - 5;b ++)
		add(f[a][b] = F(a, b - 1), mod - F(a - 1, b)), mul(f[a][b], iv);
		for (int a, b;q --;) scanf("%d%d", &a, &b), printf("%d\n", F(a, b));
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3992kb

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: 128ms
memory: 99468kb

input:

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

output:

381781645
0
1

result:

wrong answer 2nd lines differ - expected: '1', found: '0'