yukicoder : No.125 悪の花弁

約数じゃなくて素因数分解しちゃった。あとmod取ってるのに普通に除算しちゃってた。
http://yukicoder.me/problems/167

問題

K種類の色の花びらがそれぞれC[i]個ずつある。
これら全てを円形に並べて花を作りたい。
回転して色が一致する並べ方は、同じものとみなす。
花を構成する花びらの組み合わせは何通りあるか。

解法

蟻本２版 p.269に同じような問題がある。

花びらx個分花を回転させて元と同じ色合いになるとき、その花の周期をxとする。

C[i]の総和をTとすると、花を完全に１回転すると元の形状に戻るので、どんな花も周期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;
}

まとめ

「蟻本にあったポリアの数え上げ定理とかうまく使えないかな？」と思ったけど、うまく適用できませんでした。