DTPOLY2 - Divide Polygon (HARD)

no tags 

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 contains several test cases, i-th line consists of 3 integers: Ni (3 ≤ Ni, ΣNi ≤ 108 over all test cases),

Ki (1 ≤ K≤ N- 2) and Mi (1 < Mi < 260), all pairs (Ni, Ki) are different.


On the i-th line print the number of different ways to cut the polygon with Ni vertices into Ki pieces modulo Mi.


4 2 100
6 3 100
10000000 2 1000000007
10000000 5000000 1000000014000000049

hide comments
[Lakshman]: 2016-06-01 10:36:46

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
[Rampage] Blue.Mary: 2014-09-04 18:32:59

OK, finally got Accepted after changing my algorithm. BTW, the precision issues in this problem is so strange...
--ans--> Nothing strange. In your WA you have error.

Last edit: 2013-03-25 08:24:18
Francky: 2014-09-04 18:32:59

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
[Rampage] Blue.Mary: 2014-09-04 18:32:59

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
Francky: 2014-09-04 18:32:59

@ 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

Added by:Michael Kharitonov
Time limit:6s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)