Problem Statement
Use the following instructions to determine the coloring of the board. You are given
X[0] = X0 MOD N
X[i] = (X[i-1]*A+B) MOD N
Y[0] = Y0 MOD N
Y[i] = (Y[i-1]*C+D) MOD N
For each i between 0 and M-1, inclusive, the cell at column X[i], row Y[i] is black. The remaining cells are white.
Let's denote the score for the cell at column i, row j as score(i, j). Return the sum of score(X[i], Y[i]) for all i between M and M+K-1, inclusive.
Definition
- Class:
- CellScores
- Method:
- countScores
- Parameters:
- int, int, int, int, int, int, int, int, int
- Returns:
- long
- Method signature:
- long countScores(int N, int M, int K, int X0, int A, int B, int Y0, int C, int D)
- (be sure your method is public)
Constraints
- N will be between 1 and 1,500, inclusive.
- M and K will each be between 0 and 1,000,000, inclusive.
- X0,Y0,A,B,C,D will each be between 0 and 1,500, inclusive.
Examples
10
0
1
0
1
1
0
1
1
Returns: 100
The whole board is white. You are interested in cell (0,0). The score for this cell is 100.
10
1
1
5
1
5
5
1
5
Returns: 75
Only the cell (5,5) is black. You are interested in cell (0,0). The score for this cell is 75.
7
4
3
0
1
1
0
1
1
Returns: 194
The first 4 cells on the diagonal are black, and you are interested in the other 3 cells on the diagonal.
23
10
30
26
48
76
231
463
707
Returns: 8088
211
30
12
3
35
82
0
43
15
Returns: 18196443
1498
19677
911056
215
114
610
17
1071
637
Returns: 7387463034
1416
7774
536097
302
658
101
267
827
311
Returns: 34425974016
1340
57012
919931
625
202
131
816
516
261
Returns: 0
295
27530
562253
157
1371
1219
1008
532
1411
Returns: 2738615
1381
260824
808034
250
1083
833
1272
1382
502
Returns: 98606712
1438
48578
523417
470
773
284
833
720
664
Returns: 36635148768
1431
46263
43977
1060
425
1392
899
67
1145
Returns: 189103509
1451
804634
685095
336
1
33
749
724
320
Returns: 7097842
1357
26856
500284
921
1231
517
985
296
269
Returns: 3268732180
1498
32568
350725
563
516
797
1374
1499
1094
Returns: 2904720860
1355
55590
281205
650
1356
421
420
186
689
Returns: 941581612
1133
28465
152038
97
207
181
1435
1229
440
Returns: 155054988
1401
336759
277837
503
468
606
546
10
584
Returns: 0
1357
4491
312356
1356
296
182
567
781
1187
Returns: 134280094752
1446
21373
427603
783
1267
71
221
1
628
Returns: 5264736220
1457
23276
310573
731
894
761
167
265
162
Returns: 2073438470
1494
10909
763019
1405
748
271
472
199
1068
Returns: 44471270100
1407
13282
869465
1026
1
573
283
165
722
Returns: 10563854508
1317
71915
177655
451
427
85
1465
879
1002
Returns: 36852672
1497
159115
93166
213
1210
1048
749
1498
562
Returns: 49745736
1393
64852
97218
1337
1492
1484
265
1394
814
Returns: 145044991
1359
25610
765505
1439
1209
1200
1414
954
290
Returns: 0
1493
418490
227658
1466
850
172
916
1494
172
Returns: 8111314
1309
53090
138211
1432
41
1100
743
375
1311
Returns: 0
1357
24968
710260
860
1146
210
579
591
1486
Returns: 4557019793
1498
43677
895536
73
857
775
814
46
1197
Returns: 0
1435
37508
160946
292
299
65
1053
862
489
Returns: 0
1199
34662
393736
1434
655
1122
552
1221
349
Returns: 0
1445
21740
773412
468
428
1152
993
936
1143
Returns: 1543991306
1322
44088
722321
1497
662
1321
933
877
653
Returns: 201407438830
1076
47617
483582
5
1067
493
1352
1077
1381
Returns: 157427151
1471
920089
927510
546
1472
677
54
207
789
Returns: 916555
1474
19549
202911
250
117
320
483
1207
1213
Returns: 956673040
1235
25230
231210
176
1267
648
994
1236
602
Returns: 294434378
1450
10299
172817
758
627
535
784
1
526
Returns: 18493437726
1321
195533
462590
304
483
928
23
1
1314
Returns: 0
1414
30140
910545
145
351
1463
659
607
177
Returns: 34963908
1315
164570
101756
883
790
744
1063
547
910
Returns: 0
1494
4598
750294
639
9
759
1228
1
271
Returns: 1442474625168
1446
62907
737984
369
483
725
415
292
1173
Returns: 0
747
16635
641759
353
778
697
932
333
472
Returns: 290597328
1415
66004
714481
750
850
1365
825
676
83
Returns: 1310376890
1419
31079
677605
16
1365
571
779
689
1418
Returns: 232208361
893
139056
417538
339
11
1249
328
1
732
Returns: 0
841
30216
391610
282
755
453
119
820
201
Returns: 0
1492
127150
559609
1244
1105
1022
968
1493
676
Returns: 14507200
1371
270830
981047
799
458
346
629
78
930
Returns: 0
1497
84718
795446
971
1
987
1329
394
1073
Returns: 781847850
1495
40131
60975
451
1197
112
1105
1480
326
Returns: 0
1457
20256
508682
34
737
44
1306
142
665
Returns: 8173851824
3
0
100
0
0
0
0
0
0
Returns: 900
1500
1499
1000000
1498
1
1499
0
1
1
Returns: 750875250
1500
1499
1000000
1499
1
1499
1
1
1
Returns: 750875250
1500
1499
1000000
0
1
1
1
1
1
Returns: 750875250
1500
1499
1000000
1
1
1
0
1
1
Returns: 750875250
2
0
1
620
732
1030
232
873
1132
Returns: 4
10
4
8
346
680
1454
1226
1041
19
Returns: 700
7
3
17
1304
206
702
853
314
1466
Returns: 357
5
12
4
248
1016
291
409
97
937
Returns: 12
7
1
41
907
1095
726
826
769
1011
Returns: 4242
1
0
1
1220
719
1474
176
892
363
Returns: 1
3
1
1
1437
163
616
757
1020
1418
Returns: 8
4
1
2
299
531
30
1166
140
815
Returns: 8
1
0
1
849
1060
270
620
94
245
Returns: 1
3
0
5
843
10
496
34
295
308
Returns: 57
4
0
16
771
1359
1060
1073
795
706
Returns: 480
5
2
2
1340
1159
171
1026
1295
1482
Returns: 3
3
0
1
80
1417
168
1439
720
610
Returns: 9
5
1
8
1362
1405
1270
300
1410
997
Returns: 288
3
1
5
719
1153
170
850
1362
623
Returns: 33
2
0
1
1102
1233
806
811
8
1144
Returns: 4
9
5
74
298
427
817
1449
211
1248
Returns: 2460
2
0
2
800
214
1301
447
1432
1405
Returns: 8
3
3
8
59
535
749
849
876
307
Returns: 6
7
2
6
513
1180
627
502
1428
1496
Returns: 48
10
3
4
739
247
75
283
1293
279
Returns: 228
1
0
1
1259
1222
1328
347
1201
1246
Returns: 1
3
1
3
53
80
266
970
1106
966
Returns: 14
2
1
4
710
356
552
860
1197
599
Returns: 4
1
0
1
123
1237
1101
1215
490
198
Returns: 1
3
0
1
1332
716
1109
1442
1257
21
Returns: 9
7
14
49
548
1380
51
1280
1066
791
Returns: 276
5
2
6
1036
64
1289
851
1101
347
Returns: 88
6
1
14
852
25
703
793
559
1476
Returns: 830
2
0
3
536
1066
1063
1459
686
504
Returns: 12
2
1
4
1028
711
1436
274
1066
341
Returns: 8
4
2
15
159
274
548
353
979
410
Returns: 180
8
3
45
296
585
282
1234
826
779
Returns: 6214
10
1
23
1062
1394
1067
644
49
1386
Returns: 10350
2
0
1
430
1120
286
1016
280
1456
Returns: 4
7
0
10
180
549
1215
737
884
881
Returns: 1728
7
10
44
24
543
710
102
15
3
Returns: 124
3
0
8
1416
150
449
635
218
595
Returns: 72
2
0
4
1001
980
836
780
635
1092
Returns: 16
5
1
16
105
623
645
996
1144
1496
Returns: 40
6
0
8
786
1461
655
193
867
1492
Returns: 760
1
0
1
1457
1072
1371
492
1393
1424
Returns: 1
4
0
11
89
877
852
1286
870
1280
Returns: 276
4
1
13
12
626
860
865
375
19
Returns: 56
2
0
4
647
1116
30
1077
62
640
Returns: 16
4
0
7
652
98
671
744
337
531
Returns: 188
6
0
9
1067
349
241
734
385
685
Returns: 732
6
0
28
1002
1042
699
1052
240
794
Returns: 3960
9
7
55
1355
1249
1417
1036
1317
1317
Returns: 852
3
2
1
351
838
485
359
14
1142
Returns: 5
1498
41
4580
1139
723
1075
420
1461
1445
Returns: 15640991606039
1491
9
1000000
1011
922
1159
1234
919
1420
Returns: 21829315775061514
1493
0
28
1292
894
608
393
360
1402
Returns: 3961348964953
1493
61
1301
1428
1479
270
1299
456
1307
Returns: 2103351658027
1499
0
77767
594
845
824
1347
1452
1500
Returns: 11318391040188715
1491
4
9
396
1188
1426
1356
63
131
Returns: 386210801760
1494
8
77
668
285
426
160
207
749
Returns: 2839258610448
1499
67
2
295
1024
1265
298
428
1309
Returns: 4086941400
1493
64
84
1375
259
1362
863
1028
647
Returns: 157357586889
1493
196
390235
805
1220
1190
1332
893
990
Returns: 102733363312109
1493
116
342
437
1359
593
1041
407
1082
Returns: 231513234652
1497
378
1000000
261
843
1127
741
1160
1246
Returns: 29833782946758
1499
443
1000000
805
234
315
534
126
1421
Returns: 62824123631887
1496
659
646755
858
52
1497
1043
450
788
Returns: 348921008128
1493
444
5513
767
884
1
734
940
457
Returns: 336581831721
1494
571
295770
964
1052
830
648
826
1205
Returns: 3771882712904
1500
190
617708
1300
609
362
699
985
427
Returns: 51055717723170
1496
628
886
79
1406
960
669
584
12
Returns: 8030743608
1500
313
1000000
686
16
683
651
263
359
Returns: 118162999881060
1493
828
4568
860
221
1456
1229
655
672
Returns: 62649927755
1493
1341
1000000
1020
45
1247
1109
135
1358
Returns: 1246715764228
1499
264177
740768
1323
1500
1291
1460
1298
1252
Returns: 85909800
1499
1285
381499
1306
1126
623
864
1424
202
Returns: 811395283185
1493
1445
6259
1417
713
1332
625
361
137
Returns: 2477075695
1498
5437
8529
706
178
267
575
1285
752
Returns: 3692121904
1499
1377
7506
617
1429
776
1123
692
484
Returns: 6576450107
1497
28912
278025
587
1
306
1393
105
683
Returns: 2027065968
1496
6974
64369
113
58
832
265
1310
1051
Returns: 4108249600
1494
4599
1000000
76
748
1048
92
916
643
Returns: 702852262556
1494
44783
556080
950
738
1241
763
250
154
Returns: 552981780
1498
10812
1000000
20
1028
1440
1158
1499
848
Returns: 9836141860244
1494
42148
90975
1141
908
1500
323
1495
1337
Returns: 192477204
1492
18574
1000000
1293
374
774
1405
248
1121
Returns: 10528677984
1493
1000000
404874
1044
380
849
1278
1
854
Returns: 4104291
1497
93038
1000000
59
999
587
1336
511
31
Returns: 1366161492
1490
13534
253203
733
378
1065
140
150
1113
Returns: 2839954560
1493
978793
1000000
715
1494
1469
726
894
857
Returns: 9294732
1492
64530
1000000
452
374
1485
81
452
156
Returns: 849209712
1493
1000000
554771
619
1336
54
745
1
472
Returns: 3634182
1493
1000000
650723
96
1186
837
143
1494
1157
Returns: 3971833
1499
1000000
426717
1073
509
981
527
1
1210
Returns: 2835366
1493
747640
570671
8
1494
1056
1312
38
924
Returns: 159051151
1493
173992
1000000
1249
1207
1111
713
1
903
Returns: 364268991
1499
275864
1000000
1146
1500
976
19
415
1094
Returns: 386123602
1490
107163
1000000
433
1193
212
36
961
384
Returns: 12700320
1499
1000000
1000000
493
1500
1041
484
304
113
Returns: 244849938
1499
835700
1000000
405
1
1409
488
1480
1424
Returns: 2066568
1493
120355
581218
1294
231
1053
728
1
216
Returns: 399677354
1499
1000000
270118
609
1
214
66
304
1121
Returns: 780999967
1499
732544
961087
969
1
1404
28
923
87
Returns: 42460335
499
10000
1000000
1
154
985
1
500
1166
Returns: 1623652789
1500
1000000
1000000
281
121
121
198
118
918
Returns: 0