結果

問題 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 #
raw source code 

#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;
}
0