TopCoder Statistics - Problem Statement

Problem Statement

Manao has a matrix X with 10,000 rows and W columns. He likes to fill it with characters; he even has developed an algorithm for this task. First, he chooses a string S consisting of at most W lowercase letters. The string S is called the generator. Then, he applies the algorithm described by the following pseudocode:

cur := 0
for i := 0 to 9999
  for j := 0 to W - 1
    X[i][j] := S.charAt(cur)
    cur := (cur + 1) mod length(S)

Manao has recently found a matrix X in his notepad. He wonders whether it was generated using the above algorithm. You are given:

a String[] fragment that contains a rectangular submatrix of X,
the int W: the width of X,
and two ints i0 and j0: the coordinates of the upper left corner of your submatrix within X.

In other words, for all valid i, j we have fragment[i][j] = X[i + i0][j + j0]. Count how many different generators Manao could have used to create a matrix X that contains the fragment you were given. Return this number modulo 1,000,000,009.

Definition

Class:: CharacterBoard2
Method:: countGenerators
Parameters:: String[], int, int, int
Returns:: int
Method signature:: int countGenerators(String[] fragment, int W, int i0, int j0)
(be sure your method is public)

Constraints

fragment will contain N elements, where N is between 1 and 10, inclusive.
Each element of fragment will be M characters long, where M is between 1 and 10, inclusive.
Each element of fragment will consist of lowercase letters ('a'-'z') only.
W will be between M and 10,000, inclusive.
i0 will be between 0 and 10,000 - N, inclusive.
j0 will be between 0 and W - M, inclusive.

Examples

{"dea", "abc"}

7

1

1

Returns: 1

Manao has a matrix with 10000 rows and 7 columns. We know that it looks as follows: ??????? ?dea??? ?abc??? ??????? ... The only string of length at most 7 which could generate such matrix is "abcde".
{"xyxxy"}

6

1

0

Returns: 28

The given information is: ?????? xyxxy? ?????? ... The corresponding generator could be "xyx", "yxyxx", or a string of form "xyxxy?", where '?' stands for any lowercase letter.
{"gogogo", "jijiji", "rarara"}

6

0

0

Returns: 0

No generator could create this matrix using the given algorithm.
{"abababacac", "aaacacacbb", "ccabababab"}

882

10

62

Returns: 361706985
{"asjkffqw", "basjkffq", "qbasjkff", "qqbasjkf"}

9031

9024

1959

Returns: 173947456
{"aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa"}

10000

0

0

Returns: 253373800
{"aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaaa", "aaaaaaaaab"}

10000

0

0

Returns: 481162973
{"a","a"}

1

125

0

Returns: 1
{"a","a"}

2

145

0

Returns: 27
{"a","b"}

1

125

0

Returns: 0
{"aaaaaaaaaa","aaaaaaaaaa","aaaaaaaaaa","aaaaaaaaaa","aaaaaaaaaa","aaaaaaaaaa","aaaaaaaaaa","aaaaaaaaaa","aaaaaaaaaa","aaaaaaaaab"}

10000

8159

1230

Returns: 481162973
{"bbbbbbaaaa","abbbaabbaa","aabbbbabba","aabbbbbaaa","aabbaabaaa","bbaabaabaa","bbaaaaaaaa","babaaabbbb","aaabbbaaab","bababbaabb"}

10000

1275

92

Returns: 954403309
{"dqjzzwkax","enrupfqzx","roxyelnno"}

5029

6425

413

Returns: 533708449
{"eenrd","xyofp","vxxok"}

4510

5340

3953

Returns: 844044003
{"qd","kc","zc","nt","np"}

8593

7103

3960

Returns: 651086495
{"czfrvlvpp"}

7634

5529

4058

Returns: 490663457
{"ubtqsargxu","jrhaxcdwmd","tpqrqhxgbe","pezkuvvotx","mxveehtyov","qpvvtxdzmd","dftswtdcln","pbchlocqmu","exipytuxpv"}

3897

9186

3785

Returns: 714044871
{"tytj","eajj","gyyi","wldm","gdwv","ljte","jzle","lshh","tuag","ujyf"}

5480

3992

3192

Returns: 369980528
{"sgjp","dcnk","feqv","wbfh","nzpa","cvob","ipix","odfx","ndri"}

5703

5089

3753

Returns: 517784911
{"zvsnnazg","vgxueslx","rlbxazqe","pocouael","gfealvaz"}

9375

877

729

Returns: 816068458
{"paxtpex","rwjsmel","notosgd","eytogfr","kzupfjr","rseoehg","qirryik","osjwzrq","qzzhvei"}

7216

6421

1038

Returns: 931120584
{"m","e","z","z","b","a","m"}

5304

8738

5072

Returns: 681802875
{"xrdjb"}

2193

6710

1856

Returns: 253662504
{"dgew","mhrp","dixm","xvpk","mewp","kvdj","issi","tmlr","ewpu","bpae"}

7036

1401

390

Returns: 12329671
{"srpomdt","zjemhhv","ycqusbg","dblhmho","fhcfsfg"}

4645

4081

3788

Returns: 444526770
{"ip","pv","gi"}

8299

636

6371

Returns: 689579247
{"jwgyskv","azraxkh","eapvmrt","fnuglpp","hismjwr","zfhcwre"}

3253

7363

2190

Returns: 820308701
{"cbgbfv","zeyrzl","okbmrv","uqbyhp"}

4052

733

419

Returns: 382516384
{"su","lh","vd","se","cf","ro","sd","km"}

1172

2216

351

Returns: 954950596
{"tekgwa","bzfuwl","wjbltm"}

9286

4366

4600

Returns: 651904760
{"vwks","izam","amvp","xphi","ycne"}

4148

6902

2313

Returns: 204930400
{"s","x","i","j","q","i","e"}

3879

4604

2123

Returns: 710328089
{"aimhbgpxn","xlbijvpcl","hbzfzgsap","wpzpuulpt","gjakjbfce","pqmpibtqv","eveeutuny","gjbfkdnnh","vuhzofnmj"}

9668

4651

5697

Returns: 167662266
{"nkasdzkj","tkyjghdm","xjfpiskm","ukffcbxm","thdeunic","cxocksob","waahtxzd","onrmfsmk","idhvnpfg"}

6838

938

66

Returns: 656602208
{"krtrtgxuo","yglhaielr","ppoguroyf","whxlozbrd","nipotsswq","mauwewqcn","rxgjsbuls","oqmgpcsof","dzavfluhc"}

584

501

404

Returns: 44297560
{"aspafgarp","jcmbpqfbj","czuazqmvy","usinbwhul","xpagogwsz","vyptiuvlk","gjkrwerpu","ffxfmekih","rzrlpuvrd","rsdthprjx"}

4289

2367

3403

Returns: 147231832
{"zkzazeyj","uaipnnaq","monbzdtn","igbddzaj","mwxaucnf","zljnqyht","wixtfoga","vzpajias","lyqgwfjb"}

7380

1115

1685

Returns: 605258212
{"levtgaytu","rjlqxrntp","pigyswcgu","szetuqfzc","lvpdkziot","strhuiepp","fchbmyfia","dhbrucicd","yzygzxczl"}

9225

113

6684

Returns: 712311637
{"lqdkmyup","ufetjqkl","uwkxvnak","mswlbwrt","bhfhvqvd","lijcmcyr","lfwkeoaa","oobdajgu","oitaqizl","xytgmyoa"}

7628

5476

5708

Returns: 349208890
{"zanlmjkqg","cwcnvhxws","dqtjhykxw","hfdvshdhj","hwcmtkmdb","iqhhmerrx","pjumvpovr","nabgvwpdi","ztrlahjmo"}

7702

1985

4046

Returns: 991831630
{"ekebgtpdok","pjtefofxny","igecbdkmkn","uzmclskuum","jhqdxfowfx","wuoqdydrtd","vgytdejvcn","hxmwwlgxcx","oltuefwdib","cdjwxqxdqq"}

2431

5069

1199

Returns: 400344995
{"pmpucylvb","ufyipkbeo","fnyohjgfl","rqzinqqep","ezfossytt","dwctzclbh","fszmkhggt","jfmueggyj","qbkyqldtu"}

1643

3623

86

Returns: 802976187
{"vyjfrbyrhi","rhikjtvvyj","vyjfrbyrhi","rhikjtvvyj","vyjfrbyrhi","rhikjtvvyj","vyjfrbyrhi","rhikjtvvyj","vyjfrbyrhi","rhikjtvvyj"}

8015

650

3386

Returns: 791546177
{"xknntimzx","nxknntimz","hnxknntim","uhnxknnti","buhnxknnt","tbuhnxknn","ltbuhnxkn","xltbuhnxk"}

9843

7762

6739

Returns: 850014162
{"zcfarxan","hizcfarx","nbhizcfa","annbhizc","rxannbhi","farxannb","zcfarxan","hizcfarx","nbhizcfa","annbhizc"}

7126

1779

294

Returns: 221359024
{"iwipaqtb","ipaqtbxi","aqtbxiph","tbxiphbu","xiphbuzo","phbuzoby","buzobyui","zobyuiwi","byuiwipa"}

