| Submit | All submissions | Best solutions | Back to list |
DTPOLY2 - Divide Polygon (HARD) |
This is hard version of DTPOLY.
Determine the number of ways to cut a convex polygon with N vertices if the only cuts allowed are from vertex to vertex, each cut divides exactly one polygon into exactly two polygons, and you must end up with exactly K polygons. Consider each vertex distinct. For example, there are three ways to cut a square - the two diagonals and not cutting at all - but only two ways to cut it to form 2 polygons, and only one way to cut it to form 1 polygon. The order of cuts does not matter. Since the number of ways can be very large, you should return the number taken modulo M.
Input
Input contains several test cases, i-th line consists of 3 integers: Ni (3 ≤ Ni, ΣNi ≤ 108 over all test cases),
Ki (1 ≤ Ki ≤ Ni - 2) and Mi (1 < Mi < 260), all pairs (Ni, Ki) are different.
Output
On the i-th line print the number of different ways to cut the polygon with Ni vertices into Ki pieces modulo Mi.
Example
Input: 4 2 100 6 3 100 10000000 2 1000000007 10000000 5000000 1000000014000000049 Output: 2 21 984650007 780127215155143528
| Added by: | Michael Kharitonov |
| Date: | 2013-03-01 |
| Time limit: | 6s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
hide comments
|
2016-06-01 10:36:46 [Lakshman]
Can some one help me. What complexity we need to get AC for the hard version. Mine O(N * log num) where (num) is the largest number to be factored. =(Francky)=> Mine is O(N/log(N)) for each test case. No need to factor M ; use 64bit modular multiplications. Good luck. ==(Lakshman)=> Thanks for reply and sorry for creating confusion here M (just changed to num) is an intermediate number which I am factoring is is always less than 10^8. I will try to improve my algo to get AC. Last edit: 2016-06-01 13:22:36 |
|
|
2014-09-04 18:32:59 Francky
Yeah!!! AC at first attempt, I could pass the 10(?) test files without too much optimizations, now is time for opti. The problem is very nice and I don't know problems here with a similar way to the green AC. Thanks a lot. --ans:--> Congrats for first AC. The code can be simpler))) Last edit: 2013-03-15 13:23:48 |
|
|
2014-09-04 18:32:59 [Rampage] Blue.Mary
1. You may create a new problem rather than simply change the problem description. 2. I don't like this kind of constant optimization problem. As you can see, the 1st program I submitted (for previous task) only exceed the time limit for .01 sec. It's so boring. I used to be a problem setter like you. However now the time limit for problems added by me is always at least 10*(my program without any constant optimization). Maybe many people like this, but I'm not. ans: Your problem exceeded for .01 sec on the new tests. However, TL raised. Last edit: 2013-03-06 08:16:28 |
|
|
2014-09-04 18:32:59 Francky
@ Michael K.: You just have to accord the example with some moduli. <fixed> And, could you tell what is the constraint for the number of lines, please. ans: the constraints for N,K => the constraint for number of lines. (Fr)--> Sorry if we misunderstood, I would like to know the maximum number of lines. ans: all pairs (N,K) are different => number of lines are not so big. Edit : now I see the little sigma, and I have a decent bound for test cases. OK. Last edit: 2013-03-06 17:59:39 |
RSS