QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100
[+3]

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

Statistics

凸多边形正则划分问题:对于给定的 nk,求一个凸 nk2(n1) 边形的 k 角剖分的方案数,对 109+7 取模。

输入格式

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

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

输出格式

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

样例数据

样例输入

2 3
3 3
3 4

样例输出

19

子任务

对于 50% 的数据,n5000

对于 100% 的数据,k200,n1100000

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