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