Statistics

Problem Statement for "LinenCenterEasy"

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:
LinenCenterEasy
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 50, inclusive.
  • K will be between 0 and 50, inclusive.
  • L will be between 1 and 50, inclusive.
  • S will contain exactly L characters.
  • S will contain only lowercase English letters.

Examples

  1. "aaaa"

    1

    4

    Returns: 127

  2. "abcd"

    0

    3

    Returns: 1

  3. "abcab"

    15

    0

    Returns: 743760874

  4. "x"

    20

    5

    Returns: 732797485

  5. "abcdefghabcdefgh"

    1

    15

    Returns: 417

  6. "sgrlobvqgthjpwzgkocigfcoyrlgpzkhuzmngcnojgdutvkvib"

    50

    50

    Returns: 65601003

  7. "abbaaabbabbabaaabbabbabbaabbbaabbbbababbabaababbaa"

    50

    50

    Returns: 123939933

  8. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    50

    50

    Returns: 960113657

  9. "ebecdafebebcdfbcdacbbadecbdcbfddbaddcbafefcfcddbdf"

    50

    49

    Returns: 262170370

  10. "eszycidpyopumzgdpamntyyawoixzhsdkaaauramvgnxaqhyv"

    48

    40

    Returns: 54119203

  11. "zscpyibaevspyxlkyaipzgxnrrvdgsrwzxivztvcnkclznzi"

    49

    39

    Returns: 352137928

  12. "kemubcrdlsbqgbcnnchcrnbsdhuusbssmbhbrejnerdsjrvfdb"

    49

    43

    Returns: 6827285

  13. "kemubcrdlsbqgbcnnchcrnbsdhuusbssmbhbrejnerdsjrvfn"

    49

    48

    Returns: 421855831

  14. "yxyzxxzxyzxzxxxyyxxxzyxzxxzzzxzzyxxxzxyyxzxzyzy"

    45

    26

    Returns: 503385394

  15. "npqmnvklmnwsnqukrrrqrtnqlrnwkvosqrqvluollqtqn"

    46

    30

    Returns: 519162333

  16. "pqmnvklmnwsnqukrrrqrtnqlrnwkvo"

    21

    28

    Returns: 60409055

  17. "tliefvakqotckrtwbxmfwoxnffhbdeqscywmzxdjmikzbgwanb"

    22

    47

    Returns: 773764946

  18. "bnpagopkchlbnelmnjiofjlepckfhnhbbpjccemleddoiefd"

    24

    19

    Returns: 25324637

  19. "yyqpzpnytomlwypkmllqrkyuyqrtzkmysxmsurtkmnwtwmkkqq"

    35

    40

    Returns: 788684041

  20. "qymuqrsuvpnutotttqqymuqrsuvpnutor"

    46

    35

    Returns: 898225864

  21. "yrpzzrpozmtovqzwlxxszzkmtyrpzzrpozmtovqzwlq"

    50

    29

    Returns: 992518686

  22. "vozkoustmnktvnypwvzuzuvxtsqkoommysywuxulwoykxz"

    49

    50

    Returns: 864998767

  23. "lwrurnoosrozyonsmsmxlrpnrzlstuouznoqpyputvyuvopwo"

    50

    47

    Returns: 428523958

  24. "izxvzouoalhskhkvqvxdrvuglanayleaupnkpxmzmcvbrzrq"

    49

    9

    Returns: 881671829

  25. "izxvzouoalhskhkvqvxizxvzouoalhskhkvqvxiizxzouoalz"

    48

    46

    Returns: 469833517

  26. "hhhghghghgghghghhhghghghgghghghhhghhhghghghgghghg"

    50

    47

    Returns: 960220045

  27. "hhhghghghghhhghghghghhhghghghghhhghghghhhhghghghg"

    49

    26

    Returns: 427083556

  28. "mpompmomnnppnnmnpnpmmpopmnmnmompompomnpompmomnnppn"

    48

    45

    Returns: 405348803

  29. "xuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuw"

    50

    10

    Returns: 449298594

  30. "pppzykrwtxwbppppzykrwtxwbpppxwbppppzykrwtxwbpzpmrf"

    18

    50

    Returns: 160577973

  31. "gxgxgxgxgxgxgxgxgxgxgggxgxgxgxgxgxg"

    49

    20

    Returns: 970482946

  32. "uusipjwdojaseluilljiuusipjwdojaseluilljiuusipjw"

    43

    49

    Returns: 791630232

  33. "qbnpygnwefupqbnpygnwefupqqbnpygnwefupqbnp"

    35

    24

    Returns: 976174260

  34. "nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnna"

    44

    28

    Returns: 27607004

  35. "szpfswszpfswszpfswszpfswszpfswszpfswsq"

    50

    50

    Returns: 655144296

  36. "njqomqmojlmmmihqloiomtrpknjqomqmojlmmmihqlq"

    50

    49

    Returns: 531980496

  37. "xunhthrnvwvvpowrtvuxxunhthxunhthpowrtvuxxulwxunhf"

    9

    9

    Returns: 538312199

  38. "fsckuztcncfsckuztcncfsckuztcnfsckuztcncf"

    11

    27

    Returns: 665269236

  39. "awywzynraaawywynraawywawywzynraaawywynraawywawyz"

    27

    27

    Returns: 731136689

  40. "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.

  41. "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.

  42. "ababab"

    5

    4

    Returns: 527166180

    Watch out for integer overflows and make sure you are using the correct modulus!

  43. "fgcdx"

    10

    3

    Returns: 586649223

  44. "ghjhhhgjhjhgjhghghjhjg"

    8

    10

    Returns: 192161304

  45. "pdpfrpfdfdpfdpfdpfpdfldfpfldpfe"

    49

    25

    Returns: 164673990

  46. "a"

    7

    0

    Returns: 357828722

  47. "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee"

    50

    50

    Returns: 960113657

  48. "assad"

    50

    50

    Returns: 381512648

  49. "lolol"

    30

    25

    Returns: 338754637

  50. "aaabbbaaa"

    30

    20

    Returns: 904826543

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.
This problem was used for: