TopCoder SRM 576 - 900: CharacterBoard

Problem Statement

很久很久以前，有一个活泼可爱的小朋友，他拥有一个1000000000行W列的棋盘，
行从上至下以0..999999999编号，列从左至右以0..W-1编号。

后来，有一个长者给了他一个长度为L的字符串s[0..L-1]，
并让小朋友以以下伪代码去填充这个棋盘a[1000000000][W]。

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

接着，小朋友在大棋盘中取出一个以(i0,j0)为左上角，行数为N，列数为M的子矩阵fragment[N][M]。

现在已知i0,j0,W，以及取出的子矩阵fragment[N][M]，
而对于那个用于循环节的字符串s，连长度L都不知道，更别提内容了，只知道 L<= W，
且s只含有小写字母。小朋友想要猜出这个字符串s究竟是啥。

于是问你s有多少种可能的值，答案 mod 1000000009。

Manao has a matrix X with 1,000,000,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 999999999
  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 CharacterBoard
Method countGenerators
Parameters vector<string> , int , int , int
Returns int
Method signature int countGenerators(vector<string> fragment, int W, int i0, int j0)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

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 1,000,000,000, inclusive.
i0 will be between 0 and 1,000,000,000 - N, inclusive.
j0 will be between 0 and W - M, inclusive.

Test cases

input
- fragment {"dea",
  "abc"}
- W 7
- i0 1
- j0 1
output
Returns 1
note
Manao has a matrix with 1000000000 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".
input
- fragment { "xyxxy" }
- W 6
- i0 1
- j0 0
output
Returns 28
note
The given information is:
```
??????
xyxxy?
??????
...
```
The corresponding generator could be "xyx", "yxyxx", or a string of form "xyxxy?", where '?' stands for any lowercase letter.
input
- fragment {"gogogo",
  "jijiji",
  "rarara"}
- W 6
- i0 0
- j0 0
output
Returns 0

note

No generator could create this matrix using the given algorithm.
input
- fragment {"abababacac",
  "aaacacacbb",
  "ccabababab"}
- W 8827
- i0 104
- j0 6022
output
Returns 829146844

back to the menu

SRM 576 1 900 CharacterBoard

Problem Statement

Definition

Limits

Constraints

Test cases