本题属于三角化（Triangulation）问题中的一类，根据此论文中的定理4，取$k=4, r=30$，总切法的数量是
$$\sum_{j=0}^k\sum_{\ell=0}^{rk-(r+1)j-2}(-1)^j2^{\ell}\binom{k}{j}\binom{k-2+\ell}{\ell}\binom{(r-1)k-\ell-3}{rk-(r+1)j-\ell-2},$$
其中$\binom{n}{m}$需要使用扩展定义，即当$n\ge m>0$时$\binom{n}{m}$就是组合数，当$m>n\ge 0$时$\binom{n}{m}$为$0$，而当$n$小于$0$时它等于$(1+x)^{-|n|}$的幂级数展开中$x^m$前的系数，即$(-1)^m\binom{m+|n|-1}{m}$。
直接求和计算即得结果$82282080$。
注：以下代码为Python 3代码，因math.comb是Python 3的新增函数。
import math
def f(n,m):
if n>=m>=0:
return math.comb(n,m)
elif m>=n>=0:
return 0
elif n < 0 <= m:
return -math.comb(-n+m-1,m) if m%2>0 else math.comb(-n+m-1,m)
k,r=4,30
print(sum((-1 if j%2>0 else 1)*(1<<l)*f(k,j)*f(k-2+l,l)*f((r-1)*k-l-3,r*k-(r+1)*j-l-2) for j in range(k+1) for l in range(r*k-(r+1)*j-1))%100000000)
|
