結果
問題 | No.603 hel__world (2) |
ユーザー | testestest |
提出日時 | 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 |
ソースコード
#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); }