QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#618150#2834. NonsenseMilkcat2009WA 151ms107492kbC++144.2kb2024-10-06 19:11:442024-10-06 19:11:45

Judging History

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

  • [2024-10-06 19:11:45]
  • 评测
  • 测评结果:WA
  • 用时:151ms
  • 内存:107492kb
  • [2024-10-06 19:11:44]
  • 提交

answer

#include <bits/stdc++.h>
#define REP(i, l, r) for (int i = (l); i <= (r); ++ i)
#define DEP(i, r, l) for (int i = (r); i >= (l); -- i)
#define fi first
#define se second
#define pb emplace_back
#define mems(x, v) memset((x), (v), sizeof(x))
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
using namespace std;
namespace Math {
	template <typename T> T qpow(T b, long long k) { if (!k) return T(1); T r = b; k --; for (; k; b = b * b, k >>= 1) if (k & 1) r = r * b; return r; }
	template <int P = 0> struct Mint {
		typedef long long LL;
		static int Mod; int x;
		constexpr static int getMod() { return P > 0 ? P : Mod; }  
		constexpr static void setMod(int Mod_) { Mod = Mod_; }
		#define mod getMod()
		constexpr Mint(int x_ = 0) : x(normal(x_)) {}
		constexpr Mint(LL x_) : x(normal(x_ % mod)) {}
		constexpr int normal(int x) const { if (x >= mod) x -= mod; if (x < 0) x += mod; return x; }
		explicit constexpr operator int() const { return x; }
		constexpr static int Qpow(int x, int k) { int r = 1; for (; k; x = 1LL * x * x % mod, k >>= 1) if (k & 1) r = 1LL * r * x % mod; return r; }
		constexpr Mint inv() const { assert(x != 0); return Mint(Qpow(x, mod - 2)); }
		constexpr Mint operator - () const { return Mint(mod - x); }
		constexpr Mint& operator += (const Mint &rhs) & { x = normal(x + rhs.x); return *this; }
		constexpr Mint& operator -= (const Mint &rhs) & { x = normal(x - rhs.x); return *this; }
		constexpr Mint& operator *= (const Mint &rhs) & { x = 1LL * x * rhs.x % mod; return *this; }
		constexpr Mint& operator /= (const Mint &rhs) & { return *this *= rhs.inv(); }
		friend constexpr Mint operator + (const Mint &lhs, const Mint &rhs) { Mint res = lhs; res += rhs; return res; }
		friend constexpr Mint operator - (const Mint &lhs, const Mint &rhs) { Mint res = lhs; res -= rhs; return res; }
		friend constexpr Mint operator * (const Mint &lhs, const Mint &rhs) { Mint res = lhs; res *= rhs; return res; }
		friend constexpr Mint operator / (const Mint &lhs, const Mint &rhs) { Mint res = lhs; res /= rhs; return res; }
		friend constexpr istream &operator >> (istream &is, Mint &a) { LL v; is >> v; a = Mint(v); return is; }
		friend constexpr ostream &operator << (ostream &os, const Mint &a) { return os << a.x; }
		#undef mod
	};
	using DMint = Mint<0>;
	template <> int DMint::Mod = 998244353;
	typedef long long LL;
	template <typename MI>
	struct Comb {
		#define mod MI::getMod()
		vector<MI> fac, inv, Finv;
		void init(int n) {
			fac.resize(n + 1), inv.resize(n + 1), Finv.resize(n + 1); 
			inv[1] = 1, fac[0] = Finv[0] = 1;
			for (int i = 2; i <= n; i ++)
				inv[i] =  inv[mod % i] * (mod - mod / i);
			for (int i = 1; i <= n; i ++)
				fac[i] = fac[i - 1] * i, Finv[i] = Finv[i - 1] * inv[i];
		}
		MI operator () (LL n, LL m) {
			if (m > n || m < 0 || n < 0) return 0;
			if (n < mod && m < mod) return fac[n] * Finv[m] * Finv[n - m];
			return n ? (*this)(n / mod, m / mod) * (*this)(n % mod, m % mod) : 1;
		}
		#undef mod
	};
}
namespace Milkcat {
	using namespace Math;
	typedef long long LL;
	typedef pair<LL, LL> pii;
	const int N = 5005, M = 1e6 + 5, mod = 998244353;
	typedef Mint<mod> MI;
	int n, m, q, A[N], B[N]; MI x, y, c[M], px[M], py[M], f[N][N];
	void solve() {
		m = 0;
		REP(i, 1, q)
			cin >> A[i] >> B[i], m = max({m, A[i] + 1, B[i] + 1});
		c[0] = 1, px[0] = qpow(x, n + 1), py[0] = qpow(y, n + 1);
		REP(i, 1, m * 2) {
			c[i] = c[i - 1] * (n - i + 2) / i;
			if (x.x > 0) px[i] = px[i - 1] / x;
			if (y.x > 0) py[i] = py[i - 1] / y;
		}
		if (x.x == y.x) {
			REP(i, 1, q) {
				int a = A[i], b = B[i];
				cout << c[a + b + 1] * (a + b < n ? px[a + b] : 1) << '\n';
			}
			return;
		}
		MI iv = (MI)1 / (x - y);
		REP(a, 0, m) REP(b, 0, m) {
			f[a][b] = 0;
			f[a][b] += (b > 0 ? f[a][b - 1] : c[a] * px[a]);
			f[a][b] -= (a > 0 ? f[a - 1][b] : c[b] * py[b]);
			f[a][b] *= iv;
		}
		REP(i, 1, q) {
			int a = A[i], b = B[i];
			cout << f[a][b] << '\n';
		}
	}
	int main() {
		while (cin >> n >> x >> y >> q)
			solve();
		return 0;
	}
}
int main() {
	// freopen("count.in", "r", stdin);
	// freopen("count.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T = 1;
	while (T --) Milkcat::main();
	return 0;
}

详细

Test #1:

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

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

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: 151ms
memory: 107492kb

input:

1000000000 998244351 998244352 1
5000 5000

output:

663228915

result:

ok single line: '663228915'

Test #4:

score: -100
Wrong Answer
time: 22ms
memory: 9812kb

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:

wrong answer 601st lines differ - expected: '693360471', found: '555662003'