ADASQR - Ada and Squares
As you might already know, Ada the Ladybug is a farmer. She has a beautiful square field (of size NxN) in which she grows many beautiful plants. Each plant has some height. She wants to know, for each subsquare (of some defined size KxK) what is the minimal sized plant in it. As she doesn't want too many information, she only asks you for the sum of all such lowest plants.
As it is mentioned above, she doesn't like "too many information" so she also comprimed the heights for you. For each of the N rows, you wll be given 4 integers x0 a b c. The rest of the row (N-1 plants) could be obtained as xi+1=(xi*a+b)%c.
Input
The first line will contain two integers N, K: 1 ≤ K ≤ N ≤ 5000, the size of field and the defined size of subsquare.
The next N lines will contain four integers 0 ≤ x0, a, b, c ≤ 1018 (c ≠ 0), which will generate the ith row.
Output
Output the sum of minimal heights of each subarray of size KxK. As it might be pretty big, output the number modulo 109+7 (1000000007).
Example Input
4 2 8 2 9 9 5 7 9 3 9 7 7 5 7 4 7 3
Example Output
6
Real Field
8 7 5 1 5 2 2 2 9 0 2 1 7 2 0 1
Example Input 2
10 8 78 51 99 77 27 95 37 80 76 5 93 32 92 48 56 64 93 17 18 28 70 30 15 73 60 69 36 56 12 11 63 57 18 81 55 60 59 92 68 81
Example Output 2
18
Real Field 2
78 73 49 57 3 21 15 17 42 8 27 42 27 42 27 42 27 42 27 42 76 25 26 31 24 21 6 27 4 17 92 56 56 56 56 56 56 56 56 56 93 3 13 15 21 11 9 3 13 15 70 71 28 52 42 34 13 40 47 38 60 32 4 32 4 32 4 32 4 32 12 24 42 12 24 42 12 24 42 12 18 13 28 43 58 13 28 43 58 13 59 69 17 12 38 0 68 6 53 3
Example Input 3
20 5 2956 1596 6710 2713 2626 2791 1425 3859 1874 6262 3248 2238 5856 4491 7062 2271 2722 1707 9943 7035 403 2209 7057 1975 7211 9708 3898 6949 2426 9144 8440 2974 5034 3983 6243 7717 3877 37 9002 7373 3021 2549 7277 5516 3673 9640 7775 5355 1563 9728 6671 5484 4342 2971 1237 6834 3589 3662 5391 9672 780 6008 5239 304 5095 4370 280 9403 6295 118 822 2545 5649 2519 5412 6501 2901 2829 9801 846
Example Output 3
38811
Example Input 4
30 8 42190820083565085 13910582960072682 404339598526125697 18330389877395687 13136432922739892 360508552206096544 840939247896706683 166851773518294104 195629367891644832 133017412681920741 791801761173755587 953548694494513035 930566226452148080 212263842828807811 175150807852323258 261521670663969864 223183990889228375 549657188306426129 227104892059916771 710982591168543028 622099644118414985 984577533571891185 802914550839341535 577466815316077292 363883415474075556 913215986569797 257759523922291507 129711072317319582 472381530848232370 587974020968388203 95939647385371737 421772367107774947 870958993881230243 98076059799725034 955829596729745763 73827358022047846 50043465537791007 178000244851301580 686791668222702403 230423627799787034 41761070639181344 703749524391633426 575680731101407438 948818018258441027 74006463131502635 534256412790647769 117842073420805101 689203117404347787 720627491787492218 206756570671097114 5074687913252083 402683208709668506 583558162725379851 516050342346753246 792500576162473842 130741479957823970 709539139438259321 132262390506172747 780941668119266465 575886488550729150 518457490774399283 781644026117044419 451050302936677524 319690456859518311 747952274084607955 433194299929591864 829471355224525516 87759356942462111 472230421696663981 150197958929639709 699963373353260575 156451405305679606 379767724942828073 307602673656652612 536339937437228412 450095461910438107 130196535602142550 12133076804665744 944874740331622465 112002748054899251 384924669386020020 895364022010504585 562727215734096434 364228612518853658 2558159832040223 42876494731943717 303029667687965036 370694399470107119 801915657644445462 610444723365908160 304599053734522278 593616674445351229 318887526987442235 390853723621574162 339872209606293879 308835452771750585 476033942116470840 213009419015490269 20470342994674399 282092030038623628 582424275023334455 712867665674241464 17697708714929958 654849385199113364 475223303973240030 425222042042672679 12723252770801578 591938517391534160 538033927835846645 318295777283007977 593613359214212470 772515434523625506 612174705584217229 415458073586196348 508007743847849815 965297054583491903 179981864970425260 975763652798172152 215122546620747273 113899093042760092
Example Output 4
641904340
hide comments
|
morass:
2017-10-19 21:17:34
@Rishav Goyal: Great you figuredit out! And also glad it was helpful ^_^ So congratulations & Have Nice Day ^_^ |
|
Rishav Goyal:
2017-10-19 19:37:47
@morass : Your comment was quite helpful. Thanks :) |
|
|
morass:
2017-10-18 23:23:38
@Rishav Goyal: Good day to you. Well I strongly agree that your algorithm is "fine". Anywy for this problem the "so called" imput storage is also part of problem. It can be solved in O(N^2) yet your "algorithm" doesn't fulfill this :'( Anyway I'm sure tht if you will improve your "mulmod" function (optimal is to O(1)) you will get AC :) So to sum it up, it is not about "big constant" but "unwanted" logarithm :)
|
|
|
Rishav Goyal:
2017-10-18 20:17:24
@time limit does not allow even input storing complexity. such issues always spoil the problems. should not spoj allow a big constant to pass the time-complexity so that people can focus on the real logic? for ex. like Codeforces. |
|
|
morass:
2017-10-14 19:37:09
@mahmud2690: 10^9+7, thank you (fixed :) ) |
|
mahmud2690:
2017-10-14 17:28:14
Is modulo equal to 10^9 + 7 or 10^10 + 7?. Please, make it clear in the statement. |
|
|
morass:
2017-10-14 02:01:22
@[Rampage] Blue.Mary:
|
|
[Rampage] Blue.Mary:
2017-10-14 01:57:28
1. The first line contains two integers N and K, not K and N.
|
| Added by: | Morass |
| Date: | 2017-10-13 |
| Time limit: | 4s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
RSS