画图可以发现形成的图形状类似于网格图，每一斜行代表每一列，若增加 1 1 1，则向外拓展 1 1 1 个单位，否则向内收缩一个单位。
相邻关键列之间结点数最多变化 5 5 5，所以关键列上点数是 O ( n ) O(n) O(n) 级别的。
设 f i , j f_{i,j} fi,j 表是到达第 i i i 列从上往下数的 j j j 个点的方案数。
f i , j = ∑ k f i − 1 , k ∗ ( a i + b i a i + j − k ) f_{i,j} = \sum_k f_{i - 1,k}*\binom{a_i + b_i}{a_i + j - k} fi,j=k∑fi−1,k∗(ai+j−kai+bi)
然后把组合数拆成阶乘形式
f i , j = ( a i + b i ) ! ∑ k f i − 1 , k ∗ 1 ( a i + j − k ) ! ∗ 1 ( b i − j + k ) ! f_{i,j} = (a_i + b_i)!\sum_k f_{i - 1,k}*\frac{1}{(a_i + j - k)!}*\frac{1}{(b_i - j + k)!} fi,j=(ai+bi)!k∑fi−1,k∗(ai+j−k)!1∗(bi−j+k)!1
然后将后面那项编号为 j − k j - k j−k，然后就是卷积的形式了，可以 N T T NTT NTT 优化为 O ( n 2 log n ) O(n^2\log n) O(n2logn)