Statistics

Problem Statement for "LinenCenter"

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

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

    1000

    1000000000

    Returns: 75313186

  7. "abbaaabbabbabaaabbabbabbaabbbaabbbbababbabaababbabaababaabbbabbaaaaabbabaaabaaabbbaabbaabbababbababa"

    1000

    1000000000

    Returns: 860541017

  8. "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"

    1000

    1000000000

    Returns: 286425258

  9. "ebecdafebebcdfbcdacbbadecbdcbfddbaddcbafefcfcddbdadffdadbeacacfcacebadbcabdffcfedbdecbfefaaaaecefdaf"

    1000

    999999999

    Returns: 192483554

  10. "eszycidpyopumzgdpamntyyawoixzhsdkaaauramvgnxaqhyoprhlhvhyojanrudfuxjdxkxwqnqvgjjspqmsbphxzmnvflrwyv"

    947

    792652821

    Returns: 351354632

  11. "zscpyibaevspyxlkyaipzgxnrrvdgsrwzxivztvcnkclznziowdygwuzjdbsgulpgqsuwzqaulhtnjlsdcqvqgdtvijxgmphet"

    989

    225362687

    Returns: 177090833

  12. "kemubcrdlsbqgbcnnchcrnbsdhuusbssmbhbrejnerdsjrvfdssugldrwcsbtgpvrnykosoljhzfwyhcsjqpkxojtcdqnfykepnb"

    999

    718244981

    Returns: 381882240

  13. "kemubcrdlsbqgbcnnchcrnbsdhuusbssmbhbrejnerdsjrvfdssugldrwcsbtgpvrnykosoljhzfwyhcsjqpkxojtcdqnfykepn"

    985

    981622566

    Returns: 133047455

  14. "yxyzxxzxyzxzxxxyyxxxzyxzxxzzzxzzyxxxzxyyxzxzyzzxxzzzxyxzzxzxzxyzzyyyzyyyxxzxxzyzyyzyyzxxzyxyxy"

    905

    469572379

    Returns: 391957190

  15. "npqmnvklmnwsnqukrrrqrtnqlrnwkvosqrqvluollqtqlukpnvlrusntwmtlskrvnmtrvtrospqmmwtlsvpvpurstn"

    919

    331562138

    Returns: 2706300

  16. "pqmnvklmnwsnqukrrrqrtnqlrnwkvo"

    418

    558536687

    Returns: 909612018

  17. "tliefvakqotckrtwbxmfwoxnffhbdeqscywmzxdjgvhxzncyigmikzbgwanb"

    388

    961871573

    Returns: 66803650

  18. "bnpagopifbpkchlbnelmnjiofjleohombahegjlhkonpckfhnhbbpjccemleddofglnnohiefd"

    467

    286718130

    Returns: 668551283

  19. "yyqpzpnytomlwypkmllqrkyuyqrtzkmysxmsurtkmnwntwmkkqqlzwwxmq"

    692

    835919668

    Returns: 318647785

  20. "qymuqrsuvpnutotttqqymuqrsuvpnutotttqqymuqrsuvvxsswsvlurruutomkurnr"

    722

    692196312

    Returns: 450640188

  21. "yrpzzrpozmtovqzwlxxszzkmtyrpzzrpozmtovqzwlxxszzkmtyrpzzrpozmtovqzmzpnuxqoxwwrvzkuutxnq"

    984

    555463335

    Returns: 962045307

  22. "vozkoustmnktvnypwvzuzuvxtsqkoommysywuxulwoykxysuzwxrrxpkvozkousonmmrtwvqmkqvpkyysllznknpwyvoz"

    987

    861483070

    Returns: 998913893

  23. "lwrurnoosrozyonsmsmxlrpnrzlstuouznoqpyputvyuvopwqkroqsrmxpqklvwpkoptwswwwtrqzkvwqyzqtnxqnlwrlwrurno"

    1000

    971980678

    Returns: 285081213

  24. "izxvzouoalhskhkvqvxdrvuglanayleaupnkpxmzmcvbrzrqrueqwetjdeizxvzouoalhskhkvqvxdrvuglanayleaupnkizmz"

    993

    2056594

    Returns: 106532257

  25. "izxvzouoalhskhkvqvxizxvzouoalhskhkvqvxiizxzouoalhskhkvqvxizxvzouoalhskhkvqvxizxvzouoalhskhkvqvizmz"

    982

    868927929

    Returns: 844987051

  26. "hhhghghghgghghghhhghghghgghghghhhghhhghghghgghghghhhghghghhghghghgghghghhhghghghgghghghghgghhhhhgg"

    962

    846701254

    Returns: 143366168

  27. "hhhghghghghhhghghghghhhghghghghhhghghghhhhghghghghhhghghghghhhghghghghhhghghghhhhghghghghhhghghghg"

    984

    472971079

    Returns: 772446602

  28. "mpompmomnnppnnmnpnpmmpopmnmnmompompomnpommpompmomnnppnmpompmomnnppnnmnpnpmmpmpompmmompnnpomompm"

    968

    959779154

    Returns: 777391456

  29. "xuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxuvxyuyyw"

    997

    239031913

    Returns: 210683594

  30. "ppppzykrwtxwbppppzykrwtxwbppppzykrwtxwbppppzykrwtxwbppppzykrwtxwpkytzpmrf"

    306

    999045580

    Returns: 969584299

  31. "gxgxgxgxgxgxgxgxgxgxgggxgxgxgxgxgxgxgxgxgxgxgxgxgxgxgxgxgxgxgxgxgxgggxg"

    980

    411456026

    Returns: 685087917

  32. "uusipjwdojaseluilljiuusipjwdojaseluilljiuusipjwdmsdbwpunxzjfbuusipjwdojaseluilljiuusipjiquusolv"

    883

    230097069

    Returns: 752928052

  33. "qbnpygnwefupqbnpygnwefupqqbnpygnwefupqbnpygnwefupqqbnwefupqbncwrzrsaquhhrksxseqavqb"

    577

    492384012

    Returns: 266641299

  34. "nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnna"

    842

    72023817

    Returns: 607151068

  35. "szpfswszpfswszpfswszpfswszpfswszpfswszpfswszpfswszszpfswoaiuszpfswoaiussowmq"

    875

    33904

    Returns: 608342993

  36. "njqomqmojlmmmihqloiomtrpknjqomqmojlmmmihqloiomtrpknjqomqmojlmmmihqlonjmojlmmmihptplnjq"

    122

    134757843

    Returns: 859291038

  37. "xunhthrnvwvvpowrtvuxxunhthxunhthpowrtvuxxulwxunhthrnvwvvpxunhthrnvnxunhthrnvwvvpovuxxulwxuundnkjjf"

    456

    219458559

    Returns: 391679292

  38. "fsckuztcncfsckuztcncfsckuztcnfsckuztcncfsckuqiiojgkkffsckuztcncfsckuztcncdddxxvxeh"

    394

    433942936

    Returns: 905107676

  39. "awywzynraaawywynraawywawywzynraaawywynraawywawywzynraaawywynrsrcqonnimawywzynraaawyawywynraawywz"

    638

    643195515

    Returns: 739649728

  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"

    500

    10

    Returns: 942389748

  44. "ghjhhhgjhjhgjhghghjhjg"

    8

    10000000

    Returns: 618639712

  45. "pdpfrpfdfdpfdpfdpfpdfldfpfldpfdlfpdlfdpflepflfldpflofpwpldlfpde"

    999

    500000000

    Returns: 852730493

  46. "a"

    100

    0

    Returns: 990669582

  47. "eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee"

    1000

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