SRM576 Div2 Hard "CharacterBoard2"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12506

訳

マナオは行数が10000、 列数がWの行列を持っていた。
彼は、この行列を文字で埋める為、そのためのアルゴリズムを開発した。
まず始めに、長さがWを超えないような、文字列Sを選ぶ。
このSはジェネレーターと呼ばれる。
それから、次のような擬似コードで表現されるアルゴリズムで
文字を行列に埋めていく。

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)

マナオは最近、メモ書きされた行列Xを発見した。
彼は、それがジェネレーターで生成されたものなのかを知りたがっている。
あなたには以下のような情報が与えられる。
String[] fragment ... これはXの一部を表した行列である。
int W ... これは行列Xの幅（列数）である。
int i0とint j0 ... これはfragmentの左上の座標である。
言い換えれば、fragment[i][j] = X[i + i0][j + j0]である。

fragmentを含んだ行列Xを生成できるジェネレーターが
何種類あるのかを返せ。

制約

fragmentの行数をN 列数をMとする。
1 <= N, M <= 10
M <= W <= 10000

考えた事

まずジェネレーターSの文字数を決めちゃう。
そうすると、fragmentの各文字が、
Sのどの場所の文字なのかが分かるので、
その場所と文字を記憶していく。

ある場所にある文字を記憶するときに、
同じ場所に既に何らかの文字が記憶されていて、それが違う文字だったら、
現在調べている文字数のジェネレーターでは、行列Xは生成できないことになる。

全てのfragmentを調べたときに、まったく記憶されていない場所は、
a～zのどれでも使えるため、* 26通りになる。

事後

fragmentが10 * 10で、Wが10000までだから
計算量は100万なのかなぁ
その割には時間かかっていたような気がする。

ソースコード

char S[10050];
const int MOD = 1000000009;

class CharacterBoard2 {
public:
    int countGenerators(vector <string> fragment, int W, int i0, int j0){
        int h = fragment.size();
        int w = fragment[0].length();
        long long res = 0;

        // ジェネレーターSの文字数lenを決める
        for( int len = 1; len <= W; len++ ){
            // 全部?にしとく
            for( int i = 0; i < len; i++ ) S[i] = '?';

            bool ok = true;
            for( int i = 0; i < h; i++ ){
                int base = (i0+i) * W;
                for( int j = 0; j < w; j++ ){
                    int index = (base + j0 + j) % len;
                    // 既に違う文字が入ってたらダメ
                    if( S[index] != '?' && S[index] != fragment[i][j] ){
                        ok = false;
                        break;
                    }
                    S[index] = fragment[i][j];
                }
            }
            if( ok ){
                long long lenRes = 1;
                for( int i = 0; i < len; i++ ){
                    // 何にも入ってないところの数だけ*26する
                    if( S[i] == '?' ){
                        lenRes = lenRes * 26 % MOD;
                    }
                }
                res = (res + lenRes) % MOD;
            }
        }
            
        return (int)res;
    }
};