CountSubarrays
TCO19 SRM 749 · 2019-01-09 · by Blue.Mary
Problem Statement
You are given an array A containing N elements. You are also given an integer X. Count the number of ordered pairs (L, R), such that:
- 0 ≤ L ≤ R < N.
- (A[L] * A[L+1] * ... * A[R]) modulo 744,444,499 = X.
The array A is given in the following format: You are given the
for i = 0 to length(Aprefix)-1:
A[i] = Aprefix[i]
for i = length(Aprefix) to n-1:
A[i] = ( A[i-length(Aprefix)] * a + b ) modulo m
Constraints
- n will be between 1 and 94,749, inclusive.
- Aprefix will contain between 1 and n elements, inclusive.
- Aprefix will contain at most 200 elements.
- Each element of Aprefix will be between 0 and 744,444,498, inclusive.
- m will be between 1 and 744,444,499, inclusive.
- Each of a and b will be between 0 and m-1, inclusive.
- X will be between 0 and 744,444,498, inclusive.
{2,1,2}
3
5
7
11
2
Returns: 4
We are looking for all subarrays of {2,1,2} that have product (modulo 744,444,499) equal to 2. There are four such subarrays. The corresponding pairs (L,R) are (0,0), (0,1), (1,2), and (2,2).
{1}
3
0
0
744444499
0
Returns: 5
The array you should generate is {1,0,0}, and we are counting subarrays whose product is 0. There are five such subarrays: all of them, except for (0,0).
{332561219,121884851,427632830,369957091,549417829,685227621,436551677,351304445,243813223,371998688}
94749
330563283
311776610
744444499
222370756
Returns: 8
{35828110,300357300,191011600,527986654,415569791,725672838,190156296,463922833,573251140,479251458,49076642,305285101,226658648,535061251,340108009,337072284,324710641,197385849,691064495,486979567,233626036,510537426,329787224,540184586,552934843,473485542,162834789,319948368,177935440,543937403,236082224,698309840,681221525,437102554,349926815,15236521,142872311,504082258,612944708,94456611,222664208,27773577,194613842,103338974,270702420,334463309,577120441,232099245,606615432,543411229,535242657,651415329,462235251,552781226,255220605,686019139,63153350,284507479,639257318,427922808,719983500,238084469,661213618,191288994,366182406,521203673,199578216,162038913,115677507,420719156,225954897,390528592,533997682,21505642,327643990,637337490,158079254,324299791,455651610,202660228,501706940,640968709,181429278,353863711,185780035,477690014,383281213,281352956,443140453,346417612,419464686,158201693,194549867,318373691,237906359,567594330,354823318,196740282,577879399,370429071}
94749
278084788
265616225
744444499
607723945
Returns: 3
{476954577,370173635,30905049,722823112,578527209,229685557,498220579,253798363,689274976,422746075,274045439,49053368,39267706,682430721,106098889,115383543,589046807,409120140,532408504,51397597,673588242,560973763,73143982,350002329,321525875,346463645,318978921,2021102,90971253,460183324,596452415,584608960,97770626,471072653,54383122,296125193,403426787,401293411,336295522,726662999,203484631,42849260,163678066,50651358,341560741,465391343,230266416,402567647,230854868,344828799,490251686,537905734,322387272,501177102,512529640,165488371,81011741,333652400,398785182,280175080,628346239,211709077,338270907,206884971,14083111,357274768,266703079,369892674,679318196,716905393,115914632,277584988,296815088,249985280,567506266,164053008,631666933,138278535,404113742,75337621,720573544,716237219,306987375,91849629,585591625,606401480,500917857,529248811,527437200,30485750,377849398,8137133,447742270,302689726,714466757,106079022,230431795,554038095,574951280,399317628}
94749
138316247
79107884
744444499
347061333
Returns: 2
Submissions are judged against all 29 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class CountSubarrays with a public method long long count(vector<int> Aprefix, int n, int a, int b, int m, int X) · 29 test cases · 2 s / 256 MB per case