結果

問題 No.603 hel__world (2)
ユーザー 👑 testestesttestestest
提出日時 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);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0