#PQJ1190x6170. QOJ 1190_6170
QOJ 1190_6170
凸多边形正则划分问题:对于给定的 𝑛 和 𝑘 ,求一个凸 𝑛 𝑘 − 2 ( 𝑛 − 1 ) 边形的 𝑘 角剖分的方案数,对 10 9 + 7 取模。
输入格式
每个测试点中包含多组测试数据。
输入的第一行包含两个整数 𝑛 , 𝑘 。
输出格式
输出一行一个整数,表示所有询问的答案之和。
样例数据 样例输入 2 3 3 3 3 4 样例输出 19 子任务
对于 50 % 的数据, 𝑛 ≤ 5 000 。
对于 100 % 的数据, 𝑘 ≤ 200 , 𝑛 ≤ 1 100 000
注 赛时并未提供数据组数,“请选手自行评估”。 赛时并未提供 𝑘 的下界,且出题人答疑时声称并不保证(尽管数据里没有) 𝑘 ≰ 2 。 赛时并未提供空间限制,“请选手自行评估” QOJ 上设置为 1 GB。