Swarm of PolygonsProblem code: SWARM |
All submissions for this problem are available.
There is a regular n-gon. Some points are marked on each of its sides. There are x1 point marked on the first side, x2 on the second, , xn on the nth. The marked points do not coincide with the vertices of the n-gon. You can choose no more than one of the marked points from each side and form a convex non-degenerate polygon by connecting all those points with lines. Now your task is to find the number of different k-gons that can be formed that way.
Input
The first line of input file contains positive integer t the amount of test cases. Next t lines contain six integers each: n, k, a, b, c, m. Here n is the number of sides of the initial n-gon. The amount of marked points on the first side of this n-gon is x1 = a, the amount of the marked points on the following sides is xi = (b*xi-1 + c) mod m, for i > 1.
Constraints
1 <= t <= 30
3 <= n <= 109
3 <= k <= 20
1 <= b, c, m <= 106
0 <= a < m
Output
For each test case output the number of k-gons that can be formed modulo 1000000007.
Example
Input: 2 4 3 1 2 2 191 10 5 1 113 157 999991 Output: 1228 328836201
| Author: | spooky |
| Date Added: | 13-04-2010 |
| Time Limit: | 10 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
what is the meaning of non
what is the meaning of non degenerate?
anyone please explain.
@atul the vertices do not
@atul
the vertices do not coincide, the adjacent sides do not form a 180 or 0 degree angle. generally it's just a normal polygon
is the reqd.. output (no. of
is the reqd.. output (no. of k-gons)mod1000000007
@vijay yes
@vijay
yes
Can the official solution
Can the official solution handle 30 worst-case tests in under 10 seconds, or does it make some assumptions that the input will never be anything near that worst case? (And if so, what assumptions?)
@Stephen Yes, it can. No
@Stephen
Yes, it can. No assumptions. Everything in the statement.
Is O(m*k^2) enough to pass
Is O(m*k^2) enough to pass the tests? I didn't manage to code this in time.
Mine was O(mk + k^2).@Ivan
Mine was O(mk + k^2).
@Ivan Mistreanu: your comment really confused me. Even the fastest submission for this problem doesn't come close to running 30 worst-case tests within the time limit (1000000000 20 1 5 1 999983). I asked because a simple loop like this:
for (int i=0; i<30; i++)
for (int j=0; j<20; j++)
for (int k=0; k<999983; k++) {
// any line like one multiplication mod m
}
doesn't run in 10 seconds on the judge, let alone an actual solution. I was 99% sure that there couldn't possibly be a faster solution than O(mk), but mine took about 2-3 seconds on the judge per test case in the worst case, so I was very surprised to see it passing.
Can't wait to see the official solution, I'm either going to be extremely impressed or extremely disappointed..
I am curious what the
I am curious what the official solution is. Mine was O(m*k + k^3) and i had to get down and dirty with asm to get it correct :)
@Stephen, same case here, I
@Stephen, same case here, I did similar timing tests and felt that it depended on the input distribution. Ivan's comment not withstanding, I figured my solution was just a little bit slower. So, asm it was for me.
This is what i figured out: long long modulus is VERY expensive compared to integer modulus. gcc generates a library function call __moddi3 apparently. But, in the restricted case that the modulus is a 32 bit integer (the MOD), you can actually do modulus of 64 bit dividend and 32 bit divisor in one instruction. That got me running in time.
i had O(m*k+k^2) and i was
i had O(m*k+k^2) and i was getting TLE in C++ but when i changed it to C it got AC.
O(m*k + k*k*ln n) is enough
O(m*k + k*k*ln n) is enough to pass all tests, while O(m*k + k*k*1000) is not enough.
It is confusing that someone need optimize second part of solution (O(k*k*1000)), while in worst case (some example is "1000000000 20 1 1 1 1000000") slowest part will be m*k, which is not possible to run for 30 test cases within 10 seconds.
@Stephen Sorry, that this
@Stephen
Sorry, that this confused you. You probably will be dissapointed. I also doubt there is a solution better than O(mk). I can only say that there was a test case close to maximum test case and we sey the TL about 1.5 times of the official solution.
OK, so the official solution
OK, so the official solution can't handle the worst case like you said it did :( Can I request that in future the author's solution can solve the problem as stated; I spent many many hours trying to work out how to make my program faster than O(mk) since I knew that had no hope of passing based on the constraints + what you said.