3048:XX’s puzzle

题目描述
XX and QQ are good friends. Some few months ago, XX always sat beside QQ and they always talked about some hard programming problems and also sometimes played StarCraft (∩_∩). XX likes playing Protoss while QQ likes playing Terran, and XX is a perfect player and courage QQ to win the others. But now, XX has gone to ZJU to study master, so QQ always thinks of him. XX is a mischievous boy, and he invariably comes up with lots of hard problems to challenge QQ, but fails at the most time. In the recent days, XX finds a problem which he regards as a very puzzling problem. Being surprised by QQ’s skill, XX is determined to let you solve this problem and tests whether the problem is enough puzzling, the problem is described:
It's not hard to see that every triangulation breaks the polygon into n-2 triangles. The triangulation is called k-isosceles, if there are exactly k isosceles triangles among them. Given integer n and k, compute the number of distinct k-isosceles triangulations of a regular polygon with n vertices. Return the result modulo 9397.
输入解释
There are many test cases.
For every case, there are two nonnegative integer n and k, 3<=n<=50, 0<=k<=n-2;

输出解释
For every case, output the result modulo 9397.
输入样例
4 2 
3 0 
5 3 
输出样例
2
0 
5
提示
Hint: 
For the first case, we can have a diagonal between vertices 0 and 2 or between vertices 1 and 3. In both cases, there are 2 isosceles triangles.
For the second case, the only triangulation of an equilateral triangle contains no diagonals and 1 isosceles triangle (the polygon itself).
For the third case, a regular pentagon has 5 triangulations. 
Each of them is obtained by connecting one selected vertex with the two others that are not its neighbors, so each triangulation is 3-isosceles.
来自杭电HDUOJ的附加信息
Recommend gaojie

该题目是Virtual Judge题目,来自 杭电HDUOJ

源链接: HDU-3048

最后修改于 2020-10-25 22:59:34 UTC 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
10000/5000MS(Java/Others) 32768/32768K(Java/Others)

·

·

·

·

登陆或注册以提交代码