TaleOfTwoSquares
SRM 790 · 2020-09-09 · by nikhil_chandak
Problem Statement
The time limit is 4 seconds.
A sequence is called good if its product can be expressed as the sum of two squares. For example:
- {1, 1, 1} is good because 1*1*1 = 1 = 0^2 + 1^2.
- {6, 164, 15} is good because 6*164*15 = 14760 = 42^2 + 114^2.
- {2, 3} is not good because 2*3 = 6 and it is not possible to write 6 as the sum of two squares.
A subsequence of a sequence X is any sequence that can be obtained by erasing zero or more elements of X, while maintaining the order of the remaining elements. Two subsequences of the same sequence are distinct if they correspond to erasing elements at different indices.
You have an array A of size N. The elements of A are positive integers.
You are also given a collection of Q queries. For the i-th query, consider the sequence A_i formed by the elements of A at indices from QL[i] to QR[i], inclusive. The answer to the i-th query is the number of non-empty good subsequences of the sequence A_i.
Calculate answers to all the queries, and return their sum modulo 998,244,353.
To keep the input size small, you are only given prefixes of A, QL, and QR in the
state = seed
A = Aprefix
while length(A) < N:
state = (state * 1103515245 + 12345) modulo 2^31
A.append( 1 + state modulo 10000000)
QL = QLprefix
QR = QRprefix
while len(L) < Q:
state = (state * 1103515245 + 12345) modulo 2^31
x = state modulo N
state = (state * 1103515245 + 12345) modulo 2^31
y = state modulo N
QL.append( min(x,y) )
QR.append( max(x,y) )
Constraints
- N will be between 1 and 10^5, inclusive.
- Aprefix will have between 0 and min(100,N) elements.
- Each element of Aprefix will be between 1 and 10^7, inclusive.
- Q will be between 1 and 10^5, inclusive.
- QLprefix will have between 0 and min(100,Q) elements.
- QRprefix will have the same number of elements as QLprefix.
- For each valid i, 0 <= QLprefix[i] <= QRprefix[i] <= N-1.
- seed will be between 0 and 2^31 - 1, inclusive.
8
{1, 1, 1, 6, 164, 15, 2, 3}
3
{0, 3, 6}
{2, 5, 7}
0
Returns: 11
In this example we are given the entire arrays A, QL, QR. There are three queries. Query 0 asks about the sequence {1, 1, 1}. Each of the 7 non-empty subsequences of this sequence is good. Query 1 asks about the sequence {6, 164, 15}. Only the subsequences {6, 15}, {164}, and {6, 164, 15} are good. Query 2 asks about the sequence {2, 3}. Only the subsequence {2} is good. The sum of answers to all queries is therefore 7 + 3 + 1 = 11.
40
{2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}
300
{}
{}
47
Returns: 800453880
All non-empty subsequences of each sequence are good.
14
{47, 12345}
5
{4, 5}
{6, 7}
47
Returns: 11
You should have the following arrays: A = {47, 12345, 5621309, 3614406, 1878299, 854092, 6820649, 3962434, 1250151, 3983528, 7736277, 8477438, 9514867, 2640324} QL = {4, 5, 5, 1, 3} QR = {6, 7, 8, 6, 6}
100000
{}
100000
{}
{}
47
Returns: 15457790
98997
{}
99898
{}
{}
436437432
Returns: 33172965
Submissions are judged against all 37 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TaleOfTwoSquares with a public method int count(int N, vector<int> Aprefix, int Q, vector<int> QLprefix, vector<int> QRprefix, int seed) · 37 test cases · 2 s / 256 MB per case