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;
	}
};