結果

問題 No.125 悪の花弁
ユーザー ey429
提出日時 2015-03-05 12:25:01
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 42 ms / 5,000 ms
コード長 1,046 bytes
コンパイル時間 204 ms
コンパイル使用メモリ 25,216 KB
実行使用メモリ 31,100 KB
最終ジャッジ日時 2024-06-24 08:17:21
合計ジャッジ時間 994 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 6
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:40:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |         scanf("%d",&m);
      |         ~~~~~^~~~~~~~~
main.cpp:43:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |                 scanf("%d",&S[i]);
      |                 ~~~~~^~~~~~~~~~~~

ソースコード

diff #
プレゼンテーションモードにする

#include<stdio.h>
#define M 1000000007
#define N 1000000
void swap(int &a,int &b){
    int p=a;a=b;b=p;
}
int gcd(int a,int b){
    if(a<b)swap(a,b);
    if(a%b==0)return b;
    else return gcd(b,a%b);
}
long long fact[N+1];
long long rev[N+1];
long long frev[N+1];
void init(int n){
    int i;
    fact[0]=1;
    for(i=1;i<=n;i++)fact[i]=fact[i-1]*i%M;
    rev[1]=1;
    for(i=2;i<=n;i++)rev[i]=M-(M/i)*rev[M%i]%M;
    frev[0]=1;
    for(i=1;i<=n;i++)frev[i]=frev[i-1]*rev[i]%M;
}
long long C(int n,int k){
    if(k<0||k>n)return 0;
    return fact[n]*(frev[k]*frev[n-k]%M)%M;
}
int S[100000];
long long dp[N+1];
int main(){
    int n,m,i,j;
    scanf("%d",&m);
    n=0;
    for(i=0;i<m;i++){
        scanf("%d",&S[i]);
        n+=S[i];
    }
    init(n);
    int d=n;
    for(i=0;i<m;i++)d=gcd(d,S[i]);
    for(i=0;i<=d;i++)dp[i]=0;
    long long ans=0;
    for(i=d;i>=1;i--){
        if(d%i!=0)continue;
        long long res=1;
        int s=n/i;
        for(j=0;j<m;j++){
            res=res*C(s,S[j]/i)%M;
            s-=S[j]/i;
        }
        for(j=2;i*j<=d;j++)res=(res+M-dp[i*j])%M;
        dp[i]=res;
        ans=(ans+dp[i]*rev[n/i])%M;
    }
    printf("%lld\n",ans);
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0