yukicoder : No.377 背景パターン

ポリアの数え上げ定理はすぐ頭に浮かんだのに、そこから解法までたどり着けないあたり、ポリアの数え上げ定理を上っ面しか理解していなかったことがバレバレですね。
http://yukicoder.me/problems/561

問題

大きさH*Wの２次元グリッドの各セルをK色のいずれかで塗った模様がある。
このグリッドを敷き詰めたとき、得られる模様は何通りか。
ただし、平行移動して同じ模様が得られる模様群が１通りと数える。

解法

1次元のケースは蟻本第二版p.269「石の塗り方の数え上げ」そのままである。
まずはこれを理解した上で2次元版である本問に進もう。

以下ほとんど公式Editorialの要約。

横に0≦x＜W、縦に0≦y＜Hマス平行移動した場合同じ模様になるような模様の組み合わせをf(x,y)とする。
ポリアの数え上げ定理より解はである。

(a,b)をa列b行のセルを意味するとする。
x,yマス平行移動しても同じ模様となるためには、(0,0),(x%W,y%H),(2x%W,2y%H),...が同じ色でなければならないので、nx%W=0かかつny%H=0となる最小の正整数n=LCM(W/GCD(W,x),H/GCD(H,y))を考えると、nマスは同じ色でなければならない。
言い換えるとWH/nマスは任意の色を取れるので、となる。

とはいえf(x,y)はわかっても元の2つのsumを愚直に計算すると間にあわない。
ここでも蟻本の問題を参考に式変形しよう。
例えばWの約数wに対しGCD(W,x)=wとなるxの数はφ(W/w)となる。（φはオイラーのトーシェント関数）
同様にWの約数hに対しGCD(H,y)=hとなるhの数はφ(H/h)となる。
ここから上記式はと変形できる。
事前にH,Wの約数や、H,Wの素因数を列挙しておくと、上記二重ループは高速に処理できる。

ll H,W,K;
ll mo=1000000007;
set<ll> primes;
ll modpow(ll a, ll n) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

vector<ll> enumdiv(ll n) {
	vector<ll> S;
	for(ll i=1;i*i<=n;i++) if(n%i==0) {S.push_back(i); if(i*i!=n) S.push_back(n/i); }
	sort(S.begin(),S.end());
	for(ll i=2;i*i<=n;i++) if(n%i==0) { primes.insert(i); while(n%i==0) n/=i;}
	if(n>1) primes.insert(n);
	return S;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>K;
	auto VH=enumdiv(H);
	auto VW=enumdiv(W);
	ll ret=0;
	
	FORR(h,VH) FORR(w,VW) {
		ll eu1=h;
		ll eu2=w;
		FORR(r,primes) if(h%r==0) eu1 = eu1/r*(r-1);
		FORR(r,primes) if(w%r==0) eu2 = eu2/r*(r-1);
		
		ret += eu1*eu2%mo*modpow(K,(H/h)*(W/w)*__gcd(h,w))%mo;
	}
	
	cout<<ret%mo*modpow(H,mo-2)%mo*modpow(W,mo-2)%mo<<endl;
	
}

まとめ

最初のGCDの部分をスマートに処理できなかったことも敗因。
最近ARCでも色の塗り分け問題出たのにね…。