$$f(i, j) = f(i – 1, j – 1) + (i – 1) \times f(i – 1, j)$$

$n$前面的结成 $a – 1$个环，$n$后面的结成 $b – 1$个环，相当于一共用 $n – 1$个数字结成 $a + b – 2$个环

$Ans = S _ 1(n – 1, a + b – 2) \times C _ {a + b – 2} ^ {b – 1}$

$$\prod _ {i = 0} ^ {n – 1} (x + i)$$

#include <bits/stdc++.h>

#define NS (262144)
#define LGS (18)
#define MOD (998244353)
#define G (3)

#define pls(a, b) ((a) + (b) < MOD ? (a) + (b) : (a) + (b) - MOD)
#define mns(a, b) ((a) - (b) < 0 ? (a) - (b) + MOD : (a) - (b))
#define mul(a, b) (1ll * (a) * (b) % MOD)
#define Inv(a) (qpow((a), MOD - 2))

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int qpow(int a, int b)
{
int res = 1;
while (b)
{
if (b & 1) res = mul(res, a);
a = mul(a, a), b >>= 1;
}
return res;
}

int n, A, B;

int rev[NS];

struct poly
{
int d[NS], N, bs;
int& operator [] (const int a) {return d[a];}
void resize(int s)
{
int tmp = N;
N = 1, bs = 0;
while (N < s) N <<= 1, bs++;
for (int i = tmp; i < N; i += 1) d[i] = 0;
}
void ntt(int t)
{
for (int i = 1; i < N; i += 1)
{
rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bs - 1));
if (i < rev[i]) swap(d[i], d[rev[i]]);
}
for (int l = 1; l < N; l <<= 1)
{
int dt = qpow(G, (MOD - 1) / (l << 1));
if (t == -1) dt = Inv(dt);
for (int i = 0; i < N; i += (l << 1))
{
int g = 1, t1, t2;
for (int j = i; j < i + l; j += 1, g = mul(g, dt))
{
t1 = d[j], t2 = mul(g, d[j + l]);
d[j] = pls(t1, t2), d[j + l] = mns(t1, t2);
}
}
}
if (t == -1)
{
int inv = Inv(N);
for (int i = 0; i < N; i += 1) d[i] = mul(d[i], inv);
}
}
void operator *= (poly &oth)
{
for (int i = 0; i < N; i += 1) d[i] = mul(d[i], oth[i]);
}
} P[LGS];

stack<int> rub;

int Binary(int l, int r)
{
if (l == r)
{
int a = rub.top(); rub.pop();
P[a].resize(2), P[a][0] = l, P[a][1] = 1;
return a;
}
int mid = (l + r) >> 1;
int a = Binary(l, mid), b = Binary(mid + 1, r);
P[a].resize(r - l + 2), P[b].resize(r - l + 2);
P[a].ntt(1), P[b].ntt(1), P[a] *= P[b], P[a].ntt(-1), rub.push(b);
return a;
}

int C(int a, int b)
{
int x = 1, y = 1;
for (int i = a - b + 1; i <= a; i += 1) x = mul(x, i);
for (int i = 1; i <= b; i += 1) y = mul(y, i);
return mul(x, Inv(y));
}

int main(int argc, char const* argv[])
{
IN(n), IN(A), IN(B), n--;
if (!A || !B || A + B - 2 > n) puts("0"), exit(0);
if (!n) puts("1"), exit(0);
for (int i = 0; i < LGS; i += 1) rub.push(i);
int a = Binary(0, n - 1);
printf("%lld\n", mul(P[a][A + B - 2], C(A + B - 2, B - 1)));
return 0;
}


#### Remmina

No puzzle that couldn't be solved.

### 5 条评论

你行你写啊 QvQ

#### boshi · 2019年1月30日 9:55 下午

https://www.luogu.org/recordnew/show/15932564

比你快哦

#### Remmina · 2019年1月30日 10:49 下午

我是要你写博客，不是要你装 X

行行行