結果
問題 | No.603 hel__world (2) |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
#include <stdio.h>#include <string.h>#include <stdlib.h>#define P 1000003long 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);}