Description
求将一个凸多边形划分为n个k边形的方案数($mod$ $10^9 + 7$)
Solution
ps：看了兔队的游记，但由于太菜推了好久才懂，稍微记录下
原凸多边形的边数是$n imes(k-2)+2$(因为$n$个$k$边形的顶点都在原凸多边形顶点上，它们的内角和等于原凸多边形内角和)，不过这东西并没有任何卵用
划分时，原凸多边形的每条边都会成为某个$k$边形的边
因此我们先选定某条边，然后再在原凸多边形上再选择$k-2$个点，把这$k$个点构成的$k$边形取走后原凸多边形被划分为$k-1$个凸多边形(当然有些变成0个点直接忽略掉)
取的时候要保证拆分后的凸多边形划分成$k$边形后不会有剩余
方程为 $f(n,k)=sum f(a_1,k) imes f(a_2,k) imes cdots imes f(a_{k-1},k)$ ,( $sum_{i=1}^{k-1} a_i == n - 1$ )
这样得到一个$O(n^k)$的暴力
方程长得有点像Catalan数，多了几重枚举
他们说这是K-Catalan数，但是百度好像没什么人写，找到一篇英文的但是看不懂
然后就对着结论瞎猜
兔队算的是由$n$个$+(k-2)$和$n(k-2)$个$-1$组成的任意前缀和都大于等于0的序列数
想想好像等价于上面的方程式，$n=0$ or $1$时, $f(0,k)=f(1,k)=1$ 显然满足两者等价，$n>1$时相当于在序列的开头放一个$+(k-2)$,在后面总共$n imes(k-1)-1$个位置中任意选取$(k-2)$个位置放入$-1$，这样就把整个序列分割成$k-1$段（目前已放入的位置相邻两个之间为一段，包含为空的段），对于每种确定的分割方案对总方案贡献为$f(a_1,k) imes f(a_2,k) imes cdots imes f(a_{k-1},k)$, 这样枚举每种分割方案后相加得到总方案可以保证不重不漏
稍微转化一下，改成计算由$n$个$+(k-2)$和$n(k-2)+1$个$-1$组成的(除最后一个位置外)任意前缀和都大于等于0的序列数
这里先放下结论:$$ans=frac{1}{nk-n+1}inom{nk-n+1}{n}$$
$inom{nk-n+1}{n}$算的显然是任意排列的序列数
乘上$frac{1}{nk-n+1}$是因为对于每$nk-n+1$个循环同构的序列中有且仅有一个序列合法
对于每种不合法的序列，我们可以找到它的前缀和最小的位置$pos$（有多个取最靠前的那个），将[1,pos]和[pos+1,nk-n+1]对调，得到一个与它循环同构的合法序列
对于每种合法序列，任意后缀和均小于0，无论将哪个后缀调到前面都会把序列变为非法
这样可以推出每$nk-n+1$个循环同构的序列中有且仅有一个序列合法
（写得好啰嗦，博客新人大家体谅下，如果哪里写错了欢迎指出）
（听说还有一种生成函数的推法，不过好像要解一个$xg(x)^{k-1}-g(x)+1=0$的$k-1$次方程再展开,不会呜呜呜。这个方程可以解吗，还是用的其它方法，又或者我方程推错了？？（不过我验证了k=3似乎没问题，往上就不会了）。求路过的大佬指点下）