結果
問題 | No.1933 ABC String |
ユーザー |
|
提出日時 | 2022-05-06 18:20:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,097 bytes |
コンパイル時間 | 4,486 ms |
コンパイル使用メモリ | 255,112 KB |
最終ジャッジ日時 | 2025-01-29 02:54:39 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 11 TLE * 25 |
ソースコード
#include<bits/stdc++.h> #include<atcoder/all> using mint=atcoder::static_modint<998244353>; using namespace std; template<typename T> struct comb{ vector<T> dat,idat; comb(int mx=3000000):dat(mx+1,1),idat(mx+1,1){ for(int i=1;i<=mx;++i){ dat[i]=dat[i-1]*i; } idat[mx]/=dat[mx]; for(int i=mx;i>0;--i){ idat[i-1]=idat[i]*i; } } T operator()(int n,int k){ if(n==k){ return 1; } if(n<0||k<0||n<k){ return 0; } return dat[n]*idat[k]*idat[n-k]; } }; int main(){ string S; int A,B,C; cin>>S>>A>>B>>C; int N=S.size(); int P=count(S.begin(),S.end(),'a'),Q=count(S.begin(),S.end(),'b'),R=count(S.begin(),S.end(),'c'); int T=A-P,U=B-Q,V=C-R; comb<mint> Cb; auto f = [&](int n, int m) { return Cb(n+m-1,m-1); }; mint ans=0; for(int k = 0; k <= T+U; k++) { mint cnt1 = 0,cnt2=0; for(int i = 0; i <= k; i++) { cnt1+=f(i,R)*f(V,P+Q+T+U-i+1); } for(int i = max(0,k-U); i <= T && i <= k; i++) { cnt2+=Cb(k,i)*f(T-i,Q)*f(U-(k-i),P); } ans += cnt1*cnt2; } cout<<ans.val()<<endl; }