All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
In this problem we will have a few definitions as described below:
- Binary string: A string containing only characters '0' and '1'.
- Hamming distance of the two binary string of the same length is the number of the positions where the two strings have
different characters. eg. the hamming distance of "01010101" and
"00110111" is 3, the hamming distance of a binary string with itself is 0.
- Sub-string of a string is a segment of contiguous characters of that string.
You would be given two binary strings A and B with the length of N and M respectively.
You need to calculate the Hamming distance between B and every sub-strings of length M of A.
For this problem, you will be given a fixed string A. There will be K queries each containing a string representing B.
- The first line contains the binary string A.
- The next line contains an integer K.
- Each of the next K lines contains a binary string B.
To avoid generating large output, for each query string B instead of printing N - M + 1 values of Hamming distance between
sub-strings of A and B in the order of the position of the sub-string in A, you only need to print
the hash value of this sequence as described below.
Let s[0..L -1] be a sequence of L integers. The recursive function f(s) will return the hash value of s.
- if L = 1, f(s) = s mod 1000000007
- Otherwise, f(s) = (f(s[0..L-2]) * 100001 + s[L-1]) mod 1000000007
So overall, your output should be K lines, each containing the hash value corresponding to the query string B.
- 1 ≤ M ≤ N ≤ 1000
- 1 ≤ K ≤ 5
- 1 ≤ M ≤ N ≤ 50000
- 1 ≤ K ≤ 5
- 1 ≤ M ≤ N ≤ 100000
- 1 ≤ K ≤ 5
Input: 10101 3 101 00 0101 Output: 300003 993599731 400004
First test case: A = "10101", B = "101".
The Hamming distances sequence will be (0, 3, 0) and the hash value of this sequence is 300003.
Second test case: A = "10101", B = "00". The Hamming distances sequence will be (1, 1, 1, 1)
and the hash of this sequence is 993599731.
Third test case: A = "10101", B = "0101". The Hamming distances sequence will be (4, 0)
and the hash value of this sequence is ((4 mod 1000000007) * 100001 + 0) mod 1000000007 = 400004.
|Tags||fft, hard, ltime19, tuananh93|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.