「FJOI2020」凸多边形正则划分问题

题意

求把一个凸多边形划分为 $n$ 个边数为 $k$ 的凸多边形的方案数。

思路

前置定理：由 $n$ 个凸 $k$ 边形组成的凸多边形的边数为 $k+(n-1)\cdot(k-2)$（是一个定值）。

设 $f_{n,k}$ 为把一个凸多边形划分为 $n$ 个边数为 $k$ 的凸多边形的方案数。

枚举这个凸多边形最下方的一条边所在的 $k$ 边形，显然它把多边形分成了好几部分。这个 $k$ 边形的除了最下方的一条边以外的其余 $k-1$ 条边，每边都可以 “延伸” 出由若干个由 $k$ 边形组成的形状。

易知方案是不重不漏的。

递推式：

$\begin{aligned} f_{0,k}&=1\\ f_{n,k}&=\sum_{\sum_{i=1}^{k-1}S_i=n-1}\prod_{i=1}^{k-1}f_{S_i,k} \end{aligned}$

考虑拉格朗日反演。

$\begin{aligned} F&=x\cdot(F+1)^{k-1}\\ G&=F^{\langle-1\rangle}=\frac x{(x+1)^{k-1}}\\ [x^n]F&=\frac 1n[x^{n-1}]\left(\frac xG\right)^n\\ &=\frac1n[x^{n-1}](x+1)^{n(k-1)}\\ &=\frac1nC_{nk-n}^{n-1} \end{aligned}$

实现

预处理阶乘及其逆元，按照式子求即可。

注意空间限制。

代码

#include<cstdio>
using namespace std;
const int N=555555,K=200,L=1e7,mod=1e9+7;
int n,k;
int fac[L+1],invf[L+1];
int res;
int pow(int x,int times)
{
    int ret=1;
    while(times) {
        if(times&1) {
            ret=1ll*ret*x%mod;
        }
        times>>=1,x=1ll*x*x%mod;
    }
    return ret;
}
inline int inv(int x)
{
    return pow(x,mod-2);
}
void initFac()
{
    fac[0]=1;
    for(int i=1;i<=L;++i) {
        fac[i]=1ll*fac[i-1]*i%mod;
    }
    invf[L]=inv(fac[L]);
    for(int i=L;i;--i) {
        invf[i-1]=1ll*invf[i]*i%mod;
    }
    return;
}
int C(int n,int m)
{
    if(n<=L) {
        return 1ll*fac[n]*invf[n-m]%mod*invf[m]%mod;
    }
    int ret=1;
    for(int i=n-m+1;i<=n;++i) {
        ret=1ll*ret*i%mod;
    }
    ret=1ll*ret*invf[m]%mod;
    return ret;
}
int main()
{
    freopen("conv.in","r",stdin);
    freopen("conv.out","w",stdout);
    initFac();
    while(scanf("%d%d",&n,&k)!=EOF) {
        res=(res+1ll*C(n*(k-1),n-1)*inv(n))%mod;
    }
    printf("%d\n",res);
    return 0;
}

致谢

感谢 PinkRabbit 给出的拉格朗日反演式子。
感谢 Yuc 给出的求复合逆的方法。