PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
This problem can be solved using dynamic programming. The idea is based on a quite usual algorithm of checking if string S is a subsequence of some other string T: take the first character of S and find its first occurrence in T (say, Ti); take the second character of S and find its first occurrence in T after position i; take the third character of S… and so on, until there are no more characters in S (then S is indeed a subsequence of T) or there is no occurrence of the next character of S in T after the required position (then S is not a subsequence of T). Each string of length N which is a subsequence of the string given in the input will be implicitly searched for using this algorithm.
Let the given string be S. Let fi, j be the number of distinct strings of length i-j such that if we search for each of them in S, we’ll stop our search at position i in S (basically, j stands for the number of skipped characters in S). If we find an efficient way to calculate fi, j for all i ≤ N+K and j ≤ K, we’ll be able to find the answer easily as the sum of all fi, j such that i-j = N.
A simple way to do this works in O(NKM), where M = 26 (the size of the alphabet). Set f0,0 = 1. Then, for each i and j try every possible next character (a…z) of the searched string and add fi,j, to fp,j +(p-i-1), where p is the position of the next occurrence of this character in S after position i. The position of the next occurrence of character c in S after position i, nexti,c, can be easily precalculated in O(NM) time beforehand. However, this approach is too slow to get accepted.
To solve the problem in O(NK), we need to reverse our DP. From the above paragraph it can be inferred that fi,j is equal to the sum of fp,j-(i-p-1) for all p such that t ≤ p < i, where t is the largest integer smaller than i such that Si = St. To find this sum quickly, an auxiliary DP gi,j is needed such that gi,j = gi-1, j-1 + fi,j (basically, all gi,j represent partial sums on the “diagonals” of fi,j). Then fi,j can be calculated in O(1) as fi,j = gi-1, j - gt-1, j-(i-t). To understand why this is so, draw a rectangular matrix representing fi,j and find out which elements of f sum up to each gi,j, then note that the difference of those two elements of g is actually a plain sum of all required elements of f.
That’s all for the solution. Don’t forget that all calculations should be done modulo 1009419529. Also note that modulo operator (% in C++ and Java, mod in Pascal) is much slower than addition and subtraction, so it’s not recommended to use it when it’s possible not to use it. For reference of a solution without any modulo operations at all, see problem setter’s or problem tester’s (a single modulo at the end) solution.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.