飛ばしてた。
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; } }
まとめ
なんで書いてなかったんだろ。