結果
問題 | No.2164 Equal Balls |
ユーザー | hotman78 |
提出日時 | 2022-12-15 06:00:08 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 788 ms / 5,000 ms |
コード長 | 1,114 bytes |
コンパイル時間 | 4,138 ms |
コンパイル使用メモリ | 243,124 KB |
実行使用メモリ | 18,804 KB |
最終ジャッジ日時 | 2023-08-08 16:37:31 |
合計ジャッジ時間 | 23,608 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,384 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,384 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 3 ms
4,380 KB |
testcase_07 | AC | 3 ms
4,380 KB |
testcase_08 | AC | 46 ms
7,552 KB |
testcase_09 | AC | 34 ms
6,280 KB |
testcase_10 | AC | 20 ms
5,036 KB |
testcase_11 | AC | 86 ms
10,900 KB |
testcase_12 | AC | 48 ms
7,568 KB |
testcase_13 | AC | 30 ms
5,916 KB |
testcase_14 | AC | 39 ms
6,944 KB |
testcase_15 | AC | 83 ms
10,636 KB |
testcase_16 | AC | 44 ms
7,284 KB |
testcase_17 | AC | 11 ms
4,380 KB |
testcase_18 | AC | 61 ms
9,056 KB |
testcase_19 | AC | 104 ms
12,964 KB |
testcase_20 | AC | 53 ms
8,092 KB |
testcase_21 | AC | 8 ms
4,376 KB |
testcase_22 | AC | 8 ms
4,380 KB |
testcase_23 | AC | 287 ms
7,584 KB |
testcase_24 | AC | 237 ms
14,424 KB |
testcase_25 | AC | 251 ms
5,776 KB |
testcase_26 | AC | 154 ms
14,252 KB |
testcase_27 | AC | 283 ms
16,376 KB |
testcase_28 | AC | 287 ms
16,316 KB |
testcase_29 | AC | 109 ms
6,512 KB |
testcase_30 | AC | 248 ms
11,816 KB |
testcase_31 | AC | 345 ms
6,936 KB |
testcase_32 | AC | 301 ms
15,184 KB |
testcase_33 | AC | 180 ms
5,576 KB |
testcase_34 | AC | 247 ms
7,680 KB |
testcase_35 | AC | 49 ms
4,380 KB |
testcase_36 | AC | 505 ms
17,236 KB |
testcase_37 | AC | 400 ms
6,888 KB |
testcase_38 | AC | 784 ms
18,652 KB |
testcase_39 | AC | 785 ms
18,636 KB |
testcase_40 | AC | 783 ms
18,620 KB |
testcase_41 | AC | 786 ms
18,548 KB |
testcase_42 | AC | 785 ms
18,500 KB |
testcase_43 | AC | 787 ms
18,804 KB |
testcase_44 | AC | 785 ms
18,708 KB |
testcase_45 | AC | 787 ms
18,544 KB |
testcase_46 | AC | 785 ms
18,624 KB |
testcase_47 | AC | 786 ms
18,620 KB |
testcase_48 | AC | 788 ms
18,496 KB |
testcase_49 | AC | 652 ms
6,236 KB |
testcase_50 | AC | 652 ms
6,140 KB |
testcase_51 | AC | 653 ms
6,192 KB |
testcase_52 | AC | 652 ms
6,240 KB |
testcase_53 | AC | 654 ms
6,200 KB |
ソースコード
#include<bits/stdc++.h> #include<atcoder/modint> #include<atcoder/convolution> using namespace std; using lint = long long; #define rep(i,n) for(lint i=0;i<(n);++i) using mint=atcoder::static_modint<998244353>; int main(){ lint n,m; cin>>n>>m; vector<lint>a(n),b(n); rep(i,n)cin>>a[i]; rep(i,n)cin>>b[i]; vector<vector<mint>>v(m*2+1); rep(i,2*m+1)v[i].resize(601,1); vector<mint>table(1000,1),inv(1000); rep(i,1000)table[i+1]=table[i]*(i+1); inv[999]=table[999].inv(); for(lint i=998;i>=0;--i)inv[i]=inv[i+1]*(i+1); auto comb=[&](auto a,auto b){ return table[a]*inv[b]*inv[a-b]; }; rep(i,n){ rep(k,601){ if(300-a[i]<=k&&k<=300+b[i]){ const lint j=k-300+a[i]; v[i%m+m][k]*=comb(a[i]+b[i],j); }else{ v[i%m+m][k]=0; } } // rep(j,a[i]+b[i]+1){ // const lint k=300-a[i]+j; // v[i%m+m][k]*=comb(a[i]+b[i],j); // // if(j<a[i])v[i%(m)+(m)][k]=j+1; // // else if(j<b[i])v[i%(m)+(m)][k]=comb(a[i]); // // else v[i%(m)+(m)][k]=a[i]+b[i]-j+1; // } } for(lint i=m-1;i>=1;--i){ v[i]=atcoder::convolution(v[i*2],v[i*2+1]); } cout<<v[1][300*m].val()<<endl; }