約数じゃなくて素因数分解しちゃった。あとmod取ってるのに普通に除算しちゃってた。
http://yukicoder.me/problems/167
問題
K種類の色の花びらがそれぞれC[i]個ずつある。
これら全てを円形に並べて花を作りたい。
回転して色が一致する並べ方は、同じものとみなす。
花を構成する花びらの組み合わせは何通りあるか。
解法
蟻本2版 p.269に同じような問題がある。
花びらx個分花を回転させて元と同じ色合いになるとき、その花の周期をxとする。
C[i]の総和をTとすると、花を完全に1回転すると元の形状に戻るので、どんな花も周期Tである。
花は複数の周期をもつこともある。そもそも周期xの花は整数kに対し周期(x*k)ともなる。
C[i]の(最大以外のものを含め)公約数をgとするとき、周期(T/g)の花を作ることができる。
最小の周期が(T/g)の花の組み合わせを考える。
まずは回転を無視して、各花をC[i]/g個ずつ並べるとその組み合わせP(T/g)はである。
この中には周期がT/gより短いケースも含まれてしまうので、T/gの(T/g未満の)約数yに対しP(T/g)からP(y)を引いておく。
今求めたP(T/g)は周期がちょうど(T/g)の花の組み合わせを求めたものなので、1個ずつずらしていくと同じものを(T/g)回ずつカウントしていることになる。
なので各gについてP(T/g)/(T/g)の総和を取れば良い。
int K; ll C[101000],T; ll mo=1000000007; const int NUM_=1000005; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; ll num[1010000]; ll modpow(ll a, ll n = mo-2) { ll r=1; while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1; return r; } void solve() { int i,j,k,l,r,x,y; string s; inv[1]=fact[0]=factr[0]=1; for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo; for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo; cin>>K; if(K==1) return _P("1\n"); FOR(i,K) cin>>C[i], T+=C[i]; ll g=C[0]; ll tot=0; FOR(i,K) g=__gcd(g,C[i]); vector<ll> V; for(ll i=1;i*i<=g;i++) if(g%i==0) {V.push_back(T/i); if(i*i!=g) V.push_back(T/(g/i)); } sort(V.begin(),V.end()); FOR(i,V.size()) { x=V[i]; num[x]=fact[x]; FOR(j,K) num[x] = num[x] * factr[C[j]/(T/x)] % mo; FOR(j,i) if(x%V[j]==0) num[x] -= num[V[j]]; num[x]=(num[x]%mo+mo)%mo; tot += num[x]*modpow(x)%mo; } cout<<tot%mo<<endl; }
まとめ
「蟻本にあったポリアの数え上げ定理とかうまく使えないかな?」と思ったけど、うまく適用できませんでした。