D. Quantity of Strings

2012-02-18

07:30 |

長さ N で M 種類の文字を使った文字列のうち、どの長さ K の部分文字列も回文になっているようなものの個数を出す。

1 <= N,M,K <= 2000

N 頂点のグラフを考えて、同じでないといけない頂点を辺で結ぶ。それで、M の「連結な部分の数」乗が答え。

こういうグラフに帰着させるようなのは１年前はできなかった気がする。よかよか。

struct UnionFind {
	vector<int> data;
	UnionFind(int size) : data(size, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

int main() {
	int n, m, k;
	cin>>n>>m>>k;
	
	//if(n<k) {
	//	cout<<0<<endl;
	//	return 0;
	//}
	UnionFind uf(n);
	REP(i, n-k+1) {
		REP(j, k/2) {
			uf.unionSet(i+j, i+k-1-j);
		}
	}
	map<int, int> mm;
	REP(i, n) {
		mm[uf.root(i)]=1;
	}
	ll ans=1;
	REP(i, mm.size()) {
		ans *= m;
		ans = ans % 1000000007LL;
	}
	cout<<ans<<endl;
	
	return 0;
}