QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#715300#9476. 012 GriddefinierenAC ✓350ms25960kbC++1413.8kb2024-11-06 11:23:302024-11-06 11:23:31

Judging History

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

  • [2024-11-06 11:23:31]
  • 评测
  • 测评结果:AC
  • 用时:350ms
  • 内存:25960kb
  • [2024-11-06 11:23:30]
  • 提交

answer

#include <bits/stdc++.h>

#define fir first
#define sec second
#ifdef LOCAL
#define dbg(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << '\n'
#define dpi(x, y) cerr << "In Line " << __LINE__ << " the " << #x << " = " << x << " ; " << "the " << #y << " = " << y << '\n'
#define dbgf(fmt, args...) fprintf(stderr, fmt, ##args)
#define dbgf(fmt, args...) fprintf(stderr, fmt, ##args)
#else
#define dbg(x) void()
#define dpi(x, y) void()
#define dbgf(fmt, args...) void()
#endif

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
using ldb = long double;
using i128 = __int128_t;
using ui128 = __uint128_t;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vpii = vector<pii>;

bool Mbe;
constexpr int MOD = 998244353;
template<typename T> T Norm(T a, T p = MOD) { return (a % p + p) % p; }
template<typename T> T add(T a, T b, T p = MOD) { return (a + b >= p) ? (a + b - p) : (a + b); }
template<typename T> T del(T a, T b, T p = MOD) { return (a - b < 0) ? (a - b + p) : (a - b); }
template<typename T> T mul(T a, T b, T p = MOD) { return 1ll * a * b % p; }
template<typename T> T cadd(T &a, T b, T p = MOD) { return a = add(a, b, p); }
template<typename T> T cdel(T &a, T b, T p = MOD) { return a = del(a, b, p); }
template<typename T> T cmul(T &a, T b, T p = MOD) { return a = mul(a, b, p); }
template<typename T> bool cmax(T &a, T b) { return a < b ? a = b, true : false; }
template<typename T> bool cmin(T &a, T b) { return a > b ? a = b, true : false; }
template<typename T> T DivFloor(T a, T b) { return a >= 0 ? a / b : (a - b + 1) / b; }
template<typename T> T DivCeil(T a, T b) { return a >= 0 ? (a + b - 1) / b : a / b; }

namespace FastIO {
	constexpr int LEN = 1 << 20;
	char in[LEN + 1], out[LEN + 1];
	char *pin = in, *pout = out, *ein = in, *eout = out + LEN;

	char gc() { return pin == ein && (ein = (pin = in) + fread(in, 1, LEN, stdin), ein == in) ? EOF : *pin ++; }
	void pc(char c) { pout == eout && (fwrite(out, 1, LEN, stdout), pout = out); (*pout ++) = c; return; }
	struct Flush { ~Flush() { fwrite(out, 1, pout - out, stdout); pout = out; return; } } _flush;

