triangulation triangulation triangulation
Time Limit: 10000/5000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Today, I meet a difficult problem.
You are given three ints $n$, $x$, $y$. We have a regular n-gon: a convex polygon with $n$ sides, in which all sides have the same length and all internal angles are equal. We want to draw $n-3$ non-intersecting diagonals in some way. Once we do that, we will have the polygon divided into exactly $n-2$ triangles. We want to produce a situation in which one of these $n-2$ triangles has a $strictly$ larger area than each of the remaining $n-3$ triangles.
The vertices of the polygon are labeled $1$ through $n$ in clockwise order. Two sets of diagonals are different if one of them contains a diagonal that is not exist in the other one. Count all sets of $n-3$ non-intersecting diagonals that produce an arrangement with the above property. Output the number modulo $x$ multiple the number modulo $y$.
I can't solve it. Can you help me?
For example , the number of the first case is $(0\% 5)*(0\% 6)=0$,the number of the second case is $(5\% 6)*(5\% 7)=25$.
First line contains an integer $T$ ($T \leq 2$), the number of test cases.
For each test case, there are three numbers $n, x, y$ in a line separated by blanks ($3 \leq n \leq 400, 1 \leq x, y \leq 10^9$).
For each test case, print a single number in a line which is described above.
2017 ACM/ICPC Asia Regional Shenyang Online