TopCoder SRM 576 Div1 Hard CharacterBoard
問題
10^9行W列のグリッドがある。各セルには英小文字が書かれている。
このグリッドを(i0, j0)を左上として高さh, 幅wの長方形の一部を切り出したところ、
fragmentsで表される長方形が得られた。
グリッド全体は、長さx(1≦x≦W)の文字列を、繰り返し埋めたものであることが保証されているとき、
はじめの文字列としてありえるものは何通りあるか、mod 10^9 + 9で求めよ。
制約条件
W≦10^9
h, w≦10
fragments[i][j]は英小文字
繰り返し埋めるというのは、abcdeで幅6のグリッドを埋めるとき
abcdea
bcdeab
cdeabc…みたいな感じ
方針
fragments内の文字で、かぶりがある場合とそうでない場合がある。
すなわち、繰り返し文字列の長さをLとすると、
L[i](どれか)が2度以上現れる場合とそうでない場合がある。
Lのどこかの場所が2度以上fragmentsに現れる場合、
二箇所の位置の相対関係は高々10*20通りくらいしかない。
なのでこれを全部試すと、Lの候補は、10^9くらいの数の約数だけになる。
候補の長さを決めたら、文字が決まってない場所の個数を適当にmapなんかを使って求めて、26をその分累乗すればよい。
Lのどの場所も、fragmentsに2度以上現れていない場合、
これは、全体から現れる場所を引けばよい。
ソースコード
class CharacterBoard { public: static const int mod = (int)1e9 + 9; int h, w; vector <string> f; int W, i0, j0; set<int> vis; ll solve(int len){ if(vis.count(len)) return 0; vis.insert(len); ll tot = len < h * w ? 0 : pw(26, len - h * w); map<int, char> kind; rep(i, h) rep(j, w){ int pos = ((ll)(i + i0) * W + j + j0) % len; if(kind.count(pos) && kind[pos] != f[i][j]) return mod - tot; kind[pos] = f[i][j]; } return pw(26, len - kind.size()) + mod - tot; } ll pw(ll n, ll m){ ll res = 1; for(; m; m /= 2){ if(m & 1) res = res * n % mod; n = n * n % mod; } return res; } ll inv(ll n){ return pw(n, mod - 2); } int countGenerators(vector <string> fragment, int W, int i0, int j0) { vis.clear(); f = fragment; this->W = W; this->i0 = i0; this->j0 = j0; h = f.size(), w = f[0].size(); ll ans = 0; if(W - h * w + 1>= 0) ans = (pw(26, W - h * w + 1) - 1) * inv(26 - 1) % mod; rep(i, h) for(int j = -w + 1; j < w; j++){ ll len = (ll)i * W + j; for(ll k = 1; k * k <= len; k++) if(len % k == 0){ if(k <= W) ans += solve(k); if(len / k <= W) ans += solve(len / k); } ans %= mod; } return ans; } };