9616

9680

6880

Returns: 620616321
{"jsxhdbgcdp","qbjsxhdbgc","dpqbjsxhdb","gcdpqbjsxh","dbgcdpqbjs","xhdbgcdpqb","jsxhdbgcdp","qbjsxhdbgc","dpqbjsxhdb","gcdpqbjsxh"}

7978

6222

923

Returns: 223531031
{"rrxlhribr","enmrrxlhr","zavenmrrx","ticzavenm","cyfticzav","pavcyftic","kbdpavcyf","ibrkbdpav","lhribrkbd"}

8907

1000

5913

Returns: 694325584
{"junpoysvn","uyrorzjun","oysvnpuyr","rzjunpoys","npuyrorzj","npoysvnpu","rorzjunpo","svnpuyror","junpoysvn","uyrorzjun"}

9754

8266

9423

Returns: 726038998
{"ugywscfuy","hhymdeyug","ljcqlklhh","fuyjcgalj","yugywscfu","lhhymdeyu","aljcqlklh","cfuyjcgal","eyugywscf","klhhymdey"}

9146

7991

6911

Returns: 428363515
{"mdxbftrn","tmdxbftr","atmdxbft","batmdxbf","bbatmdxb","lbbatmdx","nlbbatmd","jnlbbatm","jjnlbbat"}

8672

9140

4880

Returns: 580961481
{"sdbrpeba","dbrpebae","brpebaeg","rpebaegp","pebaegpy","ebaegpyi","baegpyiz","aegpyizq","egpyizqx"}

9145

3841

4217

Returns: 771829921
{"pvqozfsdgr","ejmtoxrqlm","mugldcsdrm","pvqozfsdgr","ejmtoxrqlm","mugldcsdrm","pvqozfsdgr","ejmtoxrqlm","mugldcsdrm","pvqozfsdgr"}

10000

3521

4530

Returns: 276277834
{"apwixecsho","rhlbriedgk","imweoonrrr","apwixecsho","rhlbriedgk","imweoonrrr","apwixecsho","rhlbriedgk"}

10000

9605

438

Returns: 338817711
{"sfsrxumc","sfsrxumc","sfsrxumc","sfsrxumc","sfsrxumc","sfsrxumc","sfsrxumc","sfsrxumc","sfsrxumc"}

10000

4052

4414

Returns: 573834803
{"skyngepa","gepaqzlw","qzlwrhdm","rhdmcsky","cskyngep","ngepaqzl","aqzlwrhd","wrhdmcsk"}

10000

7262

6046

Returns: 584970502
{"goranzhjik","sqnqnyisbr","jefvvmpyul","fnfkkzakcn","qpylbicbnn","myuxsbvizq","ygqurwzvnh","qhirgocmzk","pqllccjhct"}

9512

4854

5511

Returns: 591699156
{"qhriqrglx","ymnhsvkgl","uixvzhfqo","mrbxwoxze","inmhzyqif","hdupuqfib","ewowfogvv","ojsebirme","tdvzjquvy"}

9562

1239

329

Returns: 195920929
{"pmiweaalc","pmiweaalc","pmiweaalc","pmiweaalc","pmiweaalc","pmiweaalc","pmiweaalc","pmiweaalc","pmiweaalc"}

10

8604

0

Returns: 26
{"fxsytflugb","fxsytflugb","fxsytflugb","fxsytflugb","fxsytflugb","fxsytflugb","fxsytflugb","fxsytflugb","fxsytflugb","fxsytflugb"}

10000

5819

5629

Returns: 569107362
{"vbtwromqv","omqvbtwro","twromqvbt","qvbtwromq","romqvbtwr","btwromqvb","mqvbtwrom","wromqvbtw","vbtwromqv"}

333

1650

113

Returns: 444363246
{"taotaota","aotaotao","otaotaot","taotaota","aotaotao","otaotaot","taotaota","aotaotao","otaotaot"}

334

4827

11

Returns: 451137862
{"dea", "abc" }

7

1

1

Returns: 1
{"asjkffqw", "basjkffq", "qbasjkff", "qqbasjkf" }

9031

9024

1959

Returns: 173947456
{"xyxxy" }

6

1

0

Returns: 28
{"aaaa", "aaaa" }

5000

4888

4888

Returns: 362932625
{"asjkffww", "basjkffq", "qbasjkff", "qqbasjkf" }

9031

9024

1959

Returns: 668576860

Statistics

Problem Statement for "CharacterBoard2"

Problem Statement

Definition

Constraints

Examples