結果

問題 No.125 悪の花弁
コンテスト
ユーザー kroton
提出日時 2015-01-12 00:17:37
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 36 ms / 5,000 ms
コード長 2,038 bytes
コンパイル時間 1,358 ms
コンパイル使用メモリ 163,452 KB
実行使用メモリ 19,512 KB
最終ジャッジ日時 2024-06-22 04:10:52
合計ジャッジ時間 2,035 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

const int MOD = 1e9 + 7;
const int MAX = 1000010;

ll fact[MAX], fact_inv[MAX];
ll mod_pow(ll x, ll e){
    ll v = 1;
    for(;e;e>>=1){
        if(e & 1)v = (v * x) % MOD;
        x = (x * x) % MOD;
    }
    return v;
}
void init(){
    fact[0] = 1;
    for(int i=1;i<MAX;i++)
        fact[i] = i * fact[i-1] % MOD;

    fact_inv[MAX-1] = mod_pow(fact[MAX-1], MOD - 2);
    for(int i=MAX-2;i>=0;i--){
        fact_inv[i] = (i + 1) * fact_inv[i + 1] % MOD;
    }
}

ll comb(int n, int k){
    ll res = fact[n] * fact_inv[k] % MOD;
    res = res * fact_inv[n-k] % MOD;
    return res;
}

vector<int> ps, divs;
void init_n(int n){
    for(int d=1;d*d<=n;d++)if(n % d == 0){
        divs.push_back(d);
        if(n / d != d)
            divs.push_back(n / d);
    }
    for(int p=2;p*p<=n;p++)if(n % p == 0){
        ps.push_back(p);
        while(n % p == 0)
            n /= p;
    }
    if(n > 1)
        ps.push_back(n);
}


int euler(int n){
    int res = n;
    for(int p : ps){
        if(n % p == 0)
            res = res / p * (p - 1);
    }
    return res;
}


int K, C[100010];
int main(){
    cin >> K;
    for(int i=0;i<K;i++)
        cin >> C[i];
    
    int N = 0;
    for(int i=0;i<K;i++)
        N += C[i];
    
    int g = 0;
    for(int i=0;i<K;i++)
        g = gcd(g, C[i]);
    
    
    init();
    init_n(N);
    
    ll res = 0;
    for(int d : divs){
        int block_size = N / d;
        int block_num = N / block_size;
        
        if(g % block_size != 0)
            continue;
        
        ll tmp = euler(N / d);
        
        for(int i=0;i<K;i++){
            int use = C[i] / block_size;
            tmp *= comb(block_num, use);
            tmp %= MOD;
            block_num -= use;
        }
        
        res = res + tmp;
        res %= MOD;
    }
    
    res *= mod_pow(N, MOD - 2);
    res %= MOD;
    
    cout << res << endl;
    return 0;
}
0