Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
86411748 Дорешивание:
JKLover
960G - 18 C++17 (GCC 7-32) Полное решение 608 мс 9184 КБ 2020-07-10 11:56:12 2020-07-10 11:56:12
→ Исходный код
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 998244353, G = 3;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
int fpow(int a, int b)
{
	int res = 1;
	while (b)
	{
		if (b & 1)
			res = mul(res, a);
		a = mul(a, a);
		b >>= 1;
	}
	return res;
}
const int N = 1 << 17 | 10;
int curn = 0, invn, rev[N], omega[N], inv[N];
void init(int n)
{
	if (n == curn)	
		return;
	invn = fpow(n, P - 2);
	for (int i = 0; i < n; ++i)
		rev[i] = (rev[i >> 1] >> 1) | ((i & 1) * (n >> 1));
	for (int l = 2; l <= n; l <<= 1)
	{
		omega[l] = fpow(G, (P - 1) / l);
		inv[l] = fpow(omega[l], P - 2);
	}
	curn = n;
}
void DFT(int *a, int n, bool invflag)
{
	init(n);
	for (int i = 0; i < n; ++i)
		if (i < rev[i])
			swap(a[i], a[rev[i]]);
	for (int l = 2; l <= n; l <<= 1)
	{
		int gi = omega[l], m = l >> 1;
		if (invflag)
			gi = inv[l];
		for (int *p = a; p != a + n; p += l)
		{
			int g = 1;
			for (int i = 0; i < m; ++i)
			{
				int t = mul(g, p[i + m]);
				p[i + m] = add(p[i], P - t);
				p[i] = add(p[i], t);
				g = mul(g, gi);
			}
		}
	}
	if (invflag)
	{
		for (int i = 0; i < n; ++i)
			a[i] = mul(a[i], invn);
	}
}
typedef vector<int> poly;
int _a[N], _b[N], _c[N];
poly operator * (const poly &A, const poly &B)
{
	int len = A.size() + B.size() - 1, n = 1;
	poly C(len);
	while (n < len)
		n <<= 1;
	int lenA = A.size(), lenB = B.size();
	for (int i = 0; i < lenA; ++i)
		_a[i] = A[i];
	for (int i = lenA; i < n; ++i)
		_a[i] = 0;
	for (int i = 0; i < lenB; ++i)
		_b[i] = B[i];
	for (int i = lenB; i < n; ++i)
		_b[i] = 0;
	DFT(_a, n, false);
	DFT(_b, n, false);
	for (int i = 0; i < n; ++i)
		_c[i] = mul(_a[i], _b[i]);
	DFT(_c, n, true);
	for (int i = 0; i < len; ++i)
		C[i] = _c[i];
	return C;
}
int n, m, fac[N], invfac[N], A, B;
poly Prod(int l, int r)
{
	if (l == r)
		return poly{l, 1};
	int mid = (l + r) >> 1;
	return Prod(l, mid) * Prod(mid + 1, r);
}
int binom(int x, int y)
{
	return mul(fac[x], mul(invfac[y], invfac[x - y]));
}
int main()
{
	n = read(), A = read() - 1, B = read() - 1;
	if (A < 0 || B < 0 || A + B > n - 1)
		return puts("0"), 0;
	if (n == 1)
		return puts("1"), 0;
	fac[0] = 1;
	for (int i = 1; i <= n; ++i)
		fac[i] = mul(fac[i - 1], i);
	invfac[n] = fpow(fac[n], P - 2);
	for (int i = n - 1; i >= 0; --i)
		invfac[i] = mul(invfac[i + 1], i + 1);
	poly res = Prod(0, n - 2);
//	for (int i = 0; i <= n - 1; ++i)
//		printf("%d ", res[i]);
//	puts("");
	cout << mul(res[A + B], binom(A + B, A)) << '\n';
	return 0;
}
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования