結果
問題 | No.2345 max(l,r) |
ユーザー | kotatsugame |
提出日時 | 2023-06-09 23:43:42 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,163 bytes |
コンパイル時間 | 914 ms |
コンパイル使用メモリ | 81,748 KB |
実行使用メモリ | 7,140 KB |
最終ジャッジ日時 | 2023-08-30 14:51:53 |
合計ジャッジ時間 | 5,740 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | WA | - |
testcase_02 | AC | 18 ms
4,376 KB |
testcase_03 | AC | 17 ms
4,380 KB |
testcase_04 | AC | 16 ms
4,380 KB |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | AC | 17 ms
4,376 KB |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | AC | 27 ms
4,688 KB |
testcase_23 | AC | 28 ms
4,624 KB |
testcase_24 | AC | 9 ms
4,376 KB |
testcase_25 | AC | 18 ms
5,380 KB |
testcase_26 | AC | 20 ms
5,560 KB |
testcase_27 | AC | 20 ms
6,332 KB |
testcase_28 | AC | 11 ms
4,380 KB |
testcase_29 | AC | 18 ms
4,376 KB |
testcase_30 | AC | 10 ms
4,648 KB |
testcase_31 | AC | 24 ms
4,376 KB |
testcase_32 | AC | 12 ms
4,380 KB |
testcase_33 | AC | 14 ms
4,380 KB |
testcase_34 | AC | 4 ms
4,380 KB |
testcase_35 | AC | 8 ms
4,460 KB |
testcase_36 | AC | 9 ms
4,380 KB |
testcase_37 | AC | 11 ms
4,380 KB |
testcase_38 | AC | 30 ms
5,432 KB |
testcase_39 | AC | 35 ms
4,992 KB |
testcase_40 | AC | 32 ms
4,436 KB |
testcase_41 | AC | 30 ms
5,176 KB |
testcase_42 | AC | 31 ms
4,588 KB |
testcase_43 | AC | 29 ms
4,380 KB |
testcase_44 | AC | 36 ms
5,136 KB |
testcase_45 | AC | 39 ms
5,636 KB |
testcase_46 | AC | 36 ms
4,568 KB |
testcase_47 | AC | 33 ms
5,180 KB |
testcase_48 | WA | - |
testcase_49 | WA | - |
testcase_50 | WA | - |
testcase_51 | WA | - |
testcase_52 | WA | - |
testcase_53 | WA | - |
testcase_54 | WA | - |
testcase_55 | WA | - |
testcase_56 | WA | - |
testcase_57 | WA | - |
testcase_58 | WA | - |
testcase_59 | WA | - |
testcase_60 | WA | - |
testcase_61 | WA | - |
testcase_62 | WA | - |
testcase_63 | WA | - |
testcase_64 | WA | - |
testcase_65 | WA | - |
testcase_66 | WA | - |
testcase_67 | WA | - |
testcase_68 | AC | 63 ms
4,584 KB |
ソースコード
#include<iostream> #include<vector> #include<algorithm> #include<cassert> #include<atcoder/modint> using namespace std; #include<vector> template<typename T> struct combination{ vector<T>fac,ifac; combination(size_t N=0):fac(1,1),ifac(1,1) { make_table(N); } void make_table(size_t N) { if(fac.size()>N)return; size_t now=fac.size(); N=max(N,now*2); fac.resize(N+1); ifac.resize(N+1); for(size_t i=now;i<=N;i++)fac[i]=fac[i-1]*i; ifac[N]=1/fac[N]; for(size_t i=N;i-->now;)ifac[i]=ifac[i+1]*(i+1); } T factorial(size_t n) { make_table(n); return fac[n]; } T invfac(size_t n) { make_table(n); return ifac[n]; } T P(size_t n,size_t k) { if(n<k)return 0; make_table(n); return fac[n]*ifac[n-k]; } T C(size_t n,size_t k) { if(n<k)return 0; make_table(n); return fac[n]*ifac[n-k]*ifac[k]; } T H(size_t n,size_t k) { if(n==0)return k==0?1:0; return C(n-1+k,k); } }; using mint=atcoder::modint998244353; combination<mint>C; int N,M,A[2<<17]; vector<pair<int,int> >a; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin>>T; for(;T--;) { cin>>N>>M; for(int i=0;i<N;i++)cin>>A[i]; sort(A,A+N); a.clear(); for(int i=0;i<N;i++) { if(a.empty()||a.back().first<A[i])a.push_back(make_pair(A[i],1)); else a.back().second++; } int L=0,R=0; mint way=1; int cnt=0; for(int i=a.size()-1;i>=1;i--) { int val=a[i].first; int l=max(N-L-val,0),r=max(N-R-val,0); if(L>N-L-l)l=0; if(R>N-R-r)r=0; if(l>=1&&r>=1&&l+r==a[i].second) {//use l,r way*=C.C(l+r,l); L+=l,R+=r; cnt+=2; if(L<R)swap(L,R); } else if(l==a[i].second&&r==a[i].second) { assert(L==R); way*=2; L+=l; cnt++; } else if(l==a[i].second) { L+=l; cnt++; } else if(r==a[i].second) { R+=r; cnt++; if(L<R)swap(L,R); } else { way=0; break; } } mint ans=0; int val=a[0].first; if(max(L,R)==val) { ans+=way*C.C(M,cnt+1); } { int x=val-L; int y=val-R; if(x>=1&&y>=1&&L<=y+R&&L+x>=R&&x+y==val) { ans+=way*C.C(x+y,x)*C.C(M,cnt+2); } } cout<<ans.val()<<"\n"; } }