Cells（2021牛客暑期多校训练营9 C，LGV引理 + 范德蒙德行列式 + NTT）

本文主要是介绍Cells（2021牛客暑期多校训练营9 C，LGV引理 + 范德蒙德行列式 + NTT），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、题目链接

Cells

二、题目大意

在一个二维平面内，有 $n$ 个起点 $0, a_i)$ 要走到对应的终点 $(i, 0)$ ，每次可以向下走或向左走，问不相交路径组的方案数.

$\leq n \leq 5 \times 10^5, 0 \leq a_i \leq 10^6, a_i < a_{i+1}$ .

三、分析

易知从 $0, a_i)$ 走到 $(j, 0)$ 的方案数为 $\binom{a_i + j}{j}$ .
$\left [ \begin{matrix} \binom{a_1 + 1}{1} & \binom{a_1 + 2}{2} & \cdots & \binom{a_1 + n}{n} \\ \binom{a_2 + 1}{1} & \binom{a_2 + 2}{2} & \cdots & \binom{a_2 + n}{n} \\ \vdots & \vdots & \cdots & \vdots \\ \binom{a_n + 1}{1} & \binom{a_n + 2}{2} & \cdots & \binom{a_n + n}{n} \end{matrix} \right]$
则由 LGV 引理可知 $∣ M ∣$ 即为答案.

由于 $\times 10^5$ ，直接高斯消元是无法承受的，考虑简便计算 $∣ M ∣$ 的方法.
$\begin{aligned} |M| &= \left | \begin{matrix} \binom{a_1 + 1}{1} & \binom{a_1 + 2}{2} & \cdots & \binom{a_1 + n}{n} \\ \binom{a_2 + 1}{1} & \binom{a_2 + 2}{2} & \cdots & \binom{a_2 + n}{n} \\ \vdots & \vdots & \cdots & \vdots \\ \binom{a_n + 1}{1} & \binom{a_n + 2}{2} & \cdots & \binom{a_n + n}{n} \end{matrix} \right| \\ &= \left | \begin{matrix} \frac{(a_1 + 1)!}{1!a_1!} & \frac{(a_1 + 2)!}{2!a_1!} & \cdots & \frac{(a_1 + n)!}{n!a_1!} \\ \frac{(a_2 + 1)!}{1!a_2!} & \frac{(a_2 + 2)!}{2!a_2!} & \cdots & \frac{(a_2 + n)!}{n!a_2!} \\ \vdots & \vdots & \cdots & \vdots \\ \frac{(a_n + 1)!}{1!a_n!} & \frac{(a_n + 2)!}{2!a_n!} & \cdots & \frac{(a_n + n)!}{n!a_n!} \\ \end{matrix} \right| \\ &= \prod_{i=1}^n{\frac{1}{i!}}\left | \begin{matrix} \frac{(a_1 + 1)!}{a_1!} & \frac{(a_1 + 2)!}{a_1!} & \cdots & \frac{(a_1 + n)!}{a_1!} \\ \frac{(a_2 + 1)!}{a_2!} & \frac{(a_2 + 2)!}{a_2!} & \cdots & \frac{(a_2 + n)!}{a_2!} \\ \vdots & \vdots & \cdots & \vdots \\ \frac{(a_n + 1)!}{a_n!} & \frac{(a_n + 2)!}{a_n!} & \cdots & \frac{(a_n + n)!}{a_n!} \\ \end{matrix} \right| \\ &= \prod_{i=1}^n{\frac{1}{i!}}\left | \begin{matrix} (a_1 + 1) & (a_1 + 1)（a_1 + 2) & \cdots & \prod_{i=1}^n{(a_1 + i)} \\ (a_2 + 1) & (a_2 + 1)（a_2 + 2) & \cdots & \prod_{i=1}^n{(a_2 + i)} \\ \vdots & \vdots & \cdots & \vdots \\ (a_n + 1) & (a_n + 1)（a_n + 2) & \cdots & \prod_{i=1}^n{(a_n + i)} \\ \end{matrix} \right| \\ &= \prod_{i=1}^n{\frac{1}{i!}}\left | \begin{matrix} (a_1 + 1) & (a_2 + 1) & \cdots & (a_n + 1) \\ (a_1 + 1)（a_1 + 2) & (a_2 + 1)（a_2 + 2) & \cdots & (a_n + 1)（a_n + 2) \\ \vdots & \vdots & \cdots & \vdots \\ \prod_{i=1}^n{(a_1 + i)} & \prod_{i=1}^n{(a_2 + i)} & \cdots & \prod_{i=1}^n{(a_n + i)} \\ \end{matrix} \right| \\ &= \prod_{i=1}^n{\frac{1}{i!}}\left | \begin{matrix} (a_1 + 1) & (a_2 + 1) & \cdots & (a_n + 1) \\ (a_1 + 1)^2 & (a_2 + 1)^2 & \cdots & (a_n + 1)^2 \\ \vdots & \vdots & \cdots & \vdots \\ (a_1 + 1)^n & (a_2 + 1)^n & \cdots & (a_n + 1)^n \\ \end{matrix} \right| \\ &= \prod_{i=1}^n{\frac{a_i + 1}{i!}}\left | \begin{matrix} 1 & 1 & \cdots & 1 \\ a_1 + 1 & a_2 + 1 & \cdots & a_n + 1 \\ \vdots & \vdots & \cdots & \vdots \\ (a_1 + 1)^{n-1} & (a_2 + 1)^{n-1} & \cdots & (a_n + 1)^{n-1} \\ \end{matrix} \right| \\ &= \prod_{i=1}^n{\frac{a_i + 1}{i!} \prod_{j=1}^{i-1}{(a_i - a_j)}} \end{aligned}$
至此计算 $∣ M ∣$ 是 $O(n^2)$ 的，依然不可接受，考虑如何快速计算 $\begin{aligned} \prod_{j=1}^{i-1}{a_i - a_j} \end{aligned}$ .

