QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

# 6170. 凸多边形正则划分问题

统计

凸多边形正则划分问题:对于给定的 $n$ 和 $k$,求一个凸 $nk-2(n-1)$ 边形的 $k$ 角剖分的方案数,对 $10^9+7$ 取模。

输入格式

每个测试点中包含多组测试数据。

输入的第一行包含两个整数 $n, k$。

输出格式

输出一行一个整数,表示所有询问的答案之

样例数据

样例输入

2 3
3 3
3 4

样例输出

19

子任务

对于 $50\%$ 的数据,$n \leq 5\,000$。

对于 $100\%$ 的数据,$k \leq 200, n \leq 1\,100\,000$

  1. 赛时并未提供数据组数,“请选手自行评估”。
  2. 赛时并未提供 $k$ 的下界,且出题人答疑时声称并不保证(尽管数据里没有)$k \nleq 2$。
  3. 赛时并未提供空间限制,“请选手自行评估” QOJ 上设置为 1 GB。