Codeforces 150 B. Quantity of Strings

問題

アルファベットがm種類ある言語の上で、
n文字からなり、その連続する部分文字列の長さがkのものはどれも回文になっているような文字列はいくつあるか、mod 10^9+7で求めよ。

制約条件

n,m,k≦2000

方針

同じ文字になるところをunion-findでunionする。
すると、最終的にいくつの自由度があるかがわかるので、
m^(自由度)が求める答えとなる。

ソースコード

int p[2000];
int root(int x){ return x==p[x]?x:root(p[x]); }
void merge(int a,int b){
	a=root(a); b=root(b);
	if(a!=b)p[a]=b;
}
int main(){
	int n,m,k;
	cin>>n>>m>>k;
	iota(p,p+n,0);
	rep(i,n-k+1)rep(j,k/2)merge(i+j,i+k-j-1);
	ll ans=1;
	bool v[2000]={};
	rep(i,n)if(!v[root(i)]){
		v[root(i)]=1;
		ans=(ans*m)%((int)1e9+7);
	}
	cout<<ans<<endl;
	return 0;
}