记 $\begin{aligned} f(x) = \sum_{i=1}^{n}{x^{a_i}}\end{aligned}$ ， $\begin{aligned}g(x) = \sum_{i=1}^{n}{x^{-a_i}} \end{aligned}$ .

用 NTT 处理出 $\begin{aligned} h = f*g = \sum{c_ix^i} \end{aligned}$ .

按 $a_i - a_j)$ 计算贡献，则 $\begin{aligned} \prod_{i=1}^n{\prod_{j=1}^{i-1}(a_i - a_j)} = \prod_{i > 0}{i^{c_i}} \end{aligned}$ .

因此答案为 $\begin{aligned} \prod_{i=1}^{n}{\frac{a_i + 1}{i!}} \times \prod_{i>0}{i^{c_i}} \end{aligned}$ .

四、代码实现

#include <bits/stdc++.h>
using namespace std;template <typename T>
inline void read(T& x)
{x = 0; int f = 1; char ch = getchar();while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}while(isdigit(ch))  {x = x * 10 + ch - '0', ch = getchar();}x *= f;
}template <typename T>
void print(T x)
{if(x < 0) putchar('-'), x = -x;if(x > 9) print(x / 10);putchar(x % 10 + '0');
}template <typename T>
void print(T x, char ch)
{print(x), putchar(ch);
}typedef double db;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;template <ui M_> struct ModInt {static constexpr ui M = M_;ui x;constexpr ModInt(): x(0U){}constexpr ModInt(ui x_): x(x_ % M){}constexpr ModInt(ull x_): x(x_ % M){}constexpr ModInt(int x_): x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_){}constexpr ModInt(ll x_): x(((x_ %= static_cast<ll>(M)) < 0) ? (x_ + static_cast<ll>(M)) : x_){}ModInt &operator+=(const ModInt &a) {x = ((x += a.x) >= M) ? (x - M) : x; return *this;}ModInt &operator-=(const ModInt &a) {x = ((x -= a.x) >= M) ? (x + M) : x; return *this;}ModInt &operator*=(const ModInt &a) {x = (static_cast<ull>(x) * a.x) % M; return *this;}ModInt &operator/=(const ModInt &a) {return (*this *= a.inv());}ModInt pow(ll e) const {if(e < 0) return inv().pow(-e);ModInt a = *this, b = 1U; for(; e; e >>= 1) {if(e & 1) b *= a; a *= a;} return b;}ModInt inv() const {ui a = M, b = x; int y = 0, z = 1;while(b) {const ui q = a / b; const ui c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w;}return ModInt(y);}ModInt operator+() const {return *this;}ModInt operator-() const {ModInt a; a.x = x ? (M - x) : 0U; return a;}ModInt operator+(const ModInt &a) const {return (ModInt(*this) += a);}ModInt operator-(const ModInt &a) const {return (ModInt(*this) -= a);}ModInt operator*(const ModInt &a) const {return (ModInt(*this) *= a);}ModInt operator/(const ModInt &a) const {return (ModInt(*this) /= a);}template <class T> friend ModInt operator+(T a, const ModInt &b) {return (ModInt(a) += b);}template <class T> friend ModInt operator-(T a, const ModInt &b) {return (ModInt(a) -= b);}template <class T> friend ModInt operator*(T a, const ModInt &b) {return (ModInt(a) *= b);}template <class T> friend ModInt operator/(T a, const ModInt &b) {return (ModInt(a) /= b);}explicit operator bool() const {return x;}bool operator==(const ModInt &a) const {return (x == a.x);}bool operator!=(const ModInt &a) const {return (x != a.x);}friend std::ostream &operator<<(std::ostream &os, const ModInt &a) {return os << a.x;}
};constexpr unsigned MO = 998244353U;
constexpr unsigned MO2 = 2U * MO;
constexpr int FFT_MAX = 23;
using Mint = ModInt<MO>;
constexpr Mint FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 911660635U, 372528824U, 929031873U, 452798380U, 922799308U, 781712469U, 476477967U, 166035806U, 258648936U, 584193783U, 63912897U, 350007156U, 666702199U, 968855178U, 629671588U, 24514907U, 996173970U, 363395222U, 565042129U, 733596141U, 267099868U, 15311432U};
constexpr Mint INV_FFT_ROOTS[FFT_MAX + 1] = {1U, 998244352U, 86583718U, 509520358U, 337190230U, 87557064U, 609441965U, 135236158U, 304459705U, 685443576U, 381598368U, 335559352U, 129292727U, 358024708U, 814576206U, 708402881U, 283043518U, 3707709U, 121392023U, 704923114U, 950391366U, 428961804U, 382752275U, 469870224U};
constexpr Mint FFT_RATIOS[FFT_MAX] = {911660635U, 509520358U, 369330050U, 332049552U, 983190778U, 123842337U, 238493703U, 975955924U, 603855026U, 856644456U, 131300601U, 842657263U, 730768835U, 942482514U, 806263778U, 151565301U, 510815449U, 503497456U, 743006876U, 741047443U, 56250497U, 867605899U};
constexpr Mint INV_FFT_RATIOS[FFT_MAX] = {86583718U, 372528824U, 373294451U, 645684063U, 112220581U, 692852209U, 155456985U, 797128860U, 90816748U, 860285882U, 927414960U, 354738543U, 109331171U, 293255632U, 535113200U, 308540755U, 121186627U, 608385704U, 438932459U, 359477183U, 824071951U, 103369235U};void fft(Mint *as, int n) {int m = n;if(m >>= 1) {for(int i = 0; i < m; ++i) {const ui x = as[i + m].x;as[i + m].x = as[i].x + MO - x;as[i].x += x;}}if(m >>= 1) {Mint prod = 1U;for(int h = 0, i0 = 0; i0 < n; i0 += (m<<1)) {for(int i = i0; i < i0 + m; ++i) {const ui x = (prod * as[i + m]).x;as[i + m].x = as[i].x + MO - x;as[i].x += x;}prod *= FFT_RATIOS[__builtin_ctz(++h)];}}while(m) {if(m >>= 1) {Mint prod = 1U;for(int h = 0, i0 = 0; i0 < n; i0 += (m<<1)) {for(int i = i0; i < i0 + m; ++i) {const ui x = (prod * as[i + m]).x;as[i + m].x = as[i].x + MO - x;as[i].x += x;}prod *= FFT_RATIOS[__builtin_ctz(++h)];}}if(m >>= 1) {Mint prod = 1U;for(int h = 0, i0 = 0; i0 < n; i0 += (m<<1)) {for(int i = i0; i < i0 + m; ++i) {const ui x = (prod * as[i + m]).x;as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x;as[i + m].x = as[i].x + MO - x;as[i].x += x;}prod *= FFT_RATIOS[__builtin_ctz(++h)];}}}for(int i = 0; i < n; ++i) {as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x;as[i].x = (as[i].x >= MO) ? (as[i].x - MO) : as[i].x;}
}void invFft(Mint *as, int n) {int m = 1;if(m < n>>1) {Mint prod = 1U;for(int h = 0, i0 = 0; i0 < n; i0 += (m<<1)) {for(int i = i0; i < i0 + m; ++i) {const ull y = as[i].x + MO - as[i + m].x;as[i].x += as[i + m].x;as[i + m].x = (prod.x * y) % MO;}prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];}m <<= 1;}for(; m < n>>1; m <<= 1) {Mint prod = 1U;for(int h = 0, i0 = 0; i0 < n; i0 += (m<<1)) {for(int i = i0; i < i0 + (m>>1); ++i) {const ull y = as[i].x + MO2 - as[i + m].x;as[i].x += as[i + m].x;as[i].x = (as[i].x >= MO2) ? (as[i].x - MO2) : as[i].x;as[i + m].x = (prod.x * y) % MO;}for(int i = i0 + (m>>1); i < i0 + m; ++i) {const ull y = as[i].x + MO - as[i + m].x;as[i].x += as[i + m].x;as[i + m].x = (prod.x * y) % MO;}prod *= INV_FFT_RATIOS[__builtin_ctz(++h)];}}if(m < n) {for(int i = 0; i < m; ++i) {const ui y = as[i].x + MO2 - as[i + m].x;as[i].x += as[i + m].x;as[i + m].x = y;}}const Mint invN = Mint(n).inv();for(int i = 0; i < n; ++i) {as[i] *= invN;}
}void fft(vector<Mint> &as) {fft(as.data(), as.size());
}void invFft(vector<Mint> &as) {invFft(as.data(), as.size());
}vector<Mint> convolve(vector<Mint>& as, vector<Mint>& bs) {if(as.empty() || bs.empty()) return {};const int len = as.size() + bs.size() - 1;int n = 1;for(; n < len; n <<= 1) {}as.resize(n); fft(as);bs.resize(n); fft(bs);for(int i = 0; i < n; ++i) as[i] *= bs[i];invFft(as);as.resize(len);return as;
}const int M = (int)5e5;
const int N = (int)1e5;
const int S = (int)1e6;
const int inf = 0x3f3f3f3f;
const ll mod = (ll)998244353;int fac[M + 5], inv[M + 5], invfac[M + 5];void init()
{fac[0] = fac[1] = inv[1] = invfac[0] = invfac[1] = 1;for(int i = 2; i <= M; ++i){fac[i] = 1ll * fac[i - 1] * i % mod;inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod;invfac[i] = 1ll * invfac[i - 1] * inv[i] % mod;}
}vector<Mint> as, bs;ll quick(ll a, ll b, ll p = mod)
{ll s = 1;while(b){if(b & 1) s = s * a % p;a = a * a % p;b >>= 1;}return s % p;
}void work()
{int n; read(n);int ans = 1;as.resize(S + 1), bs.resize(S + 1);for(int i = 1, a; i <= n; ++i){read(a);as[a] = 1, bs[S - a] = 1;ans = 1ll * ans * (a + 1) % mod * invfac[i] % mod;}convolve(as, bs);int k = as.size();for(int i = S + 1; i < k; ++i) if(as[i].x) ans = 1ll * ans * quick(i - S, as[i].x) % mod;print(ans, '\n');
}int main()
{
//    ios::sync_with_stdio(0);
//    cin.tie(0); cout.tie(0);
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
//    int T; read(T);
//    for(int ca = 1; ca <= T; ++ca)
//    {
//        work();
//    }init();work();
//    cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";return 0;
}