結果

問題 No.603 hel__world (2)
ユーザー testestesttestestest
提出日時 2017-11-08 06:15:50
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 405 ms / 3,000 ms
コード長 1,836 bytes
コンパイル時間 1,869 ms
コンパイル使用メモリ 31,044 KB
実行使用メモリ 70,020 KB
最終ジャッジ日時 2023-08-20 10:02:26
合計ジャッジ時間 6,027 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 20 ms
33,368 KB
testcase_01 AC 19 ms
27,300 KB
testcase_02 AC 17 ms
21,144 KB
testcase_03 AC 19 ms
27,276 KB
testcase_04 AC 19 ms
29,400 KB
testcase_05 AC 19 ms
27,288 KB
testcase_06 AC 17 ms
21,084 KB
testcase_07 AC 20 ms
33,488 KB
testcase_08 AC 17 ms
19,224 KB
testcase_09 AC 18 ms
21,272 KB
testcase_10 AC 17 ms
21,212 KB
testcase_11 AC 69 ms
68,852 KB
testcase_12 AC 68 ms
68,732 KB
testcase_13 AC 68 ms
68,792 KB
testcase_14 AC 17 ms
21,272 KB
testcase_15 AC 17 ms
21,200 KB
testcase_16 AC 17 ms
21,080 KB
testcase_17 AC 17 ms
21,136 KB
testcase_18 AC 17 ms
21,136 KB
testcase_19 AC 17 ms
21,268 KB
testcase_20 AC 22 ms
21,256 KB
testcase_21 AC 22 ms
21,200 KB
testcase_22 AC 24 ms
60,120 KB
testcase_23 AC 24 ms
55,964 KB
testcase_24 AC 25 ms
62,164 KB
testcase_25 AC 405 ms
69,820 KB
testcase_26 AC 378 ms
69,816 KB
testcase_27 AC 385 ms
70,020 KB
testcase_28 AC 350 ms
39,796 KB
testcase_29 AC 22 ms
21,204 KB
testcase_30 AC 19 ms
21,080 KB
testcase_31 AC 17 ms
19,088 KB
testcase_32 AC 22 ms
19,108 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define P 1000003
long fact[P+10],inv[P+10];

typedef struct {
	long x;
	int a;
	int n;
} frac;

int cmp(const void*p1,const void*p2){
	//x/aが小さい方が前（-1を返す）
	frac*f1=(frac*)p1,*f2=(frac*)p2;
	long q1=(*f1).x/(*f1).a,q2=(*f2).x/(*f2).a;
	if(q1==q2){
		double r1=(double)((*f1).x%(*f1).a)/(*f1).a,r2=(double)((*f2).x%(*f2).a)/(*f2).a;
		return r1<r2?-1:r1>r2;
	}
	return q1<q2?-1:1;
}

char s[1000010];
int len;
long X[30],x[500010];
int A[30],aa[30][500010],cnt[30];
long ans;
frac arr[500010];

//二項係数
int choose(long n,long r){
	long ret=1;
	while(n&&r){
		int nn=n%P,rr=r%P;
		if(n<r)return 0;
		ret=(ret*fact[nn])%P*((inv[fact[rr]]*inv[fact[nn-rr]])%P)%P;
		n/=P;r/=P;
	}
	return ret;
}

//本体
int f(int t){
	int *a=aa[t];
	long quo=X[t]/A[t],res=X[t]%A[t];
	int len=0,need=X[t];
	for(int i=0;i<cnt[t];i++){
		x[i]=quo*a[i]+res*a[i]/A[t];//floor(X[i]*a[i]/A[i])
		need-=x[i];
		long temp=res*a[i]%A[t]+cnt[t]*a[i];
		int k=1;
		while(temp>=A[t]){
			arr[len].x=x[i]+k;
			arr[len].a=a[i];
			arr[len].n=i;
			temp-=A[t];
			len++;
			k++;
		}
	}
	qsort(arr,len,sizeof(frac),cmp);
	for(int i=0;i<need;i++)x[arr[i].n]++;
	long ret=1;
	for(int i=0;i<cnt[t];i++)ret=ret*choose(x[i],a[i])%P;
	return ret;

}

int main(){
	//逆元
	inv[1]=1;
	for(int i=2;i<P;i++)inv[i]=inv[P%i]*(P-P/i)%P;
	//階乗
	fact[0]=1;
	for(int i=1;i<P;i++)fact[i]=fact[i-1]*i%P;
	//入力
	for(int i=0;i<26;i++)scanf("%ld\n",X+i);
	scanf("%s",s);
	len=strlen(s);
	for(int i=0;i<len;i++){
		int ch=s[i]-'a';
		A[ch]++;
		aa[ch][cnt[ch]]=1;
		while(s[i+1]==s[i])i++,aa[ch][cnt[ch]]++,A[ch]++;
		cnt[ch]++;
	}
	//0チェック
	for(int i=0;i<26;i++)if(A[i]>X[i]){puts("0");return 0;}
	//やる
	ans=1;
	for(int i=0;i<26;i++)if(A[i])ans=ans*f(i)%P;
	printf("%ld\n",ans);
}
0