codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```