{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME19/mandarin/TASTRMAT.pdf\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME19/russian/TASTRMAT.pdf\"\u003eRussian\u003c/a\u003e.\u003c/h3\u003e\r\n\r\n\r\n\u003cp\u003eIn this problem we will have a few definitions as described below:\r\n\u003cul\u003e\r\n \u003cli\u003e\u003cb\u003eBinary string\u003c/b\u003e: A string containing only characters \u00270\u0027 and \u00271\u0027.\u003c/li\u003e\r\n \u003cli\u003e\u003cb\u003eHamming distance\u003c/b\u003e of the two binary string of the same length is the number of the positions where the two strings have \r\n different characters. eg. the hamming distance of \"0\u003cb\u003e10\u003c/b\u003e101\u003cb\u003e0\u003c/b\u003e1\" and\r\n \"0\u003cb\u003e01\u003c/b\u003e101\u003cb\u003e1\u003c/b\u003e1\" is 3, the hamming distance of a binary string with itself is 0.\u003c/li\u003e\r\n \u003cli\u003e\u003cb\u003eSub-string\u003c/b\u003e of a string is a segment of contiguous characters of that string.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nYou would be given two binary strings \u003cb\u003eA\u003c/b\u003e and \u003cb\u003eB\u003c/b\u003e with the length of \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eM\u003c/b\u003e respectively. \r\nYou need to calculate the Hamming distance between \u003cb\u003eB\u003c/b\u003e and every sub-strings of length \u003cb\u003eM\u003c/b\u003e of \u003cb\u003eA\u003c/b\u003e.\r\n\u003c/p\u003e\r\n\u003cp\u003e\t\r\nFor this problem, you will be given a fixed string \u003cb\u003eA\u003c/b\u003e. There will be \u003cb\u003eK\u003c/b\u003e queries each containing a string representing \u003cb\u003eB\u003c/b\u003e. \r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cul\u003e\r\n \u003cli\u003eThe first line contains the binary string \u003cb\u003eA\u003c/b\u003e.\u003c/li\u003e\r\n \u003cli\u003eThe next line contains an integer \u003cb\u003eK\u003c/b\u003e.\u003c/li\u003e\r\n \u003cli\u003eEach of the next \u003cb\u003eK\u003c/b\u003e lines contains a binary string \u003cb\u003eB\u003c/b\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003eTo avoid generating large output, for each query string \u003cb\u003eB\u003c/b\u003e instead of printing \u003cb\u003eN - M + 1\u003c/b\u003e values of Hamming distance between\r\nsub-strings of \u003cb\u003eA\u003c/b\u003e and \u003cb\u003eB\u003c/b\u003e in the order of the position of the sub-string in \u003cb\u003eA\u003c/b\u003e, you only need to print \r\nthe \u003cb\u003ehash value\u003c/b\u003e of this sequence as described below.\u003c/p\u003e\r\n\r\n\u003cp\u003eLet s[0..\u003cb\u003eL\u003c/b\u003e -1] be a sequence of \u003cb\u003eL\u003c/b\u003e integers. The recursive function f(s) will return the hash value of s.\r\n\u003cul\u003e\r\n \u003cli\u003eif \u003cb\u003eL\u003c/b\u003e \u003d 1, f(s) \u003d s[0] mod \u003cb\u003e1000000007\u003c/b\u003e\u003c/li\u003e\r\n \u003cli\u003eOtherwise, f(s) \u003d (f(s[0..\u003cb\u003eL\u003c/b\u003e-2]) * \u003cb\u003e100001\u003c/b\u003e + s[\u003cb\u003eL\u003c/b\u003e-1]) mod \u003cb\u003e1000000007\u003c/b\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\u003c/p\u003e\r\n\r\nSo overall, your output should be \u003cb\u003eK\u003c/b\u003e lines, each containing the hash value corresponding to the query string \u003cb\u003eB\u003c/b\u003e.\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cp\u003e\r\n\u003cb\u003e20 points:\u003c/b\u003e\r\n\u003cul\u003e\r\n \u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eM ≤ N\u003c/b\u003e ≤ \u003cb\u003e1000\u003c/b\u003e\u003c/li\u003e\r\n \u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eK\u003c/b\u003e ≤ \u003cb\u003e5\u003c/b\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\n\u003cb\u003e40 points:\u003c/b\u003e\r\n\u003cul\u003e\r\n \u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eM ≤ N\u003c/b\u003e ≤ \u003cb\u003e50000\u003c/b\u003e\u003c/li\u003e\r\n \u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eK\u003c/b\u003e ≤ \u003cb\u003e5\u003c/b\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\n\u003cb\u003e40 points:\u003c/b\u003e\r\n\u003cul\u003e\r\n \u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eM ≤ N\u003c/b\u003e ≤ \u003cb\u003e100000\u003c/b\u003e\u003c/li\u003e\r\n \u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eK\u003c/b\u003e ≤ \u003cb\u003e5\u003c/b\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n10101\r\n3\r\n101\r\n00\r\n0101\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n300003\r\n993599731\r\n400004\r\n\u003c/pre\u003e\r\n\r\n\u003ch3\u003eExplanation:\u003c/h3\u003e\r\n\u003cp\u003e\u003cb\u003eFirst test case: \u003c/b\u003e \u003cb\u003eA\u003c/b\u003e \u003d \"10101\", \u003cb\u003eB\u003c/b\u003e \u003d \"101\". \r\nThe Hamming distances sequence will be (0, 3, 0) and the hash value of this sequence is 300003.\u003c/p\u003e\r\n\r\n\u003cp\u003e\u003cb\u003eSecond test case: \u003c/b\u003e \u003cb\u003eA\u003c/b\u003e \u003d \"10101\", \u003cb\u003eB\u003c/b\u003e \u003d \"00\". The Hamming distances sequence will be (1, 1, 1, 1) \r\nand the hash of this sequence is 993599731.\u003c/p\u003e\r\n\r\n\u003cp\u003e\u003cb\u003eThird test case:\u003c/b\u003e \u003cb\u003eA\u003c/b\u003e \u003d \"10101\", \u003cb\u003eB\u003c/b\u003e \u003d \"0101\". The Hamming distances sequence will be (4, 0)\r\nand the hash value of this sequence is ((4 mod 1000000007) * 100001 + 0) mod 1000000007 \u003d 400004.\u003c/p\u003e"}}]}