首页 > ACM题库 > HDU-杭电 > hdu 3048 XX’s puzzle待解决[解题报告]C++
2014
02-27

hdu 3048 XX’s puzzle待解决[解题报告]C++

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;

输出:

There are many test cases.
For every case, there are two nonnegative integer n and k, 3<=n<=50, 0<=k<=n-2;

样例输入:

4 2 
3 0 
5 3 

样例输出:

2
0 
5
Hint
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.