题意：给定 \(n,k\)，求 \(nk-2(n-1)\) 边形的 \(k\) 角剖分数量，\(n\le1.1\times10^6\)。
做法：
前置知识：
-
多项式复合逆：如果 \(F(G(x)) = G(F(x))=x\)，则称 \(F,G\) 互为复合逆。
-
拉格朗日反演公式：设 \(F\) 的复合逆为 \(G\)，那么我们有
证明：因为 \(x=F(G(x))\)，所以有 \(x = \sum\limits_{i=1}^nf_iG(x)^i\)。
两边求导，得到 \(1=\sum\limits_{i=1}^nif_iG(x)^{i-1}G'(x)\)。
为了得到 \(f_n\)，我们考虑对两边除掉 \(G(x)^n\)，得到 \(\frac{1}{G(x)^n}=\sum\limits_{i=1}^nif_i{G(x)^{i-1-n}}G'(x)\)。
把这个 \(G(x)\) 塞进去再一起导，可以得到右式为 \((\sum\limits_{i=1}^n\frac{if_i}{i-n}(G(x)^{i-n})'[i\not=n])+nf_n\frac{G'(x)}{G(x)}\)。
我们考虑取 \(x^{-1}\) 的系数，注意到对于一个多项式求导一定不会出现 \(x^{-1}\) 这一项，所以只能由最后这个 \(nf_n\frac{G'(x)}{G(x)}\) 提供，这样将这一项暴力拆开就得到 $$[x^{-1}]\frac{G'(x)}{G(x)}=1$$，往回带计算就可以得到我们需要证明的东西。
然后是本题做法。
先考虑从小情况入手，比如 \(k=3\)，我们知道这个东西是卡塔兰数。考虑我们是如何解出来这个东西是卡塔兰数的，我们发现我们应该是直接考虑 \((1,2)\) 这一条边所在的多边形，把所有方案加总得到的。
那么对于更大的 \(k\) 同样计算，我们直接枚举剩余的部分分别划分为多少个 \(k\) 边形，可以写出柿子：$$a_n = \sum\limits_{x_1+x_2+\cdots x_{k-1}=n-1}\prod a_{x_i}$$。很容易写出来生成函数：$$F=1+xF^{k-1}$$。
如果 \(n\) 比较小感觉是可以递推计算的。但是 \(n\) 很大，到这里不会做了，不过我们看到有个前置知识拉格朗日反演，我们直接上拉格朗日反演：
这里 \(G\) 是 \(F\) 的复合逆，我们发现我们不会快速求复合逆（可能是可以的但是不需要），我们注意到 \(F=1+xF^{k-1}\) 这里有一个 \(x\)，所以我们直接挪一下，可以算出来 \(G=\frac{x-1}{x^{k-1}}\)。直接带入可以得到：
对于这个柿子直接用广义二项式定理展开即可，答案为 \(\frac1n(-1)^{(k-2)n+1}\frac{(-n)^{\underline{(k-2)n+1}}}{((k-2)n+1)!}=\frac{(kn)!}{n!((k-1)n+1)!}\)
对着这个柿子做就可以了，复杂度 \(O(n)\)。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1.1e6 + 5, N = 1.1e6, mod = 1e9 + 7;
int revjc[maxn], n, k;
void prepare() {revjc[0] = revjc[1] = 1;for (int i = 2; i <= N; i++)revjc[i] = (mod - mod / i) * revjc[mod % i] % mod;for (int i = 2; i <= N; i++)revjc[i] = revjc[i - 1] * revjc[i] % mod;
}
signed main() {int res = 0;prepare();while(cin >> n >> k) {int ans = revjc[n];for (int i = (k - 2) * n + 2; i <= (k - 1) * n; i++)ans = ans * i % mod;res = (res + ans) % mod;}cout << res << endl;return 0;
}