LinenCenter | Topcoder Archive

Problem Statement

A few days ago, you won a tour of a textile factory. (Chocolate factory tours were deemed too risky to children and therefore banned). As everyone knows, textile is made of strings, so it's time to solve a string problem!

You are given a String S of length L. For any string T, we can now define its covering number c(T) as the maximum number of non-overlapping occurrences of S in T. Each occurrence must be a contiguous substring of T, and they may not share any letters.

Examples:
If S="ab", we have c("xyz")=0 and c("ababxab")=3.
If S="aaa", we have c("aa")=0 and c("aaaaaa")=2.

In addition to S, you are given two ints N and K.

Consider all strings with the following properties:

Each character of the string is a lowercase English letter ('a'-'z').
The length of the string is between L*K and L*K+N, inclusive.
The covering number of the string is exactly K.

Let X be the number of strings with the above properties. Since X may be large, compute and return the value (X modulo 1,000,000,009).

Definition

Class:: LinenCenter
Method:: countStrings
Parameters:: String, int, int
Returns:: int
Method signature:: int countStrings(String S, int N, int K)
(be sure your method is public)

Constraints

N will be between 0 and 1,000, inclusive.
K will be between 0 and 1,000,000,000, inclusive.
L will be between 1 and 100, inclusive.
S will contain exactly L characters.
S will contain only lowercase English letters.

Examples

```
"xy"
```
```
2
```
```
1
```
```
Returns: 2079
```
There are 2027 strings of length 4, 52 strings of length 3 and one string of length 2 containing "xy" as a substring. One of them, "xyxy", has covering number 2, so we don't count it.
```
"q"
```
```
2
```
```
1
```
```
Returns: 1926
```
We're counting strings containing exactly one character 'q' and at most two other characters. There's one such string of length 1 ("q"), 2*25=50 of length 2 and 3*25^2=1875 of length 3.
```
"ababab"
```
```
5
```
```
4
```
```
Returns: 527166180
```
Watch out for integer overflows and make sure you are using the correct modulus!
```
"fgcdx"
```
```
500
```
```
10
```
```
Returns: 942389748
```

"ghjhhhgjhjhgjhghghjhjg"

10000000

Returns: 618639712

"pdpfrpfdfdpfdpfdpfpdfldfpfldpfdlfpdlfdpflepflfldpflofpwpldlfpde"

500000000

Returns: 852730493

```
"a"
```
```
100
```
```
0
```
```
Returns: 990669582
```

"eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee"

1000000000

Returns: 286425258

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.