K-pop Strings
시간 제한7초메모리 제한512 MB
길이 n인 문자열 가운데 길이가 n-k 이상인 연속 반복(tandem repeat)이 하나도 없는 문자열의 개수를 35종 문자로 세어 998244353으로 나눈 나머지를 구한다. n은 100 이하, k는 16 이하이다.
문제
A substring s[l..r] is a tandem repeat if r − l + 1 is even and s[l . . . (l+r−1)/2] = s[(l+r+1)/2. . . r].
Recently Gennady came up with a method to calculate the number of tandem repeats in a string using suffix structures, and now he came up with a new type of strings based on tandem repeats. Gennady thinks that string s of length n is a K-pop string if there are no tandem repeats of length ≥ n − k.
Help him find the number of K-pop strings consisting only of the characters ‘1’, ‘2’, . . . , ‘9’, ‘a’, ‘b’, . . . , ‘z’, modulo 998 244 353.
입력
The first line of input contains two integers n and k: the required length of string and the parameter (1 ≤ n ≤ 100, 0 ≤ k ≤ 16).
출력
Output one integer: the number of K-pop strings of length n for the given k, consisting only of nonzero digits and lowercase alphabetic characters, modulo 998 244 353.
힌트
The answer for the first example is 35 because all strings of length 1 are possible: “1”, “2”, . . . , “9”, “a”, “b”, . . . , “z”.
The answer for the second example is 354 − 352.