0w1

Yuki 125 悪の花弁

Problem Description:
There are K kinds of colors, each with at least one instance of object. There are C[i] number of instances of color i. You are to arrange them into a ring, and you want to know how many different kinds of rings could be made, modulo 1e9 + 7. Two rings are considered different, iff after some rotation (without flipping), they can be identical.

Constraints:
1 ≤ K ≤ 1e5
C.reduce(:+) ≤ 1e6
1 ≤ C[i], for all i

Solution:
Let's consider each color independently. We can observe that each color should form some period (the least number of rotations that make them identical). When the period of each color is determined, the period of the ring is also determined, which is the greatest common divisor of period of each color. Hence we consider to enumerate the period of the ring. Let T denote the sum of C, and G denote the greatest common divisor of C. Then we can enumerate each possible period of the ring, as T / c, where c is some factor of C. Since each group consists of identical instances, and groups have different colors, we can calculate the number of combinations as (T/c)! / (0...K).map { |i| (C[i]/(T/c))! } .reduce(:*). To take the sum of results, make sure to reduce overlapped combinations that occur from periods being a factor of other periods, which can be taken care easily with inclusion-exclusion. Also, for any ring with period p, it will be calculated p times, hence it is required to divide the result by p for each period.

#include <bits/stdc++.h>
using namespace std;

const int MOD = int(1e9) + 7;
const int MAXK = 1 << 17;
const int MAXTOT = 1 << 20;

int inv_mod(int v, int m = MOD) {
  int r = 1;
  for (int p = m - 2; p; p >>= 1) {
    if (p & 1) r = 1LL * r * v % m;
    v = 1LL * v * v % m;
  }
  return r;
}

int fac[MAXTOT];

int K;
int C[MAXK];
int T;
int G;

int dp[MAXTOT];

signed main() {
  ios::sync_with_stdio(false);
  for (int i = fac[0] = 1; i < MAXTOT; ++i) {
    fac[i] = 1LL * fac[i - 1] * i % MOD;
  }
  cin >> K;
  for (int i = 0; i < K; ++i) {
    cin >> C[i];
    T += C[i];
    G = __gcd(G, C[i]);
  }
  vector<int> periods;
  for (int i = 1; i * i <= G; ++i) {
    if (G % i != 0) continue;
    periods.emplace_back(T / i);
    if (i * i == G) break;
    periods.emplace_back(T / (G / i));
  }
  sort(periods.begin(), periods.end());
  int ans = 0;
  for (int i = 0; i < periods.size(); ++i) {
    int p = periods[i];
    dp[p] = fac[p];
    for (int j = 0; j < K; ++j) {
      dp[p] = 1LL * dp[p] * inv_mod(fac[C[j] / (T / p)]) % MOD;
    }
    for (int j = 0; j < i; ++j) {
      int q = periods[j];
      if (p % q != 0) continue;
      (dp[p] -= dp[q]) %= MOD;
    }
    (ans += 1LL * dp[p] * inv_mod(p) % MOD) %= MOD;
  }
  if (ans < 0) ans += MOD;
  cout << ans << endl;
  return 0;
}