結果

問題 No.603 hel__world (2)
コンテスト
ユーザー 👑 testestest
提出日時 2017-11-08 06:15:50
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 356 ms / 3,000 ms
コード長 1,836 bytes
コンパイル時間 1,589 ms
コンパイル使用メモリ 31,488 KB
実行使用メモリ 37,980 KB
最終ジャッジ日時 2024-11-30 11:31:07
合計ジャッジ時間 4,742 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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