TopCoder SRM 576 Div2 Hard CharacterBoard2

さてDiv2 Hard。今回はDiv1 Hardと若干パラメータが異なるだけで似た問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12506

問題

ある文字列に対し、その文字列を左上から横方向に何度も並べていき長方形を構成することができる。

ここで、完成した長方形の一部の長方形部分の文字列と、元の長方形の幅が与えられる。
構成元文字列のサイズが元の長方形の幅より短い場合、この長方形を再現できる文字列の組み合わせ数を答える。

解法

最大の長方形の幅は高々10000。
よって1～10000の各幅の文字列を仮定すると、判明している部分長方形の各文字が生成元文字列の何文字目にくるかわかるので、それらの文字を確定させていく。
部分長方形の文字のうち、生成元文字列の同じ位置から生成されている文字同士は同じでなければならない。

生成元文字列のうち、部分文字列から参照されていない文字はA～Zの何を入れてもいいので、そのような文字の数だけ26の累乗を取ったものが解となる。

class CharacterBoard2 {
	public:
	int countGenerators(vector <string> fragment, int W, int i0, int j0) {
		ll mo=1000000009;
		ll res=0;
		ll p26[10001];
		p26[0]=1;
		for(int i=1;i<=10000;i++) p26[i]=(p26[i-1]*26)%mo;
		
		for(int S=1;S<=W;S++) {
			map<ll,char> T;
			
			for(int ty=j0;ty<j0+fragment.size();ty++) {
				for(int tx=i0;tx<i0+fragment[0].size();tx++) {
					ll st=(ty*W+tx)%S;
					if(T[st]==0) T[st]=fragment[ty-j0][tx-i0];
					else if(T[st]!=fragment[ty-j0][tx-i0]) goto ne;
				}
			}
			
			res = (res + p26[S-T.size()]) % mo;
			ne:
			;
		}
		return (int)res;
	}
};

まとめ

力技だけどすんなり行った。解法もすぐ思いついたし。
なお、Div1は幅が10^9になるので全幅試すことはできない。
もう少しスマートな解法が必要そうだね。