結果
問題 | No.2512 Mountain Sequences |
ユーザー | kotatsugame |
提出日時 | 2023-10-20 22:38:02 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 925 ms / 3,000 ms |
コード長 | 1,660 bytes |
コンパイル時間 | 974 ms |
コンパイル使用メモリ | 78,240 KB |
実行使用メモリ | 24,572 KB |
最終ジャッジ日時 | 2023-10-20 22:38:31 |
合計ジャッジ時間 | 23,351 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge10 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 309 ms
18,296 KB |
testcase_01 | AC | 308 ms
18,372 KB |
testcase_02 | AC | 312 ms
18,372 KB |
testcase_03 | AC | 310 ms
18,296 KB |
testcase_04 | AC | 309 ms
18,372 KB |
testcase_05 | AC | 307 ms
18,296 KB |
testcase_06 | AC | 320 ms
18,296 KB |
testcase_07 | AC | 305 ms
18,296 KB |
testcase_08 | AC | 309 ms
18,300 KB |
testcase_09 | AC | 313 ms
18,296 KB |
testcase_10 | AC | 915 ms
22,016 KB |
testcase_11 | AC | 907 ms
21,576 KB |
testcase_12 | AC | 874 ms
22,180 KB |
testcase_13 | AC | 888 ms
22,016 KB |
testcase_14 | AC | 909 ms
21,180 KB |
testcase_15 | AC | 898 ms
23,400 KB |
testcase_16 | AC | 885 ms
22,016 KB |
testcase_17 | AC | 900 ms
22,016 KB |
testcase_18 | AC | 925 ms
22,260 KB |
testcase_19 | AC | 891 ms
24,572 KB |
testcase_20 | AC | 819 ms
19,868 KB |
testcase_21 | AC | 832 ms
19,876 KB |
testcase_22 | AC | 859 ms
19,880 KB |
testcase_23 | AC | 848 ms
19,868 KB |
testcase_24 | AC | 819 ms
19,876 KB |
testcase_25 | AC | 787 ms
19,140 KB |
testcase_26 | AC | 812 ms
19,140 KB |
testcase_27 | AC | 352 ms
19,140 KB |
testcase_28 | AC | 486 ms
19,416 KB |
ソースコード
#include<iostream> #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; mint ans[2<<17]; int N[2<<17],M[2<<17]; vector<int>Qi[2<<17]; mint tmp[2<<17]; mint solve(int n,int m) { mint ret=0; for(int i=0;i<m;i++)ret+=C.C(2*i,n-1); return ret; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T;cin>>T; for(int i=0;i<T;i++) { cin>>N[i]>>M[i]; Qi[N[i]].push_back(i); } const int B=1000; for(int m=0;m<=200000;m+=B)tmp[m]=mint::raw(m); const mint inv2=mint::raw(2).inv(); for(int n=1;n<=200000;n++) { for(int qi:Qi[n]) { int m=M[qi]; int qm=m/B; mint now=tmp[qm*B]; for(int i=qm*B;i<m;i++)now+=C.C(2*i,n-1); ans[qi]=now; } for(int m=0;m<=200000;m+=B)tmp[m]=(C.C(2*m,n+1)-tmp[m])*inv2; } for(int i=0;i<T;i++)cout<<ans[i].val()<<"\n"; }