Cells
二、题目大意在一个二维平面内，有 n n n 个起点 ( 0 , a i ) (0, a_i) (0,ai) 要走到对应的终点 ( i , 0 ) (i, 0) (i,0)，每次可以向下走或向左走，问不相交路径组的方案数.
1
≤
n
≤
5
×
1
0
5
,
0
≤
a
i
≤
1
0
6
,
a
i
<
a
i
+
1
1 leq n leq 5 times 10^5, 0 leq a_i leq 10^6, a_i < a_{i+1}
1≤n≤5×105,0≤ai≤106,ai 易知从
(
0
,
a
i
)
(0, a_i)
(0,ai) 走到
(
j
,
0
)
(j,0)
(j,0) 的方案数为
(
a
i
+
j
j
)
binom{a_i + j}{j}
(jai+j). 由于
m
a
x
(
n
)
=
5
×
1
0
5
max(n) = 5 times 10^5
max(n)=5×105，直接高斯消元是无法承受的，考虑简便计算
∣
M
∣
|M|
∣M∣ 的方法. 记
f
(
x
)
=
∑
i
=
1
n
x
a
i
begin{aligned} f(x) = sum_{i=1}^{n}{x^{a_i}}end{aligned}
f(x)=i=1∑nxai，
g
(
x
)
=
∑
i
=
1
n
x
−
a
i
begin{aligned}g(x) = sum_{i=1}^{n}{x^{-a_i}} end{aligned}
g(x)=i=1∑nx−ai. 用 NTT 处理出
h
=
f
∗
g
=
∑
c
i
x
i
begin{aligned} h = f*g = sum{c_ix^i} end{aligned}
h=f∗g=∑cixi. 按
(
a
i
−
a
j
)
(a_i - a_j)
(ai−aj) 计算贡献，则
∏
i
=
1
n
∏
j
=
1
i
−
1
(
a
i
−
a
j
)
=
∏
i
>
0
i
c
i
begin{aligned} prod_{i=1}^n{prod_{j=1}^{i-1}(a_i - a_j)} = prod_{i > 0}{i^{c_i}} end{aligned}
i=1∏nj=1∏i−1(ai−aj)=i>0∏ici. 因此答案为
∏
i
=
1
n
a
i
+
1
i
!
×
∏
i
>
0
i
c
i
begin{aligned} prod_{i=1}^{n}{frac{a_i + 1}{i!}} times prod_{i>0}{i^{c_i}} end{aligned}
i=1∏ni!ai+1×i>0∏ici.
M
=
[
(
a
1
+
1
1
)
(
a
1
+
2
2
)
⋯
(
a
1
+
n
n
)
(
a
2
+
1
1
)
(
a
2
+
2
2
)
⋯
(
a
2
+
n
n
)
⋮
⋮
⋯
⋮
(
a
n
+
1
1
)
(
a
n
+
2
2
)
⋯
(
a
n
+
n
n
)
]
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]
M=⎣⎢⎢⎢⎡(1a1+1)(1a2+1)⋮(1an+1)(2a1+2)(2a2+2)⋮(2an+2)⋯⋯⋯⋯(na1+n)(na2+n)⋮(nan+n)⎦⎥⎥⎥⎤
则由 LGV 引理可知
∣
M
∣
|M|
∣M∣ 即为答案.
∣
M
∣
=
∣
(
a
1
+
1
1
)
(
a
1
+
2
2
)
⋯
(
a
1
+
n
n
)
(
a
2
+
1
1
)
(
a
2
+
2
2
)
⋯
(
a
2
+
n
n
)
⋮
⋮
⋯
⋮
(
a
n
+
1
1
)
(
a
n
+
2
2
)
⋯
(
a
n
+
n
n
)
∣
=
∣
(
a
1
+
1
)
!
1
!
a
1
!
(
a
1
+
2
)
!
2
!
a
1
!
⋯
(
a
1
+
n
)
!
n
!
a
1
!
(
a
2
+
1
)
!
1
!
a
2
!
(
a
2
+
2
)
!
2
!
a
2
!
⋯
(
a
2
+
n
)
!
n
!
a
2
!
⋮
⋮
⋯
⋮
(
a
n
+
1
)
!
1
!
a
n
!
(
a
n
+
2
)
!
2
!
a
n
!
⋯
(
a
n
+
n
)
!
n
!
a
n
!
∣
=
∏
i
=
1
n
1
i
!
∣
(
a
1
+
1
)
!
a
1
!
(
a
1
+
2
)
!
a
1
!
⋯
(
a
1
+
n
)
!
a
1
!
(
a
2
+
1
)
!
a
2
!
(
a
2
+
2
)
!
a
2
!
⋯
(
a
2
+
n
)
!
a
2
!
⋮
⋮
⋯
⋮
(
a
n
+
1
)
!
a
n
!
(
a
n
+
2
)
!
a
n
!
⋯
(
a
n
+
n
)
!
a
n
!
∣
=
∏
i
=
1
n
1
i
!
∣
(
a
1
+
1
)
(
a
1
+
1
)
（
a
1
+
2
)
⋯
∏
i
=
1
n
(
a
1
+
i
)
(
a
2
+
1
)
(
a
2
+
1
)
（
a
2
+
2
)
⋯
∏
i
=
1
n
(
a
2
+
i
)
⋮
⋮
⋯
⋮
(
a
n
+
1
)
(
a
n
+
1
)
（
a
n
+
2
)
⋯
∏
i
=
1
n
(
a
n
+
i
)
∣
=
∏
i
=
1
n
1
i
!
∣
(
a
1
+
1
)
(
a
2
+
1
)
⋯
(
a
n
+
1
)
(
a
1
+
1
)
（
a
1
+
2
)
(
a
2
+
1
)
（
a
2
+
2
)
⋯
(
a
n
+
1
)
（
a
n
+
2
)
⋮
⋮
⋯
⋮
∏
i
=
1
n
(
a
1
+
i
)
∏
i
=
1
n
(
a
2
+
i
)
⋯
∏
i
=
1
n
(
a
n
+
i
)
∣
=
∏
i
=
1
n
1
i
!
∣
(
a
1
+
1
)
(
a
2
+
1
)
⋯
(
a
n
+
1
)
(
a
1
+
1
)
2
(
a
2
+
1
)
2
⋯
(
a
n
+
1
)
2
⋮
⋮
⋯
⋮
(
a
1
+
1
)
n
(
a
2
+
1
)
n
⋯
(
a
n
+
1
)
n
∣
=
∏
i
=
1
n
a
i
+
1
i
!
∣
1
1
⋯
1
a
1
+
1
a
2
+
1
⋯
a
n
+
1
⋮
⋮
⋯
⋮
(
a
1
+
1
)
n
−
1
(
a
2
+
1
)
n
−
1
⋯
(
a
n
+
1
)
n
−
1
∣
=
∏
i
=
1
n
a
i
+
1
i
!
∏
j
=
1
i
−
1
(
a
i
−
a
j
)
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∣=∣∣∣∣∣∣∣∣∣(1a1+1)(1a2+1)⋮(1an+1)(2a1+2)(2a2+2)⋮(2an+2)⋯⋯⋯⋯(na1+n)(na2+n)⋮(nan+n)∣∣∣∣∣∣∣∣∣=∣∣∣∣∣∣∣∣∣∣1!a1!(a1+1)!1!a2!(a2+1)!⋮1!an!(an+1)!2!a1!(a1+2)!2!a2!(a2+2)!⋮2!an!(an+2)!⋯⋯⋯⋯n!a1!(a1+n)!n!a2!(a2+n)!⋮n!an!(an+n)!∣∣∣∣∣∣∣∣∣∣=i=1∏ni!1∣∣∣∣∣∣∣∣∣∣a1!(a1+1)!a2!(a2+1)!⋮an!(an+1)!a1!(a1+2)!a2!(a2+2)!⋮an!(an+2)!⋯⋯⋯⋯a1!(a1+n)!a2!(a2+n)!⋮an!(an+n)!∣∣∣∣∣∣∣∣∣∣=i=1∏ni!1∣∣∣∣∣∣∣∣∣(a1+1)(a2+1)⋮(an+1)(a1+1)（a1+2)(a2+1)（a2+2)⋮(an+1)（an+2)⋯⋯⋯⋯∏i=1n(a1+i)∏i=1n(a2+i)⋮∏i=1n(an+i)∣∣∣∣∣∣∣∣∣=i=1∏ni!1∣∣∣∣∣∣∣∣∣(a1+1)(a1+1)（a1+2)⋮∏i=1n(a1+i)(a2+1)(a2+1)（a2+2)⋮∏i=1n(a2+i)⋯⋯⋯⋯(an+1)(an+1)（an+2)⋮∏i=1n(an+i)∣∣∣∣∣∣∣∣∣=i=1∏ni!1∣∣∣∣∣∣∣∣∣(a1+1)(a1+1)2⋮(a1+1)n(a2+1)(a2+1)2⋮(a2+1)n⋯⋯⋯⋯(an+1)(an+1)2⋮(an+1)n∣∣∣∣∣∣∣∣∣=i=1∏ni!ai+1∣∣∣∣∣∣∣∣∣1a1+1⋮(a1+1)n−11a2+1⋮(a2+1)n−1⋯⋯⋯⋯1an+1⋮(an+1)n−1∣∣∣∣∣∣∣∣∣=i=1∏ni!ai+1j=1∏i−1(ai−aj)
至此计算
∣
M
∣
|M|
∣M∣ 是
O
(
n
2
)
O(n^2)
O(n2) 的，依然不可接受，考虑如何快速计算
∏
j
=
1
i
−
1
a
i
−
a
j
begin{aligned} prod_{j=1}^{i-1}{a_i - a_j} end{aligned}
j=1∏i−1ai−aj.#include
