結果

問題 No.125 悪の花弁
ユーザー EmKjpEmKjp
提出日時 2015-03-31 08:47:29
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 174 ms / 5,000 ms
コード長 2,415 bytes
コンパイル時間 1,006 ms
コンパイル使用メモリ 86,588 KB
実行使用メモリ 31,008 KB
最終ジャッジ日時 2023-09-17 00:36:47
合計ジャッジ時間 2,212 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 120 ms
29,468 KB
testcase_01 AC 123 ms
29,728 KB
testcase_02 AC 164 ms
30,924 KB
testcase_03 AC 174 ms
31,008 KB
testcase_04 AC 158 ms
30,352 KB
testcase_05 AC 160 ms
30,420 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<numeric>
#include<functional>
#include<complex>

using namespace std;
#define BET(a,b,c) ((a)<=(b)&&(b)<(c))
#define FOR(i,n) for(int i=0,i##_end=(int(n));i<i##_end;i++)
#define SZ(x) (int)(x.size())
#define ALL(x) (x).begin(),(x).end()
#define MP make_pair
#define FOR_EACH(it,v) for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++)
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll_t;
const int MAXN = 1000000+2;
const int mod = 1000000007;
ll_t fact[MAXN];
ll_t inv[MAXN];
ll_t inv_fact[MAXN];

void setup(){
    fact[0] = fact[1] = 1;
    for(int i=2;i<MAXN;i++) fact[i] = (1LL * fact[i-1] * i) % mod;
    inv[1] = 1;
    for(int i=2;i<MAXN;i++) inv[i] =  (mod - (mod / i) * inv[mod % i] % mod);
    inv_fact[0] = inv_fact[1] = 1;
    for(int i=2;i<MAXN;i++){
        inv_fact[i] = (1LL * inv_fact[i-1] * inv[i]) % mod;
    }
}

ll_t choose_mod(long long s , long long t) // O(1) , mod is prime
{
    if(s<0 || t<0) return 0 ;
    if(s < t) return 0 ;
    if(s >= mod){ // Lucas' theorem
        return choose_mod(s%mod, t%mod) * choose_mod(s/mod, t/mod) % mod;
    }
    return fact[s]*inv_fact[t]%mod*inv_fact[s-t]%mod;
}
int main()
{
    setup();
    
    int K;
    cin>>K;
    VI C(K);
    FOR(i,K) scanf("%d",&C[i]);
    int total = 0 ;
    FOR(i,K) total += C[i];
    long long ans = 0 ;
    VI result(total+1, -1);
    FOR(i,total){
        int len = __gcd(i, total);
        int num = total / len;
        if(result[len] != -1){
            ans += result[len];
            ans %= mod;
            continue;
        }
        long long pattern = 1;
        bool canDivide = true;
        int subTotal = len;
        FOR(i,K){
            if(C[i] % num) {
                canDivide = false;
                break;
            }else {
                int c = C[i] / num;
                pattern *= choose_mod(subTotal, c);
                pattern %= mod;
                subTotal -= c;
            }
        }
        if(canDivide){
            result[len] = pattern;
        }else {
            result[len] = 0;
        }
        ans += result[len];
        ans %= mod;
    }
    ans *= inv[total];
    ans %= mod;
    cout<<ans<<endl;
    return 0;
}
0