結果

問題 No.125 悪の花弁
ユーザー なおなお
提出日時 2015-01-12 01:21:59
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 225 ms / 5,000 ms
コード長 1,390 bytes
コンパイル時間 1,549 ms
コンパイル使用メモリ 160,840 KB
実行使用メモリ 27,980 KB
最終ジャッジ日時 2024-06-22 04:26:03
合計ジャッジ時間 2,893 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 131 ms
26,184 KB
testcase_01 AC 154 ms
26,052 KB
testcase_02 AC 225 ms
27,976 KB
testcase_03 AC 222 ms
25,928 KB
testcase_04 AC 209 ms
27,980 KB
testcase_05 AC 211 ms
25,924 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define ITER(c)             __typeof__((c).begin())
#define FOREACH(it, c)      for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define REP(i, n)           for(int(i)=0;(i)<(n);++(i))
#define RREP(i, n)          for(int(i)=(n)-1;(i)>=0;--(i))
const int MOD = (int)1e9+7;

ll extgcd(ll a,ll b,ll &m,ll &n){ll g=a;m=1;n=0;if(b)g=extgcd(b,a%b,n,m),n-=(a/b)*m;return g;}
ll divmod(ll n,ll m,ll mod){ll a,b;extgcd(m,mod,a,b);return((n*a)%mod+mod)%mod;}
ll fact[2000001], factinv[2000001];
void factmod(int n){
    fact[0]=fact[1]=1;
    for(int i=2;i<=n;i++)fact[i]=(fact[i-1]*i)%MOD;
    factinv[n]=divmod(1,fact[n],MOD); //inv
    for(int i=n;i>=0;i--)factinv[i-1]=(factinv[i]*i)%MOD;
}

int A[111111];
int cnt[1100000];

ll gcd(ll n, ll m){return m?gcd(m,n%m):n;}

int main(){
    int K; cin >> K;
    int sum = 0, g = 0;
    REP(i,K){
        cin >> A[i];
        g = gcd(g,A[i]);
        sum += A[i];
    }
    factmod(1100000);
    REP(i,sum) cnt[sum/gcd(sum,i)]++;

    ll res = 0;
    REP(i,sum+1){
        if(cnt[i] && g % i == 0){
            ll add = cnt[i] * fact[sum/i] % MOD;
            REP(j,K){
                add = (add * factinv[A[j]/i]) % MOD;
            }
            res = (res + add) % MOD;
        }
    }
    cout << divmod(res,sum,MOD) << endl;
}
0