1478.md (20142B)
1 Source: https://codeforces.com/blog/entry/87294 2 3 Thanks for joining us today! Here is the editorial for today's problems: 4 5 [1478A - Nezzar and Colorful Balls](/contest/1478/problem/A "Codeforces Round 698 (Div. 2)") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include<bits/stdc++.h> 15 using namespace std; 16 17 #define rep(i,n) for (int i=0;i<(int)(n);++i) 18 #define rep1(i,n) for (int i=1;i<=(int)(n);++i) 19 #define range(x) begin(x), end(x) 20 #define sz(x) (int)(x).size() 21 #define pb push_back 22 #define F first 23 #define S second 24 25 typedef long long ll; 26 typedef unsigned long long ull; 27 typedef long double ld; 28 typedef pair<int, int> pii; 29 typedef vector<int> vi; 30 31 const int maxn=200007; 32 int t,n; 33 int cnt[maxn]; 34 int main(){ 35 ios::sync_with_stdio(false); 36 cin.tie(0), cout.tie(0); 37 cin>>t; 38 while (t--){ 39 cin>>n; 40 rep1(i,n) cnt[i]=0; 41 rep1(i,n){ 42 int u; 43 cin>>u; 44 cnt[u]++; 45 } 46 int mx=0; 47 rep1(i,n) mx=max(mx,cnt[i]); 48 cout<<mx<<"\n"; 49 } 50 return 0; 51 } 52 ``` 53 54 [1478B - Nezzar and Lucky Number](/contest/1478/problem/B "Codeforces Round 698 (Div. 2)") 55 56 **Tutorial** 57 58 Tutorial is loading... 59 60 **Solution** 61 62 ``` 63 #include<bits/stdc++.h> 64 using namespace std; 65 66 const int maxn=207; 67 int t,d,q; 68 bool dp[maxn]; 69 int main(){ 70 ios::sync_with_stdio(false); 71 cin.tie(0), cout.tie(0); 72 cin>>t; 73 while (t--){ 74 memset(dp,0,sizeof(dp)); 75 dp[0]=1; 76 cin>>q>>d; 77 if (!d) d+=10; 78 int mx=d*10; 79 for (int i=0;10*i+d<=mx;++i){ 80 for (int j=0;10*i+d+j<=mx;++j){ 81 dp[10*i+d+j]|=dp[j]; 82 } 83 } 84 while (q--){ 85 int u; 86 cin>>u; 87 if (u>=mx||dp[u]) cout<<"YES\n"; 88 else cout<<"NO\n"; 89 } 90 } 91 return 0; 92 } 93 ``` 94 95 [1478C - Nezzar and Symmetric Array](/contest/1478/problem/C "Codeforces Round 698 (Div. 2)") 96 97 **Tutorial** 98 99 Tutorial is loading... 100 101 **Solution** 102 103 ``` 104 #include<bits/stdc++.h> 105 #define int long long 106 using namespace std; 107 108 const int maxn=200007; 109 int t; 110 int n,a[maxn],b[maxn],d[maxn]; 111 112 signed main(){ 113 ios::sync_with_stdio(false); 114 cin.tie(0), cout.tie(0); 115 cin>>t; 116 while (t--){ 117 cin>>n; 118 for (int i=0;i<2*n;++i) cin>>a[i]; 119 sort(a,a+2*n,greater<int>()); 120 for (int i=0;i<n;++i){ 121 if (a[i*2]!=a[i*2+1]){ 122 cout<<"NO\n"; 123 goto cont; 124 } 125 b[i]=a[i*2]; 126 } 127 for (int i=1;i<n;++i){ 128 if (b[i-1]==b[i]||(b[i-1]-b[i])%(2*(n-i))){ 129 cout<<"NO\n"; 130 goto cont; 131 } 132 d[i]=(b[i-1]-b[i])/2/(n-i); 133 } 134 for (int i=1;i<n;++i){ 135 b[n-1]-=2*i*d[i]; 136 } 137 if (b[n-1]<=0||b[n-1]%(2*n)) cout<<"NO\n"; 138 else cout<<"YES\n"; 139 140 cont:; 141 } 142 return 0; 143 } 144 ``` 145 146 [1477A - Nezzar and Board](/contest/1477/problem/A "Codeforces Round 698 (Div. 1)") 147 148 **Tutorial** 149 150 Tutorial is loading... 151 152 **Solution** 153 154 ``` 155 #include<bits/stdc++.h> 156 #define int long long 157 using namespace std; 158 159 const int maxn=200007; 160 int t; 161 int n,k; 162 int x[maxn]; 163 164 signed main(){ 165 ios::sync_with_stdio(false); 166 cin.tie(0), cout.tie(0); 167 cin>>t; 168 while (t--){ 169 cin>>n>>k; 170 for (int i=0;i<n;++i) cin>>x[i]; 171 sort(x,x+n); 172 int g=0; 173 for (int i=1;i<n;++i){ 174 g=__gcd(g,x[i]-x[0]); 175 } 176 if ((k-x[0])%g) cout<<"NO\n"; 177 else cout<<"YES\n"; 178 } 179 return 0; 180 } 181 ``` 182 183 [1477B - Nezzar and Binary String](/contest/1477/problem/B "Codeforces Round 698 (Div. 1)") 184 185 **Tutorial** 186 187 Tutorial is loading... 188 189 **Solution** 190 191 ``` 192 #include<bits/stdc++.h> 193 using namespace std; 194 195 #define rep(i,n) for (int i=0;i<(int)(n);++i) 196 #define rep1(i,n) for (int i=1;i<=(int)(n);++i) 197 #define range(x) begin(x), end(x) 198 #define sz(x) (int)(x).size() 199 #define pb push_back 200 #define F first 201 #define S second 202 203 typedef long long ll; 204 typedef unsigned long long ull; 205 typedef long double ld; 206 typedef pair<int, int> pii; 207 typedef vector<int> vi; 208 209 const int maxn=200007; 210 set<int> seg; // segment: [seg[i],seg[i+1]) 211 int n,q,t,prv; 212 int l[maxn],r[maxn]; 213 bool val[maxn]; 214 string s; 215 int main(){ 216 ios::sync_with_stdio(false); 217 cin.tie(0), cout.tie(0); 218 cin>>t; 219 while (t--){ 220 cin>>n>>q; 221 cin>>s; 222 rep(i,q) cin>>l[i]>>r[i], l[i]--; 223 reverse(l,l+q), reverse(r,r+q); 224 seg.clear(); 225 rep(i,n) seg.insert(i), val[i]=s[i]-'0'; 226 seg.insert(n); 227 auto add=[&](int u){ 228 if (seg.find(u)==seg.end()){ 229 auto ret=*prev(seg.upper_bound(u)); 230 val[u]=val[ret]; 231 seg.insert(u); 232 } 233 }; 234 rep(i,q){ 235 add(l[i]), add(r[i]); 236 vi remv; 237 remv.clear(); 238 int sum[2]; 239 memset(sum,0,sizeof(sum)); 240 auto iter=seg.find(l[i]); 241 while (1){ 242 if (*iter==r[i]) break; 243 int prev=*iter; 244 iter=next(iter); 245 if (*iter<r[i]) remv.pb(*iter); 246 sum[val[prev]]+=*iter-prev; 247 } 248 if (sum[0]==sum[1]){ 249 cout<<"-\n"; 250 goto cont; 251 } 252 if (sum[0]<sum[1]) val[l[i]]=1; 253 else val[l[i]]=0; 254 for (auto c:remv) seg.erase(c); 255 } 256 prv=0; 257 for (auto c:seg){ 258 if (!c) continue; 259 for (int i=prv;i<c;++i) cout<<val[prv]; 260 prv=c; 261 } 262 cout<<"\n"; 263 cont:; 264 } 265 } 266 ``` 267 268 [1477C - Nezzar and Nice Beatmap](/contest/1477/problem/C "Codeforces Round 698 (Div. 1)") 269 270 **Tutorial** 271 272 Tutorial is loading... 273 274 **Solution** 275 276 ``` 277 #include<bits/stdc++.h> 278 using namespace std; 279 280 const int maxn=6007; 281 282 int n; 283 int x[maxn],y[maxn]; 284 vector<int> perm; 285 signed main(){ 286 ios::sync_with_stdio(false); 287 cin.tie(0), cout.tie(0); 288 cin>>n; 289 for (int i=0;i<n;++i) cin>>x[i]>>y[i]; 290 for (int i=0;i<n;++i){ 291 perm.push_back(i); 292 for (int j=i;j>1;--j){ 293 if (1ll*(x[perm[j]]-x[perm[j-1]])*(x[perm[j-1]]-x[perm[j-2]])+1ll*(y[perm[j]]-y[perm[j-1]])*(y[perm[j-1]]-y[perm[j-2]])>=0){ 294 swap(perm[j],perm[j-1]); 295 } 296 else{ 297 break; 298 } 299 } 300 } 301 for (auto c:perm) cout<<c+1<<" "; 302 303 } 304 ``` 305 306 [1477D - Nezzar and Hidden Permutations](/contest/1477/problem/D "Codeforces Round 698 (Div. 1)") 307 308 **Tutorial** 309 310 Tutorial is loading... 311 312 **Solution** 313 314 ``` 315 #include<bits/stdc++.h> 316 using namespace std; 317 318 const int maxn=500007; 319 320 struct info{ 321 int idx,val; 322 friend bool operator<(info u,info v){ 323 return u.val==v.val?u.idx<v.idx:u.val<v.val; 324 } 325 }; 326 327 struct stars{ 328 int rt; 329 vector<int> leaves; 330 }; 331 set<int> rv; // remained vertices 332 set<int> g[maxn]; // original graph 333 set<int> t[maxn]; // dfs tree 334 set<info> d; 335 int deg[maxn]; 336 int n,m; 337 int perm1[maxn],perm2[maxn]; 338 vector<stars> res; 339 340 void dfs(int u){ 341 rv.erase(u); 342 int crt=0; 343 while (1){ 344 auto iter=rv.upper_bound(crt); 345 if (iter==rv.end()) break; 346 int v=*iter; 347 crt=v; 348 if (g[u].find(v)!=g[u].end()) continue; 349 t[u].insert(v), t[v].insert(u); 350 dfs(v); 351 } 352 } 353 354 int main(){ 355 ios::sync_with_stdio(false); 356 cin.tie(0), cout.tie(0); 357 int tc; 358 cin>>tc; 359 while (tc--){ 360 cin>>n>>m; 361 for (int i=1;i<=n;++i) g[i].clear(), t[i].clear(); 362 rv.clear(), res.clear(), d.clear(); 363 for (int i=1;i<=m;++i){ 364 int u,v; 365 cin>>u>>v; 366 g[u].insert(v), g[v].insert(u); 367 } 368 for (int i=1;i<=n;++i) rv.insert(i); 369 while (rv.size()>0){ 370 int u=*(rv.begin()); 371 dfs(u); 372 } 373 int rem=n; 374 for (int i=1;i<=n;++i){ 375 deg[i]=t[i].size(); 376 if (deg[i]){ 377 d.insert((info){i,deg[i]}); 378 } 379 else{ 380 perm1[i]=perm2[i]=rem; 381 rem--; 382 } 383 } 384 while (d.size()){ 385 int idx=(*(d.begin())).idx; 386 int f=*(t[idx].begin()); 387 vector<int> leaves; 388 leaves.clear(); 389 d.erase((info){f,deg[f]}); 390 for (auto c:t[f]){ 391 d.erase((info){c,deg[c]}); 392 if (deg[c]==1) leaves.push_back(c); 393 else deg[c]--, d.insert((info){c,deg[c]}), t[c].erase(f); 394 } 395 res.push_back((stars){f,leaves}); 396 } 397 int l=0,r=0; 398 for (auto c:res){ 399 perm1[c.rt]=++l; 400 for (auto ls:c.leaves){ 401 perm1[ls]=++l; 402 perm2[ls]=++r; 403 } 404 perm2[c.rt]=++r; 405 } 406 for (int i=1;i<=n;++i) cout<<perm1[i]<<" "; 407 cout<<"\n"; 408 for (int i=1;i<=n;++i) cout<<perm2[i]<<" "; 409 cout<<"\n"; 410 } 411 } 412 ``` 413 414 [1477E - Nezzar and Tournaments](/contest/1477/problem/E "Codeforces Round 698 (Div. 1)") 415 416 **Tutorial** 417 418 Tutorial is loading... 419 420 **Solution** 421 422 ``` 423 //#pragma GCC optimize("Ofast") 424 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") 425 //#pragma GCC optimize("unroll-loops") 426 #include<bits/stdc++.h> 427 using namespace std; 428 429 #define rep(i,n) for (int i=0;i<(int)(n);++i) 430 #define rep1(i,n) for (int i=1;i<=(int)(n);++i) 431 #define range(x) begin(x), end(x) 432 #define sz(x) (int)(x).size() 433 #define pb push_back 434 #define F first 435 #define S second 436 437 typedef long long ll; 438 typedef unsigned long long ull; 439 typedef long double ld; 440 typedef pair<int, int> pii; 441 typedef vector<int> vi; 442 443 namespace internal { 444 445 // @param n `0 <= n` 446 // @return minimum non-negative `x` s.t. `n <= 2**x` 447 int ceil_pow2(int n) { 448 int x = 0; 449 while ((1U << x) < (unsigned int)(n)) x++; 450 return x; 451 } 452 453 } 454 455 template <class S, S (*op)(S, S), S (*e)()> struct segtree { 456 public: 457 segtree() : segtree(0) {} 458 segtree(int n) : segtree(std::vector<S>(n, e())) {} 459 segtree(const std::vector<S>& v) : _n(int(v.size())) { 460 log = internal::ceil_pow2(_n); 461 size = 1 << log; 462 d = std::vector<S>(2 * size, e()); 463 for (int i = 0; i < _n; i++) d[size + i] = v[i]; 464 for (int i = size - 1; i >= 1; i--) { 465 update(i); 466 } 467 } 468 469 void set(int p, S x) { 470 assert(0 <= p && p < _n); 471 p += size; 472 d[p] = x; 473 for (int i = 1; i <= log; i++) update(p >> i); 474 } 475 476 S get(int p) { 477 assert(0 <= p && p < _n); 478 return d[p + size]; 479 } 480 481 S prod(int l, int r) { 482 assert(0 <= l && l <= r && r <= _n); 483 S sml = e(), smr = e(); 484 l += size; 485 r += size; 486 487 while (l < r) { 488 if (l & 1) sml = op(sml, d[l++]); 489 if (r & 1) smr = op(d[--r], smr); 490 l >>= 1; 491 r >>= 1; 492 } 493 return op(sml, smr); 494 } 495 496 S all_prod() { return d[1]; } 497 498 template <bool (*f)(S)> int max_right(int l) { 499 return max_right(l, [](S x) { return f(x); }); 500 } 501 template <class F> int max_right(int l, F f) { 502 assert(0 <= l && l <= _n); 503 assert(f(e())); 504 if (l == _n) return _n; 505 l += size; 506 S sm = e(); 507 do { 508 while (l % 2 == 0) l >>= 1; 509 if (!f(op(sm, d[l]))) { 510 while (l < size) { 511 l = (2 * l); 512 if (f(op(sm, d[l]))) { 513 sm = op(sm, d[l]); 514 l++; 515 } 516 } 517 return l - size; 518 } 519 sm = op(sm, d[l]); 520 l++; 521 } while ((l & -l) != l); 522 return _n; 523 } 524 525 template <bool (*f)(S)> int min_left(int r) { 526 return min_left(r, [](S x) { return f(x); }); 527 } 528 template <class F> int min_left(int r, F f) { 529 assert(0 <= r && r <= _n); 530 assert(f(e())); 531 if (r == 0) return 0; 532 r += size; 533 S sm = e(); 534 do { 535 r--; 536 while (r > 1 && (r % 2)) r >>= 1; 537 if (!f(op(d[r], sm))) { 538 while (r < size) { 539 r = (2 * r + 1); 540 if (f(op(d[r], sm))) { 541 sm = op(d[r], sm); 542 r--; 543 } 544 } 545 return r + 1 - size; 546 } 547 sm = op(d[r], sm); 548 } while ((r & -r) != r); 549 return 0; 550 } 551 552 private: 553 int _n, size, log; 554 std::vector<S> d; 555 556 void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } 557 }; 558 559 560 const int maxn=500007; 561 const int maxm=1000007; 562 int n,m,k,q,t; 563 ll sum; 564 int a[maxn],b[maxn]; 565 566 struct S{ 567 int cnt; 568 ll sum; 569 }; 570 571 S e(){ 572 return {0,0}; 573 } 574 575 S op(S l,S r){ 576 return {l.cnt+r.cnt,l.sum+r.sum}; 577 } 578 579 580 581 signed main(){ 582 ios::sync_with_stdio(false); 583 cin.tie(0), cout.tie(0); 584 segtree<S,op,e> seg_a(maxm),seg_b(maxm); 585 auto fa=[&](int x){ 586 if (x>m||x<=0) cerr<<x<<endl; 587 assert(x<=m&&x>0); 588 return seg_a.max_right(0,[&](S l){return l.cnt<x;}); 589 }; 590 auto fb=[&](int x){ 591 assert(x<=n&&x>0); 592 return seg_b.max_right(0,[&](S l){return l.cnt<x;}); 593 }; 594 auto solve=[&](int start,int coef){ 595 // cerr<<"start coef:"<<start<<" "<<coef<<endl; 596 int mn=min(fa(1),fb(1)); 597 if (start<=k+mn) return 1ll*(n-m)*start+sum; 598 auto ret=seg_b.prod(0,start-k); 599 // cerr<<"ret:"<<ret.cnt<<" "<<ret.sum<<endl; 600 return 1ll*coef*(start-k-mn)+1ll*(n-m)*start+sum+ret.sum-1ll*ret.cnt*(start-k); 601 }; 602 cin>>m>>n>>q; 603 rep1(i,m) {cin>>a[i],sum+=a[i]; auto ret=seg_a.get(a[i]); ret.cnt++, ret.sum+=a[i], seg_a.set(a[i],ret);} 604 rep1(i,n) {cin>>b[i],sum-=b[i]; auto ret=seg_b.get(b[i]); ret.cnt++, ret.sum+=b[i], seg_b.set(b[i],ret);} 605 sum+=1ll*(m-n)*k; 606 auto res=[&](){ 607 ll ans=-1e15; 608 ans=max(ans,solve(fb(1),m)); 609 ans=max(ans,solve(fb(n),m)); 610 ans=max(ans,solve(fa(1),m-1)); 611 ans=max(ans,solve(fa(m),m-1)); 612 int threshold=n>1?fb(n-1):0; 613 if (k+threshold<=1e6){ 614 int pos=max(seg_a.prod(0,k+threshold).cnt,1); 615 ans=max(ans,solve(fa(pos),m-1)); 616 int nxt_pos=seg_a.max_right(0,[&](S l){return l.cnt<=pos;}); 617 if (nxt_pos<maxm) ans=max(ans,solve(nxt_pos,m-1)); 618 } 619 cout<<ans<<"\n"; 620 }; 621 while (q--){ 622 int op,idx,x; 623 cin>>op; 624 if (op==1){ 625 cin>>idx>>x; 626 auto ret=seg_a.get(a[idx]); 627 ret.cnt--, ret.sum-=a[idx]; 628 seg_a.set(a[idx],ret); 629 sum-=a[idx]; 630 sum+=x; 631 a[idx]=x; 632 ret=seg_a.get(x); 633 ret.cnt++, ret.sum+=x; 634 seg_a.set(x,ret); 635 } 636 if (op==2){ 637 cin>>idx>>x; 638 auto ret=seg_b.get(b[idx]); 639 ret.cnt--, ret.sum-=b[idx]; 640 seg_b.set(b[idx],ret); 641 sum+=b[idx]; 642 sum-=x; 643 b[idx]=x; 644 ret=seg_b.get(x); 645 ret.cnt++, ret.sum+=x; 646 seg_b.set(x,ret); 647 } 648 if (op==3){ 649 cin>>k; 650 sum+=(m-n)*k; 651 res(); 652 sum-=(m-n)*k; 653 } 654 } 655 return 0; 656 } 657 ``` 658 659 [1477F - Nezzar and Chocolate Bars](/contest/1477/problem/F "Codeforces Round 698 (Div. 1)") 660 661 **Tutorial** 662 663 Tutorial is loading... 664 665 **Solution** 666 667 ``` 668 //#pragma GCC optimize("Ofast") 669 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx") 670 //#pragma GCC optimize("unroll-loops") 671 #include<bits/stdc++.h> 672 #define int long long 673 using namespace std; 674 675 #define rep(i,n) for (int i=0;i<(int)(n);++i) 676 #define rep1(i,n) for (int i=1;i<=(int)(n);++i) 677 #define range(x) begin(x), end(x) 678 #define sz(x) (int)(x).size() 679 #define pb push_back 680 #define F first 681 #define S second 682 683 typedef long long ll; 684 typedef unsigned long long ull; 685 typedef long double ld; 686 typedef pair<int, int> pii; 687 typedef vector<int> vi; 688 689 const ll mod = (119 << 23) + 1, root = 62; // = 998244353 690 // For p < 2^30 there is also e.g. 5 << 25, 7 << 26, 479 << 21 691 // and 483 << 21 (same root). The last two are > 10^9. 692 693 ll modpow(ll b, ll e) { 694 ll ans = 1; 695 for (; e; b = b * b % mod, e /= 2) 696 if (e & 1) ans = ans * b % mod; 697 return ans; 698 } 699 700 typedef vector<ll> vl; 701 void ntt(vl &a) { 702 int n = sz(a), L = 31 - __builtin_clz(n); 703 static vl rt(2, 1); 704 for (static int k = 2, s = 2; k < n; k *= 2, s++) { 705 rt.resize(n); 706 ll z[] = {1, modpow(root, mod >> s)}; 707 for(int i=k;i<2*k;++i) rt[i] = rt[i / 2] * z[i & 1] % mod; 708 } 709 vi rev(n); 710 for(int i = 0; i < n; ++i) rev[i] = (rev[i / 2] | (i & 1) << L) / 2; 711 for(int i = 0; i < n; ++i) if (i < rev[i]) swap(a[i], a[rev[i]]); 712 for (int k = 1; k < n; k *= 2) 713 for (int i = 0; i < n; i += 2 * k) for(int j = 0; j < k; ++j) { 714 ll z = rt[j + k] * a[i + j + k] % mod, &ai = a[i + j]; 715 a[i + j + k] = ai - z + (z > ai ? mod : 0); 716 ai += (ai + z >= mod ? z - mod : z); 717 } 718 } 719 vl conv(const vl &a, const vl &b) { 720 if (a.empty() || b.empty()) return {}; 721 int s = sz(a) + sz(b) - 1, B = 32 - __builtin_clz(s), n = 1 << B; 722 int inv = modpow(n, mod - 2); 723 vl L(a), R(b), out(n); 724 L.resize(n), R.resize(n); 725 ntt(L), ntt(R); 726 for (int i = 0; i < n; ++i) out[-i & (n - 1)] = (ll)L[i] * R[i] % mod * inv % mod; 727 ntt(out); 728 return {out.begin(), out.begin() + s}; 729 } 730 731 const int maxn=1007; 732 733 int n,k; 734 int l[maxn]; 735 736 struct polynomial{ 737 int n,m; 738 vector<vi> poly; 739 polynomial(vector<vi> &po):poly(po){ 740 n = sz(poly) - 1, m = sz(poly[0]) - 1; 741 } 742 vi rsz(int nn,int mm){ 743 assert(nn>n&&mm>m); 744 vi ret; 745 ret.resize(nn*mm+1,0); 746 for (int i=0;i<=n;++i){ 747 for (int j=0;j<=m;++j){ 748 ret[i*mm+j]=poly[i][j]; 749 assert(poly[i][j]<mod&&poly[i][j]>=0); 750 } 751 } 752 return ret; 753 } 754 755 friend polynomial operator*(polynomial l,polynomial r){ 756 vector<vi> po; 757 po.clear(); 758 po.resize(l.n+r.n+1,vi(l.m+r.m+1,0)); 759 auto lpo=l.rsz(l.n+1,l.m+r.m+1),rpo=r.rsz(r.n+1,l.m+r.m+1),res=conv(lpo,rpo); 760 // for (auto c:res) cout<<c<<" "; 761 // cout<<endl; 762 // cout<<sz(lpo)<<" "<<sz(rpo)<<" "<<sz(res)<<endl; 763 for (int i=0;i<=l.n+r.n;++i){ 764 for (int j=0;j<=l.m+r.m;++j){ 765 po[i][j]=res[i*(l.m+r.m+1)+j]; 766 } 767 } 768 // cout<<"hi"<<endl; 769 return po; 770 } 771 }; 772 773 vector<polynomial> poly; 774 int f[5007]; 775 signed main(){ 776 ios::sync_with_stdio(false); 777 cin.tie(0), cout.tie(0); 778 cin>>n>>k; 779 f[0]=1; 780 rep1(i,5000) f[i]=f[i-1]*i%mod; 781 int L=0; 782 rep(i,n) cin>>l[i], L+=l[i]; 783 rep(i,n){ 784 vi res0,res1; 785 res0.clear(), res1.clear(); 786 res0.pb(1), res1.pb(0); 787 int sgn=1; 788 rep1(j,l[i]/k){ 789 int tmp0,tmp1; 790 sgn=-sgn; 791 if (l[i]==k*j) { 792 tmp0=tmp1=0; 793 } 794 else{ 795 tmp0=(modpow((l[i]-k*j)*modpow(L,mod-2)%mod,j)%mod)*modpow(f[j],mod-2)%mod, tmp1=(modpow((l[i]-k*j)*modpow(L,mod-2)%mod,j-1)%mod)*modpow(f[j-1],mod-2)%mod; 796 if (sgn<0) tmp0=(tmp0?mod-tmp0:tmp0), tmp1=(tmp1?mod-tmp1:tmp1); 797 } 798 // cerr<<i<<" "<<j<<":"<<tmp0<<" "<<tmp1<<endl; 799 res0.pb(tmp0), res1.pb(tmp1); 800 } 801 vector<vi> p({res0,res1}); 802 polynomial po(p); 803 poly.pb(po); 804 } 805 for (int k=1;k<=n;k<<=1){ 806 for (int i=k;i<n;i+=2*k){ 807 poly[i-k]=poly[i]*poly[i-k]; 808 } 809 } 810 int ans=0; 811 // x^{j-i}exp((1-k*j/L)) -> (j-i)!/((k*j/L)^{j-i+1}) = (j-i)!L^{j-i+1}/(k*j)^{j-i+1} 812 rep(i,poly[0].n+1){ 813 rep(j,poly[0].m+1){ 814 if (i>j) {assert(poly[0].poly[i][j]==0); continue;} 815 if (j==0) {assert(poly[0].poly[i][j]==1); continue;} 816 if (k*j==L) {assert(poly[0].poly[i][j]==0); continue;} 817 int num=f[j-i]*modpow(L,j-i+1)%mod,den=modpow(k*j,j-i+1)%mod; 818 // cerr<<i<<","<<j<<":"<<poly[0].poly[i][j]<<" "<<num<<" "<<den<<endl; 819 ans=(ans+(num*modpow(den,mod-2)%mod)*poly[0].poly[i][j]%mod)%mod; 820 } 821 } 822 if (ans>0) cout<<mod-ans<<endl; 823 else cout<<0<<endl; 824 return 0; 825 } 826 ```