Devu and good strings
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
A string str is called a good string if there does not exist three difference indices i, j, k such that i, j, k are consecutive three terms of an arithmetic progression and str[i] = str[j] = str[k].
You are given a string s and two integers K, A. You have to find the number of good strings t with alphabet size A (i.e. if A = 1, then string can only have a's and if A = 2, string can only contain 'a' or 'b'. e.g. if A = 2, t can be aa, ab, bb etc., for A = 3, string can only contain 'a', 'b' and 'c', i.e. it can be aab bac, bbb, cbb etc.) of length |s| such that hamming distance between strings s and t is less than or equal to K. As the answer could be very large, print answers modulo 109 + 7.
Hamming distance between two strings of same size is defined as the number of indices where their corresponding characters differ. Formally, for two strings s, t of length N, hamming distance will be number of indices 1 ≤ i ≤ N such that s[i] != t[i].
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- For each test case, first line will contain two integers A, K.
- The second line of each test case will contain the string s.
- For each test case, output a single line corresponding to the answer of the problem.
- 1 ≤ T ≤ 50
- 0 ≤ K ≤ |s|
Subtask 1 (10 points)
- 1 ≤ |s| ≤ 50, A = 1
Subtask 2 (20 points)
- 1 ≤ |s| ≤ 12, 1 ≤ A ≤ 3
Subtask 3 (30 points)
- 1 ≤ |s| ≤ 50, A = 2
Subtask 4 (40 points)
- 1 ≤ |s| ≤ 50, A = 3
Input: 2 1 0 a 2 2 aba Output: 1 5
Example case 1. Only string of length 1 and alphabet size 1 will be 'a'. Hamming distance of "a" with "a" is zero which is ≤ 1. So answer is 1.
Example case 2. There can be total 8 strings. 6 of them are good. aaa and bbb are not good, remaining all are good. From the 6 good strings, bab has a hamming distance of 3, remaining other 5 have hamming distance ≤ 2. Hence answer is 5.
|Tags||admin2, april16, arithmetic, easy-medium, hamming-dist|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.