#PQJ1190x6170. QOJ 1190_6170

    ID: 2562 传统题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:FJOI 2020组合数学

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。