結果

問題 No.125 悪の花弁
ユーザー ey429ey429
提出日時 2015-03-05 12:25:01
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 41 ms / 5,000 ms
コード長 1,046 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 28,332 KB
実行使用メモリ 32,564 KB
最終ジャッジ日時 2023-09-06 13:44:38
合計ジャッジ時間 1,090 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 33 ms
31,716 KB
testcase_01 AC 30 ms
27,500 KB
testcase_02 AC 38 ms
28,560 KB
testcase_03 AC 41 ms
28,520 KB
testcase_04 AC 38 ms
32,564 KB
testcase_05 AC 30 ms
28,908 KB
権限があれば一括ダウンロードができます

ソースコード

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