QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#618131#2834. NonsenseMilkcat2009WA 1ms9800kbC++144.1kb2024-10-06 19:02:192024-10-06 19:02:19

Judging History

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

  • [2024-10-06 19:02:19]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:9800kb
  • [2024-10-06 19:02:19]
  • 提交

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, b; MI x, y, c[M], px[M], py[M], f[N][N];
	int main() {
		cin >> n >> x >> y >> q, m = min(n, 5000);
		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;
			px[i] = px[i - 1] / x;
			py[i] = py[i - 1] / y;
		}
		if (x.x == y.x) {
			REP(test, 1, q) {
				cin >> a >> b;
				cout << c[a + b + 1] * px[a + b];
			}
			return 0;
		}
		MI iv = (MI)1 / (x - y);
		REP(a, 0, m) REP(b, 0, m) {
			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(test, 1, q) {
			cin >> a >> b;
			cout << f[a][b] << '\n';
		}
		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: 0
Wrong Answer
time: 1ms
memory: 9800kb

input:

3 1 2 2
1 1
1 2
100 2 3 1
1 1

output:

6
1

result:

wrong answer 3rd lines differ - expected: '866021789', found: ''