No.125 悪の花弁 - yukicoder
- 回転して一致するものを同じとみなしたときの数えあげ問題。
- 解法を理解してから、実装に超手間取った。g%pd とするところを T%pd にしたり、最後の 1/gs が抜けたりとひどかった...。
- 実装力がなさすぎるな...。
- 蟻本では似た問題をオイラー関数を使っていたのでそっちの解法もそのうち考えてみようと思う。
class Fact {
std::vector<long long> inv_;
std::vector<long long> fact_;
std::vector<long long> factr_;
public:
Fact(int maxN, long long P) {
long long ModP = P;
inv_.resize(maxN+1,0);
fact_.resize(maxN+1,0);
factr_.resize(maxN+1,0);
inv_[1] = fact_[0] = factr_[0] = 1;
for (int i = 2; i <= maxN; ++i)
inv_[i] = inv_[ModP % i] * (ModP - ModP/i) % ModP;
for (int i = 1; i <= maxN; ++i)
{
fact_[i] = fact_[i-1]*i % ModP;
factr_[i] = factr_[i-1]*inv_[i] % ModP;
}
}
long long fact(long long n) { return fact_[n]; }
long long factr(long long n) { return factr_[n]; }
long long inv(long long n) { return inv_[n]; }
};
using namespace std;
const int Mod = (int)(1E+9)+7;
class EvilPetal {
public:
void solve(void) {
const int maxN = (int)1E+6;
int K;
cin>>K;
vector<int> C(K);
int T = 0;
REP(i,K)
{
cin>>C[i];
T += C[i];
}
int g = C[0];
FOR(i,1,K)
g = gcd(g, C[i]);
vector<int> gsize;
for (int pd = 1; pd*pd <= g ; ++pd)
{
if ( g % pd != 0 )
continue;
gsize.push_back(T/pd);
if (g/pd != pd)
gsize.push_back(T/(g/pd));
}
Fact f(maxN, Mod);
vector<ll> num(maxN+1,0);
ll tot = 0;
sort(RANGE(gsize));
REP(i,gsize.size())
{
int gs = gsize[i];
ll cnt = f.fact(gs);
REP(j,K)
cnt = cnt * f.factr(C[j]/(T/gs)) % Mod;
REP(j,i)
{
if (gs % gsize[j] == 0)
{
cnt -= num[gsize[j]];
(cnt += Mod) %= Mod;
}
}
num[gs] = cnt;
(tot += num[gs]*f.inv(gs)%Mod) %= Mod;
}
cout<<tot<<endl;
}
};