結果

問題 No.125 悪の花弁
ユーザー HachimoriHachimori
提出日時 2015-01-12 01:46:06
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 402 ms / 5,000 ms
コード長 2,755 bytes
コンパイル時間 957 ms
コンパイル使用メモリ 76,980 KB
実行使用メモリ 15,928 KB
最終ジャッジ日時 2024-06-22 04:28:55
合計ジャッジ時間 3,916 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 333 ms
15,680 KB
testcase_01 AC 356 ms
15,856 KB
testcase_02 AC 401 ms
15,928 KB
testcase_03 AC 402 ms
15,892 KB
testcase_04 AC 378 ms
15,640 KB
testcase_05 AC 380 ms
15,440 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<numeric>
#include<map>
#include<vector>
using namespace std;
const int FACTORIAL = 1000005;
const int COLOR = 100005;
const int MOD = 1000000007;


int mul(int a, int b) {
    return 1LL * a * b % MOD;
}

int modpow(int p, int n) {
    if (n == 0) return 1;
    int t = modpow(p, n / 2);
    return n & 1 ? mul(t, mul(t, p)) : mul(t, t);
}

int inv(int v) {
    return modpow(v, MOD - 2);
}

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}


int factorial[FACTORIAL];
int invFactorial[FACTORIAL];

void makeFactorial() {
    factorial[0] = 1;
    for (int i = 1; i < FACTORIAL; ++i) {
        factorial[i] = mul(factorial[i - 1], i);
        invFactorial[i] = inv(factorial[i]);
    }
}


int nC, C[COLOR];

void read() {
    cin >> nC;
    for (int i = 0; i < nC; ++i)
        cin >> C[i];
}


void work() {
    // divisor2cnt[C の約数]: C の約数が現れた回数
    map <int, int> divisor2cnt;
    
    for (int i = 0; i < nC; ++i) {
        int n = C[i];
        for (int div = 1; div * div <= n; ++div) {
            if (n % div == 0) {
                if (div * div == n) {
                    ++divisor2cnt[div];
                }
                else {
                    ++divisor2cnt[div];
                    ++divisor2cnt[n / div];
                }
            }
        }
    }
    
    // 各 C が共通で持っている約数
    vector<int> commonDivisor;
    for (map<int, int>::iterator it = divisor2cnt.begin(); it != divisor2cnt.end(); ++it) {
        if (it->second == nC) {
            commonDivisor.push_back(it->first);
        }
    }
    
    // toMul[i]: 0 ～ sum of nC - 1 の うち、 sum of nC と gcd をとって i 
    // となる個数
    int toMul[FACTORIAL] = {};
    for (int i = 0, t = accumulate(C, C + nC, 0); i < t; ++i)
        ++toMul[gcd(t, i)];
    
    int ans = 0;
    
    for (int loop = 0; loop < commonDivisor.size(); ++loop) {
        int divisor = commonDivisor[loop];
        
        int total = 0;
        int curC[COLOR];
        for (int i = 0; i < nC; ++i) {
            total += C[i] / divisor;
            curC[i] = C[i] / divisor;
        }
        
        // toAdd: total 個の花びらがあり、同じ色の花びらは curC[i] 個存在
        //        並び方が何通り存在するか
        int toAdd = 1;
        toAdd = mul(toAdd, factorial[total]);
        for (int i = 0; i < nC; ++i) {
            toAdd = mul(toAdd, invFactorial[curC[i]]);
        }
        
        ans = (ans + mul(toMul[total], toAdd)) % MOD;
    }
    
    // C の総数で割る
    ans = mul(ans, inv(accumulate(C, C + nC, 0)));
    
    cout << ans << endl;
}


int main() {
    makeFactorial();
    read();
    work();
    return 0;
}
0