Podnizovi
레이팅 미적용의견: 0
\(5^{th}\) round, January \(16^{th}\) 2016
You are given an array of integers of length \(N\). Let \(s\)1, s2, ..., s\(q\) be the lexicographically sorted
array of all its n\(on-em\)pty subsequences. A subsequence of the array is an array obtained by removing
zero or more elements from the initial array. Notice that some subsequences can be equal and that it
holds \(q = 2^{N} - 1\).
An array \(A\) is lexicographically smaller than array \(B\) if \(A@@RISE_MATH_BLOCK_0@@i\) where \(i\) is the first position at which
the arrays differ, or if \(A\) is a strict prefix of array \(B\).
Let us define the hash of an array that consists of values \(v\)1, v2, ..., v\(p\) as:
\(h\)(\(s\)) = (\(v@@RISE_MATH_BLOCK_1@@2 \cdot B\){p} + ... + \(v@@RISE_MATH_BLOCK_2@@p\)) mod \(M\)}^{2
where \(B\), \(M\) are given integers.
Calculate \(h\)(\(s_{1}\)), h(\(s_{2}\)), ..., h(\(s_{K}\)) for a given \(K\).
In test cases worth 60% of total points, it will additionally hold 1 ⩽\(a\)1, a2, ..., a_{N} ⩽30.
The first line contains integers \(N\), \(K\), \(B\), \(M\) (1 ⩽\(N\) ⩽100 000, 1 ⩽\(K\) ⩽100 000, 1 ⩽B, M ⩽
1 000 000).
The second line contains integers \(a_{1}\), a_{2}, a_{3}, ..., a_{N} (1 ⩽\(a_{i}\) ⩽100 000).
In all test cases, it will hold \(K\) ⩽\(2^{N} - 1\).
Output \(K\) lines, the \(j\)^{th} line containing \(h\)(\(s\)\(j\)).
2 3 1 5
1 2
3 4 2 3
1 3 1
5 6 23 1000
1 2 4 2 3output
output
1
3
2
1
1
0
2
1
25
25
577
274
578Clarification of the first example: It holds: s1 = [1], s2 = [1, 2], s3 = [2]. h(s1) = 1 mod 5 = 1, h(s2) =
(1 + 2) mod 5 = 3, h(s3) = 2 mod 5 = 2.
Clarification of the second example: It holds: s1 = [1], s2 = [1], s3 = [1, 1], s4 = [1, 3].
h(s1) = 1
mod 3 = 1, h(s2) = 1 mod 3 = 1, h(s3) = (1 · 2 + 1) mod 3 = 0, h(s4) = (1 · 2 + 3) mod 3 = 2.
평가 및 의견
Podnizovi
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Podnizovi