	template<typename T> T Read() {
		T x = 0; int f = 1; char ch = gc();
		while (ch < '0' || ch > '9') f = (ch == '-' ? (~f + 1) : f), ch = gc();
		while (ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = gc();
		return x * f;
	}
	void Read(char *s) {
		char ch = gc();
		while (ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t') ch = gc();
		while ((ch != EOF) && !(ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t')) *s = ch, s ++, ch = gc();
		*s = '\0'; return;
	}
	template<typename T> void Read(T &x) { x = Read<T>(); return; }
	template<typename T, typename ...Args>
	void Read(T &x, Args &...args) { Read(x), Read(args...); return; }
	template<typename T> void Write(T x) {
		static char stk[40]; int tp = 0;
		if (x < 0) pc('-'), x = ~x + 1;
		do stk[tp++] = x % 10 + 48, x /= 10; while (x);
		while (tp --) pc(stk[tp]);
		return;
	}
	void Write(char ch) { pc(ch); return; }
	void Write(const char *s) {
		while (*s != '\0') pc(*s), s ++;
		return;
	}
	void Puts(const char *s) {
		Write(s), pc('\n'); return;
	}
	template<typename T, typename ...Args>
	void Write(T x, Args ...args) { Write(x), Write(args...); return; }
}
using FastIO::Read;
using FastIO::Write;
using FastIO::Puts;

#define getchar FastIO::gc
#define putchar FastIO::pc

template<int P>
struct Modint {
	int x; static int Mod;
	constexpr Modint(): x(0) { return; }
	constexpr Modint(ll _x): x(norm(_x % GetMod())) { return; }
	constexpr static int GetMod() { return P ? P : Mod; }
	constexpr static void SetMod(int _Mo) { Mod = _Mo; return; }
	explicit constexpr operator int() const { return x; }
	operator bool() const { return x; }
	Modint inv() const { return (*this) ^ (GetMod() - 2); }
	constexpr int norm(int x) const { if (x < 0) x += GetMod(); if (x >= GetMod()) x -= GetMod(); return x; }
	friend Modint operator - (Modint x) { x.x = x.norm(GetMod() - x.x); return x; }
	Modint &operator += (const Modint &oth) { x = norm(x + oth.x); return *this; }
	Modint &operator -= (const Modint &oth) { x = norm(x - oth.x); return *this; }
	Modint &operator *= (const Modint &oth) { x = 1ll * x * oth.x % GetMod(); return *this; }
	Modint &operator /= (const Modint &oth) { x = 1ll * x * oth.inv().x % GetMod(); return *this; }
	Modint &operator ^= (const ll &y) { return (*this) = (*this) ^ y; }
	Modint &operator ^= (const int &y) { return (*this) = (*this) ^ y; }
	Modint &operator ++ () { return (*this) += 1; }
	Modint &operator -- () { return (*this) -= 1; }
	Modint operator ++ (int) { Modint tmp = (*this); return ++ (*this), tmp; }
	Modint operator -- (int) { Modint tmp = (*this); return -- (*this), tmp; }
	friend Modint operator + (Modint x, const Modint &y) { return x += y; }
	friend Modint operator - (Modint x, const Modint &y) { return x -= y; }
	friend Modint operator * (Modint x, const Modint &y) { return x *= y; }
	friend Modint operator / (Modint x, const Modint &y) { return x /= y; }
	friend Modint operator ^ (Modint x, ll y) { Modint ans = 1; for (; y; y >>= 1, x *= x) if (y & 1) ans *= x; return ans; }
	friend Modint operator ^ (Modint x, int y) { return x ^= (ll)y; }
	friend Modint operator + (Modint x, const int &y) { return x += Modint(y); }
	friend Modint operator - (Modint x, const int &y) { return x -= Modint(y); }
	friend Modint operator * (Modint x, const int &y) { return x *= Modint(y); }
	friend Modint operator / (Modint x, const int &y) { return x /= Modint(y); }
	friend Modint operator + (int x, const Modint &y) { return Modint(x) += y; }
	friend Modint operator - (int x, const Modint &y) { return Modint(x) -= y; }
	friend Modint operator * (int x, const Modint &y) { return Modint(x) *= y; }
	friend Modint operator / (int x, const Modint &y) { return Modint(x) /= y; }
	friend ostream& operator << (ostream& os, const Modint &x) { os << (int)x; return os; }
	friend bool operator == (const Modint &x, const Modint &y) { return (int)x == (int)y; }
	friend bool operator != (const Modint &x, const Modint &y) { return (int)x != (int)y; }
	friend bool operator <= (const Modint &x, const Modint &y) { return (int)x <= (int)y; }
	friend bool operator >= (const Modint &x, const Modint &y) { return (int)x >= (int)y; }
	friend bool operator < (const Modint &x, const Modint &y) { return (int)x < (int)y; }
	friend bool operator > (const Modint &x, const Modint &y) { return (int)x > (int)y; }
};
template<> int Modint<0>::Mod = 998244353;
using mint = Modint<0>;

struct Combination {
	int N;
	vector<mint> _fac, _ifac, _inv;
	
	Combination(int n) { Init(n); return; }
	Combination(): N(0), _fac{1}, _ifac{1}, _inv{0} { return; }
	void Init(int n) {
		if (n <= N) return;
		_fac.resize(n + 1), _ifac.resize(n + 1), _inv.resize(n + 1);
		for (int i = N + 1; i <= n; i ++) _fac[i] = _fac[i - 1] * i;
		_ifac[n] = _fac[n].inv();
		for (int i = n; i > N; i --) _ifac[i - 1] = _ifac[i] * i,
																 _inv[i] = _ifac[i] * _fac[i - 1];
		N = n; return;
	}
	mint fac(int n) {
		if (n > N) Init(n << 1);
		return _fac[n];
	}
	mint ifac(int n) {
		if (n > N) Init(n << 1);
		return _ifac[n];
	}
	mint inv(int n) {
		if (n > N) Init(n << 1);
		return _inv[n];
	}
	mint C(int n, int m) {
		if (n < m || n < 0 || m < 0) return 0;
		return fac(n) * ifac(m) * ifac(n - m);
	}
} comb;

namespace Polynomial {
	constexpr int Mod = 998244353, g = 3, inv2 = (MOD + 1) >> 1;
	vector<int> rev;
	vector<mint> w{0, 1};
	
	void DFT(vector<mint> &a) {
		int n = (int)a.size();
		if ((int)rev.size() != n) { 
			int k = __lg(n) - 1; rev.resize(n);
			for (int i = 0; i < n; i ++)
				rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << k);
		}
		if ((int)w.size() < n) {
			int k = __lg(w.size()); w.resize(n);
			while (1 << k < n) {
				mint e = mint(g) ^ ((Mod - 1) >> (k + 1));
				for (int i = 1 << (k - 1); i < 1 << k; i ++)
					w[i << 1] = w[i], w[i << 1 | 1] = w[i] * e;
				k ++; 
			}
		}
		for (int i = 0; i < n; i ++)
			if (i < rev[i]) swap(a[i], a[rev[i]]);
		for (int k = 1; k < n; k <<= 1)
			for (int i = 0; i < n; i += k << 1)
				for (int j = 0; j < k; j ++) {
					mint u = a[i | j], v = a[i | j | k] * w[j | k];
					a[i | j] = u + v, a[i | j | k] = u - v;
				}
		return;
	}
	void IDFT(vector<mint> &a) {
		int n = (int)a.size();
		reverse(a.begin() + 1, a.end());
		DFT(a); mint inv = (1 - Mod) / n;
		for (int i = 0; i < n; i ++) a[i] *= inv;
		return;
	}
	
	struct Poly : public vector<mint> {
		
		Poly(): vector<mint>() { return; }
		explicit Poly(int n): vector<mint>(n) { return; }
		explicit Poly(const vector<mint> &a): vector<mint>(a) { return; }
		Poly(const initializer_list<mint> &a): vector<mint>(a) { return; }
		template<class _InputIterator, class = std::_RequireInputIter<_InputIterator>>
		explicit constexpr Poly(_InputIterator __first, _InputIterator __last): vector<mint>(__first, __last) { return; }
		template<class F> explicit constexpr Poly(int n, F f): vector<mint>(n) {
			for (int i = 0; i < n; i ++) (*this)[i] = f(i);
			return;
		}
		
		Poly Shift(int k) const {
			if (k >= 0) { auto ret = *this; ret.insert(ret.begin(), k, mint(0)); return ret; }
			else return (int)this -> size() <= - k ? Poly() : Poly(this -> begin() - k, this -> end());
		}
		Poly Trunc(int k) const {
			Poly f = *this; f.resize(k); return f;
		}
		
		friend Poly operator + (const Poly &f, const Poly &g) {
			Poly ret(max(f.size(), g.size()));
			for (int i = 0; i < (int)f.size(); i ++) ret[i] = f[i];
			for (int i = 0; i < (int)g.size(); i ++) ret[i] += g[i];
			return ret;
		}
		friend Poly operator - (const Poly &f, const Poly &g) {
			Poly ret(max(f.size(), g.size()));
			for (int i = 0; i < (int)f.size(); i ++) ret[i] = f[i];
			for (int i = 0; i < (int)g.size(); i ++) ret[i] -= g[i];
			return ret;
		}
		friend Poly operator - (const Poly &f) {
			Poly ret(f.size());
			for (int i = 0; i < (int)ret.size(); i ++) ret[i] = - f[i];
			return ret;
		}
		friend Poly operator * (Poly f, Poly g) {
			if (!f.size() || !g.size()) return Poly();
			if (f.size() < g.size()) std::swap(f, g);
			int n = 1, m = (int)f.size() + (int)g.size() - 1;
			if (g.size() < 1 << 7) {
				Poly ret(m);
				for (int i = 0; i < (int)f.size(); i ++)
					for (int j = 0; j < (int)g.size(); j ++)
						ret[i + j] += f[i] * g[j];
				return ret;
			}
			while (n < m) n <<= 1;
			f.resize(n), g.resize(n), DFT(f), DFT(g);
			for (int i = 0; i < n; i ++) f[i] *= g[i];
			IDFT(f), f.resize(m); return f;
		}
		friend Poly operator * (Poly f, mint x) {
			for (int i = 0; i < (int)f.size(); i ++) f[i] *= x;
			return f;
		}
		friend Poly operator * (mint x, Poly f) {
			for (int i = 0; i < (int)f.size(); i ++) f[i] *= x;
			return f;
		}
		friend Poly operator / (Poly f, mint x) {
			for (int i = 0; i < (int)f.size(); i ++) f[i] /= x;
			return f;
		}
		Poly& operator += (Poly oth) { return (*this) = (*this) + oth; }
		Poly& operator -= (Poly oth) { return (*this) = (*this) - oth; }
		Poly& operator *= (Poly oth) { return (*this) = (*this) * oth; }
		Poly& operator *= (mint oth) { return (*this) = (*this) * oth; }
		Poly& operator /= (mint oth) { return (*this) = (*this) / oth; }
		Poly Inv(int lim) const {
			Poly f{(*this)[0].inv()}; int k = 1;
			while (k < lim) k <<= 1, f = (f * (Poly{2}- Trunc(k) * f)).Trunc(k);
			return f.Trunc(lim);
		}
		Poly Deriv() const {
			if (this -> empty()) return Poly();
			Poly f(this -> size() - 1);
			for (int i = 0; i < (int)f.size(); i ++)
				f[i] = (i + 1) * (*this)[i + 1];
			return f;
		}
		Poly Integr() const {
			Poly f(this -> size() + 1);
			for (int i = 0; i < (int)this -> size(); i ++)
				f[i + 1] = (*this)[i] / (i + 1);
			return f;
		}
		Poly Log(int lim) const {
			return (Deriv() * Inv(lim)).Integr().Trunc(lim);
		}
		Poly Exp(int lim) const {
			Poly f{1}; int k = 1;
			while (k < lim) k <<= 1, f = (f * (Poly{1} - f.Log(k) + Trunc(k))).Trunc(k);
			return f.Trunc(lim);
		}
		Poly Pow(int k, int lim) const {
			int i = 0;
			while (i < (int)this -> size() && !(*this)[i]) i ++;
			if (i == (int)this -> size() || 1ll * i * k >= lim) return Poly(lim);
			mint v = (*this)[i]; Poly f = Shift(- i) * v.inv();
			return (f.Log(lim - i * k) * k).Exp(lim - i * k).Shift(i * k) * (v ^ k);
		}
		Poly Sqrt(int lim) const {
			Poly f{1}; int k = 1;
			while (k < lim) k <<= 1, f = (f + (Trunc(k) * f.Inv(k)).Trunc(k)) * inv2;
			return f.Trunc(lim);
		}
	};
} using Polynomial::Poly;

constexpr int N = 2e5 + 5;
int n, m;

void slv() {
	Read(n, m); mint ans = 2;
	auto calc = [&](int n, int m) {
		return comb.C(n + m - 2, n - 1) * comb.C(n + m - 2, m - 1)
				 - comb.C(n + m - 2, n) 		* comb.C(n + m - 2, m);
	};
	for (int i = 1; i <= n; i ++) ans += calc(i, m) * (n - i + 1);
	for (int j = 1; j <  m; j ++) ans += calc(n, j) * (m - j + 1);
	if (-- n >= 1 && -- m >= 1) {
		Poly F(n), G(m);
		for (int i = 0; i < n; i ++) F[i] = comb.ifac(i) * comb.ifac(i);
		for (int i = 0; i < m; i ++) G[i] = comb.ifac(i) * comb.ifac(i);
		F *= G;
		for (int i = 0; i < n + m - 1; i ++)
			ans += F[i] * comb.fac(i) * comb.fac(i) * 2;
		F.resize(n), F[0] = G[0] = 0;
		for (int i = 1; i < n; i ++) F[i] = comb.ifac(i - 1) * comb.ifac(i + 1);
		for (int i = 1; i < m; i ++) G[i] = comb.ifac(i - 1) * comb.ifac(i + 1);
		F *= G;
		for (int i = 0; i < n + m - 1; i ++)
			ans -= F[i] * comb.fac(i) * comb.fac(i) * 2;
	}
	Write((int)ans, '\n');
	return;
}
void clr() {

	return;
}

bool Med;
int main() {
#ifdef LOCAL
	freopen("!in.in", "r", stdin);
	freopen("!out.out", "w", stdout);
	fprintf(stderr, "%.3lf Mb\n", fabs((&Mbe - &Med) / 1048576.0));
#endif
	int T = 1;
//	int T = Read<int>();
	while (T --) slv(), clr();
#ifdef LOCAL
	fprintf(stderr, "%d ms\n", (int)clock());
#endif
	return 0;
}

詳細信息

Test #1:

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

input:

2 2

output:

11

result:

ok "11"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

20 23

output:

521442928

result:

ok "521442928"

Test #3:

score: 0
Accepted
time: 350ms
memory: 25812kb

input:

200000 200000

output:

411160917

result:

ok "411160917"

Test #4:

score: 0
Accepted
time: 0ms
memory: 3600kb

input:

8 3

output:

2899

result:

ok "2899"

Test #5:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

10 9

output:

338037463

result:

ok "338037463"

Test #6:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

3 3

output:

64

result:

ok "64"

Test #7:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

9 4

output:

39733

result:

ok "39733"

Test #8:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

36 33

output:

545587245

result:

ok "545587245"

Test #9:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

35 39

output:

62117944

result:

ok "62117944"

Test #10:

score: 0
Accepted
time: 0ms
memory: 3608kb

input:

48 10

output:

264659761

result:

ok "264659761"

Test #11:

score: 0
Accepted
time: 0ms
memory: 3616kb

input:

46 30

output:

880000821

result:

ok "880000821"

Test #12:

score: 0
Accepted
time: 0ms
memory: 3572kb

input:

25 24

output:

280799864

result:

ok "280799864"

Test #13:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

17 10

output:

624958192

result:

ok "624958192"

Test #14:

score: 0
Accepted
time: 9ms
memory: 3864kb

input:

4608 9241

output:

322218996

result:

ok "322218996"

Test #15:

score: 0
Accepted
time: 8ms
memory: 3680kb

input:

3665 6137

output:

537704652

result:

ok "537704652"

Test #16:

score: 0
Accepted
time: 8ms
memory: 3924kb

input:

4192 6186

output:

971816887

result:

ok "971816887"

Test #17:

score: 0
Accepted
time: 8ms
memory: 3984kb

input:

4562 4403

output:

867628411

result:

ok "867628411"

Test #18:

score: 0
Accepted
time: 8ms
memory: 3728kb

input:

8726 3237

output:

808804305

result:

ok "808804305"

Test #19:

score: 0
Accepted
time: 9ms
memory: 3780kb

input:

5257 8166

output:

488829288

result:

ok "488829288"

Test #20:

score: 0
Accepted
time: 6ms
memory: 4196kb

input:

8013 7958

output:

215666893

result:

ok "215666893"

Test #21:

score: 0
Accepted
time: 6ms
memory: 3880kb

input:

8837 5868

output:

239261227

result:

ok "239261227"

Test #22:

score: 0
Accepted
time: 6ms
memory: 3928kb

input:

8917 5492

output:

706653412

result:

ok "706653412"

Test #23:

score: 0
Accepted
time: 9ms
memory: 3944kb

input:

9628 5378

output:

753685501

result:

ok "753685501"

Test #24:

score: 0
Accepted
time: 334ms
memory: 20504kb

input:

163762 183794

output:

141157510

result:

ok "141157510"

Test #25:

score: 0
Accepted
time: 159ms
memory: 13404kb

input:

83512 82743

output:

114622013

result:

ok "114622013"

Test #26:

score: 0
Accepted
time: 158ms
memory: 11784kb

input:

84692 56473

output:

263907717

result:

ok "263907717"

Test #27:

score: 0
Accepted
time: 77ms
memory: 8380kb

input:

31827 74195

output:

200356808

result:

ok "200356808"

Test #28:

score: 0
Accepted
time: 336ms
memory: 23828kb

input:

189921 163932

output:

845151158

result:

ok "845151158"

Test #29:

score: 0
Accepted
time: 163ms
memory: 14600kb

input:

27157 177990

output:

847356039

result:

ok "847356039"

Test #30:

score: 0
Accepted
time: 159ms
memory: 12488kb

input:

136835 39390

output:

962822638

result:

ok "962822638"

Test #31:

score: 0
Accepted
time: 150ms
memory: 10668kb

input:

118610 18795

output:

243423874

result:

ok "243423874"

Test #32:

score: 0
Accepted
time: 151ms
memory: 10852kb

input:

122070 19995

output:

531055604

result:

ok "531055604"

Test #33:

score: 0
Accepted
time: 157ms
memory: 15332kb

input:

20031 195670

output:

483162363

result:

ok "483162363"

Test #34:

score: 0
Accepted
time: 341ms
memory: 25880kb

input:

199992 199992

output:

262099623

result:

ok "262099623"

Test #35:

score: 0
Accepted
time: 346ms
memory: 25960kb

input:

200000 199992

output:

477266520

result:

ok "477266520"

Test #36:

score: 0
Accepted
time: 345ms
memory: 25960kb

input:

199999 199996

output:

165483205

result:

ok "165483205"

Test #37:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

1 1

output:

3

result:

ok "3"

Test #38:

score: 0
Accepted
time: 8ms
memory: 5392kb

input:

1 100000

output:

8828237

result:

ok "8828237"

Test #39:

score: 0
Accepted
time: 11ms
memory: 6016kb

input:

100000 2

output:

263711286

result:

ok "263711286"

Test #40:

score: 0
Accepted
time: 0ms
memory: 3544kb

input:

50 50

output:

634767411

result:

ok "634767411"

Extra Test:

score: 0
Extra Test Passed