結果
問題 | No.603 hel__world (2) |
ユーザー |
![]() |
提出日時 | 2017-12-11 10:00:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 546 ms / 3,000 ms |
コード長 | 1,104 bytes |
コンパイル時間 | 1,718 ms |
コンパイル使用メモリ | 176,076 KB |
実行使用メモリ | 38,732 KB |
最終ジャッジ日時 | 2024-11-30 20:59:01 |
合計ジャッジ時間 | 12,420 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
コンパイルメッセージ
main.cpp:22:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 22 | main(){ | ^~~~
ソースコード
#include <bits/stdc++.h> using namespace std; #define long long long #define M 1000003 char T[M]; long S[26],x[M],y[M]; int inv[M],fac[M]; long r=1; int mc; void m(long t){ while(t){ r=r*fac[t%M]%M; t/=M; mc+=t; } } main(){ fac[0]=1; for(int i=1;i<M;++i){ fac[i]=1ll*fac[i-1]*i%M; long e,s=M,t=i,u=1,v=0; while(s){ e=t/s; t-=e*s; u-=e*v; swap(t,s); swap(u,v); } inv[i]=(u+M)%M; } for(int c=0;c<26;++c)cin>>S[c]; cin>>T; for(int c=0;c<26;++c){ priority_queue<pair<double,int>> q; int n=0,s=0,t=-1; for(int i=0;!i||T[i-1];++i){ if(T[i]==c+'a'){ if(t<0)t=i; }else{ if(t>=0){ int xl=i-t; x[n]=xl; ++n; s+=xl; if(s>S[c])r=0; t=-1; } } } if(s) { long d=S[c]/s; for(int j=0;j<n;++j){ y[j]=x[j]*d; q.push(make_pair(1.*~y[j]/x[j],j)); } for(S[c]%=s;S[c]--;){ int j=q.top().second;q.pop(); ++y[j]; q.push(make_pair(1.*~y[j]/x[j],j)); } for(int j=0;j<n;++j){ m(y[j]); r=inv[r];mc=-mc; m(y[j]-x[j]); m(x[j]); r=inv[r];mc=-mc; } } } cout<<!mc*r; }