kmjp's blog

競技プログラミング参加記です

yukicoder : No.1727 [Cherry 3rd Tune] Stray

飛ばしてた。
https://yukicoder.me/problems/no/1727

問題

正N角柱を考える。
底面と側面の辺の長さは異なる。

この角柱の2N点をC色で彩色するとき、回転して同じ状態になるものは1つと数えると、全体で彩色の仕方は何通りか。

解法

ポリアの数え上げ定理で解く。
底面のある1点を、回転後どこに一致させるか、を考えよう。

  • 底面でd頂点分回転させて一致させる場合、底面と上面でそれぞれd頂点分は自由に彩色できるので、φ(N/d)*C^(2d)通りの彩色ができる。
  • 底面を上面のどこかに一致させる場合、底面のN頂点と上面のN頂点が回転して同じ並びになればいいので、一致させる頂点がN通りあることを考えるとN*C^N通りの彩色が可能。

あとは上記の和を2Nで割ればよい。

int T,N,C;
const ll mo=1000000007;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	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());
	return S;
}

ll A[4040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>C;
		
		auto D=enumdiv(N);
		ll ret=0;
		// 上下回転なし
		for(i=D.size()-1;i>=0;i--) {
			A[i]=N/D[i];
			for(j=i+1;j<D.size();j++) if(D[j]%D[i]==0) A[i]-=A[j];
			(ret+=A[i]*modpow(C,2*D[i]))%=mo;
		}
		// 上下回転
		(ret+=N*modpow(C,N))%=mo;
		
		//平均で割る
		ret=ret*modpow(2*N)%mo;
		cout<<ret<<endl;
	}
}

まとめ

なんで書いてなかったんだろ。