codeforces-scrape

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

914.md (18894B)


      1 Source: https://codeforces.com/blog/entry/57250
      2 
      3 Tutorial is loading...
      4 
      5 **Author:** [crvineeth97](/profile/crvineeth97 "Expert crvineeth97")  
      6 **Testers:** [deepanshugarg](/profile/deepanshugarg "Expert deepanshugarg"), [nir123](/profile/nir123 "Candidate Master nir123")
      7 
      8 **Author's code**
      9 
     10 ```
     11 #include <bits/stdc++.h>
     12 using namespace std;
     13 
     14 int main()
     15 {
     16   long long ans=LLONG_MIN, n, x;
     17   cin>>n;
     18   for (long long i = 0; i < n; i++)
     19   {
     20     cin>>x;
     21     for (long long j = 0; j*j<=x; j++)
     22     if (j*j == x)
     23       x = LLONG_MIN;
     24     ans = max(ans, x);
     25   }
     26   cout << ans << endl;
     27   return 0;
     28 }
     29 ```
     30 
     31 Tutorial is loading...
     32 
     33 **Author:** [RohanRTiwari](/profile/RohanRTiwari "Expert RohanRTiwari")  
     34 **Tester:** [Superty](/profile/Superty "Candidate Master Superty")
     35 
     36 **Author's code**
     37 
     38 ```
     39 #include <bits/stdc++.h>
     40 using namespace std;
     41 using ll = long long;
     42 
     43 int cnt[100005];
     44 
     45 int main() {
     46   ios::sync_with_stdio(false);
     47 
     48   int n;
     49   cin >> n;
     50   while(n--) {
     51     int x;
     52     cin >> x;
     53     cnt[x]++;
     54   }
     55 
     56   for (int i = 1; i <= 1e5; i++) {
     57     if (cnt[i] % 2 == 1) {
     58       cout << "Conan\n";
     59       return 0;
     60     }
     61   }
     62   cout << "Agasa\n";
     63   return 0;
     64 }
     65 ```
     66 
     67 Tutorial is loading...
     68 
     69 **Author:** [aman_shahi2](/profile/aman_shahi2 "Expert aman_shahi2")  
     70 **Tester:** [mprocks](/profile/mprocks "Expert mprocks")
     71 
     72 **Author's code**
     73 
     74 ```
     75 #include <bits/stdc++.h>
     76 using namespace std;
     77 
     78 #define MOD 1000000007
     79 
     80 int dp[1004];
     81 long long ncr[1004][1004];
     82 
     83 int ones(int n)
     84 {
     85   int cnt = 0;
     86   while(n)
     87   {
     88     if(n%2 == 1)
     89     {
     90       cnt++;
     91     }
     92     n /= 2;
     93   }
     94   return cnt;
     95 }
     96 
     97 void calcncr()
     98 {
     99   for(int i = 0; i <= 1000; i++)
    100   {
    101     ncr[i][0] = 1;
    102   }
    103   for(int i = 1; i <= 1000; i++)
    104   {
    105     for(int j = 1; j <= 1000; j++)
    106     {
    107       ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j])%MOD;
    108     }
    109   }
    110 }
    111 
    112 int main()
    113 {
    114   string n;
    115   int k;
    116   calcncr();
    117 
    118   dp[1] = 0;
    119   for(int i = 2; i <= 1000; i++)
    120   {
    121     dp[i] = dp[ones(i)] + 1;
    122   }
    123 
    124   cin >> n >> k;
    125 
    126   if(k == 0)
    127   {
    128     cout << "1\n";
    129     return 0;
    130   }
    131 
    132   long long nones = 0, ans = 0;
    133   for(int i = 0; i < n.size(); i++)
    134   {
    135     if(n[i] == '0')
    136     {
    137       continue;
    138     }
    139     for(int j = max(nones, 1LL); j < 1000; j++)
    140     {
    141       if(dp[j] == k-1)
    142       {
    143         ans = (ans + ncr[n.size()-i-1][j-nones])%MOD;
    144         if(i == 0 && k == 1)
    145         {
    146           ans = (ans+MOD-1)%MOD;
    147         }
    148       }
    149     }
    150     nones++;
    151   }
    152 
    153   int cnt = 0;
    154   for(int i = 0; i < n.size(); i++)
    155   {
    156     if(n[i] == '1')
    157     {
    158       cnt++;
    159     }
    160   }
    161   if(dp[cnt] == k-1)
    162   {
    163     ans = (ans + 1)%MOD;
    164   }
    165   cout << ans << endl;
    166 
    167   return 0;
    168 }
    169 ```
    170 
    171 Tutorial is loading...
    172 
    173 **Author:** [RohanRTiwari](/profile/RohanRTiwari "Expert RohanRTiwari")  
    174 **Testers:** [codelegend](/profile/codelegend "Candidate Master codelegend"), [Superty](/profile/Superty "Candidate Master Superty")
    175 
    176 **Author's code**
    177 
    178 ```
    179 #include <bits/stdc++.h>
    180 using namespace std;
    181 using ll = long long;
    182 
    183 int tree[2000000];
    184 int trstp = 1;
    185 
    186 int gcd(int x, int y) {
    187   return y == 0 ? x : gcd(y, x % y);
    188 }
    189 
    190 void query(int root, int u, int v, int x, int s, int e, int& ans) {
    191   if (e < s || v < u || e < u || v < s) {
    192     return;
    193   } else if (u <= s && e <= v) {
    194     if (tree[root] % x == 0) {
    195       return;
    196     } else {
    197       while (root < trstp) {
    198         if (tree[2*root] % x != 0) {
    199           if (tree[2*root + 1] % x != 0) {
    200             ans += 2;
    201             return;
    202           }
    203           root = 2*root;
    204         } else {
    205           root = 2*root + 1;
    206         }
    207       }
    208       ans++;
    209       return;
    210     }
    211   }
    212   int mid = (s + e)/2;
    213   query(2*root, u, v, x, s, mid, ans);
    214   if (ans > 1) {
    215     return;
    216   }
    217   query(2*root + 1, u, v, x, mid + 1, e, ans);
    218 }
    219 
    220 void update(int p, int x) {
    221   p += trstp - 1;
    222   tree[p] = x;
    223 
    224   p /= 2;
    225   while (p > 0) {
    226     tree[p] = gcd(tree[2*p], tree[2*p + 1]);
    227     p /= 2;
    228   }
    229 }
    230 
    231 int main() {
    232   ios::sync_with_stdio(false);
    233    cin.tie(NULL);
    234 
    235   int n;
    236   cin >> n;
    237   while (trstp < n) {
    238     trstp *= 2;
    239   }
    240 
    241   for (int i = trstp; i < trstp + n; i++) {
    242     cin >> tree[i];
    243   }
    244   for (int i = trstp - 1; i >= 1; i--) {
    245     tree[i] = gcd(tree[2*i], tree[2*i + 1]);
    246   }
    247 
    248   int q;
    249   cin >> q;
    250   while (q--) {
    251     int t;
    252     cin >> t;
    253     if (t == 1) {
    254       int l, r;
    255       int x;
    256       cin >> l >> r >> x;
    257       int ans = 0;
    258       query(1, l, r, x, 1, trstp, ans);
    259       cout << (ans <= 1 ? "YES\n" : "NO\n");
    260     } else {
    261       int i;
    262       int y;
    263       cin >> i >> y;
    264       update(i, y);
    265     }
    266   }
    267 
    268   return 0;
    269 }
    270 ```
    271 
    272 Tutorial is loading...
    273 
    274 **Author:** [born2rule](/profile/born2rule "Candidate Master born2rule")  
    275 **Testers:** [devanshg27](/profile/devanshg27 "Candidate Master devanshg27"), [FundamentalEq](/profile/FundamentalEq "Candidate Master FundamentalEq")
    276 
    277 **Author's code**
    278 
    279 ```
    280 #include <bits/stdc++.h>
    281 #include <ext/pb_ds/assoc_container.hpp>
    282 #include <ext/pb_ds/tree_policy.hpp>
    283 using namespace std;
    284 using namespace __gnu_pbds;
    285 
    286 #define ll long long
    287 #define db long double
    288 #define ii pair<int,int>
    289 #define vi vector<int>
    290 #define fi first
    291 #define se second
    292 #define sz(a) (int)(a).size()
    293 #define all(a) (a).begin(),(a).end()
    294 #define pb emplace_back
    295 #define mp make_pair
    296 #define FN(i, n) for (int i = 0; i < (int)(n); ++i)
    297 #define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
    298 #define rep(i,a,b) for(int i=a;i<b;i++)
    299 #define repv(i,a,b) for(int i=b-1;i>=a;i--)
    300 #define SET(A, val) memset(A, val, sizeof(A))
    301 typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
    302 // order_of_key (val): returns the no. of values less than val
    303 // find_by_order (k): returns the kth largest element.(0-based)
    304 #define TRACE
    305 #ifdef TRACE
    306 #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    307 template <typename Arg1>
    308 void __f(const char* name, Arg1&& arg1){
    309   cerr << name << " : " << arg1 << std::endl;
    310 }
    311 template <typename Arg1, typename... Args>
    312 void __f(const char* names, Arg1&& arg1, Args&&... args){
    313   const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    314 }
    315 #else
    316 #define trace(...)
    317 #endif
    318 const int L=200005,N=(1<<20);
    319 //call dfsMCT,change solve and dfs1
    320 vi vpart[L],ad[L]; bool vis[L];//par:parent in cent|H:depth
    321 int SZ[L],par[L],part[L],H[L],cpart;//cpart:no of parts in cent
    322 ll ans[L],dp[L];
    323 string s;
    324 int dfsSZ(int u,int p=-1)
    325 {
    326   SZ[u]=1;//vpart[i]:nodes in part i
    327   for(int v:ad[u])
    328     if(!vis[v] && v!=p)
    329       SZ[u]+=dfsSZ(v,u);
    330   return SZ[u];
    331 }
    332 int dfsFC(int u,int r,int p=-1)
    333 {
    334   for(int v:ad[u])
    335     if(!vis[v] && v!=p)
    336       {
    337   if(SZ[v]>SZ[r]/2)
    338     return dfsFC(v,r,u);
    339       }
    340   return u;
    341 }
    342 int cnt[N],val[L],tmp[N];
    343 void dfs1(int u,int r,int p=-1)
    344 {
    345   dp[u]=0;
    346   if(p==r)
    347     {
    348       part[u]=++cpart;
    349       vpart[cpart].clear();
    350     }
    351   else if(p!=-1) part[u]=part[p];
    352   if(p!=-1) vpart[cpart].pb(u);
    353   for(int v1:ad[u])
    354     if(!vis[v1]&&v1!=p)
    355       {
    356   H[v1]=H[u]+1;
    357   val[v1]=(val[u]^(1<<(s[v1-1]-'a')));
    358   dfs1(v1,r,u);
    359       }
    360 }
    361 void dfs2(int u,int r,int par=-1)
    362 {
    363   dp[u]=cnt[val[u]];
    364   rep(i,0,20)
    365     dp[u]+=cnt[val[u]^(1<<i)];
    366   for(int v1:ad[u])
    367     {
    368       if(vis[v1] || v1==par) continue;
    369       dfs2(v1,r,u);
    370       dp[u]+=dp[v1];
    371     }
    372   ans[u]+=dp[u];
    373 }
    374 void solve(int r,int szr)
    375 {
    376   H[r]=cpart=0;
    377   val[r]=(1<<(s[r-1]-'a'));
    378   dfs1(r,r);
    379   rep(i,1,cpart+1)
    380     for(int v1:vpart[i])
    381       cnt[val[v1]]++;
    382   cnt[val[r]]++;
    383   rep(i,1,cpart+1)
    384     {
    385       for(int v1:vpart[i])
    386   {
    387     cnt[val[v1]]--;
    388     val[v1]^=(1<<(s[r-1]-'a'));
    389     tmp[val[v1]]++;
    390   }
    391       for(int v1:vpart[i])
    392   {
    393     if(tmp[val[v1]])
    394       {
    395         dp[r]+=(ll)tmp[val[v1]]*cnt[val[v1]];
    396         rep(j,0,20)
    397     dp[r]+=(ll)tmp[val[v1]]*cnt[val[v1]^(1<<j)];
    398         tmp[val[v1]]=0;
    399       }
    400   }
    401       dfs2(vpart[i][0],r,r);
    402       for(int v1:vpart[i])
    403   {
    404     val[v1]^=(1<<(s[r-1]-'a'));
    405     cnt[val[v1]]++;
    406   }
    407     }
    408   cnt[val[r]]--;
    409   dp[r]+=cnt[0];
    410   rep(i,0,20)
    411     dp[r]+=cnt[(1<<i)];
    412   ans[r]+=dp[r]/2;
    413   rep(i,1,cpart+1)
    414     for(int v1:vpart[i]) cnt[val[v1]]--;
    415 }
    416 void dfsMCT(int u,int p=-1)
    417 {
    418   dfsSZ(u);
    419   int r=dfsFC(u,u);
    420   par[r]=p; solve(r,SZ[u]); vis[r]=true;
    421   for(int v:ad[r])
    422     if(!vis[v]) dfsMCT(v,r);
    423 }
    424 int main()
    425 {
    426   std::ios::sync_with_stdio(false);
    427   cin.tie(NULL) ; cout.tie(NULL) ;
    428   int n,x,y;
    429   cin>>n;
    430   rep(i,1,n)
    431     {
    432       cin>>x>>y;
    433       ad[x].pb(y); ad[y].pb(x);
    434     }
    435   cin>>s;
    436   dfsMCT(1);
    437   rep(i,1,n+1) cout<<ans[i]+1<<" ";
    438   cout<<endl;
    439   return 0 ;
    440 }
    441 ```
    442 
    443 Tutorial is loading...
    444 
    445 There was an unexpected solution that involved bitset that runs in complexity *O*(*N*2 / 32). Have a look at [Syloviaely](/profile/Syloviaely "Legendary Grandmaster Syloviaely") 's code: [34364964](/contest/914/submission/34364964 "Submission 34364964 by Syloviaely")
    446 
    447 **Author:** [RohanRTiwari](/profile/RohanRTiwari "Expert RohanRTiwari")  
    448 **Testers:** [born2rule](/profile/born2rule "Candidate Master born2rule"), [devanshg27](/profile/devanshg27 "Candidate Master devanshg27"), [additya1998](/profile/additya1998 "Candidate Master additya1998"), [virus_1010](/profile/virus_1010 "Expert virus_1010"), [nir123](/profile/nir123 "Candidate Master nir123")
    449 
    450 **Author's code**
    451 
    452 ```
    453 #include <bits/stdc++.h>
    454 #define fr(x) scanf("%d", &x)
    455 #define SQRN 150
    456 using namespace std;
    457 
    458 const int sa = 2 * SQRN + 10;
    459 const int LEN = 100010;
    460 char s[LEN], sq[LEN], zstring[2*LEN];
    461 int z[2*LEN];
    462 string temps;
    463 
    464 struct SuffixAutomaton {
    465   int edges[26][sa], link[sa], length[sa], isTerminal[sa], dp1[sa], last;
    466   int sz;
    467   SuffixAutomaton() {
    468     last = 0;
    469     sz = 0;
    470   }
    471 
    472   void set(int k) {
    473     for(int i = 0; i < 26; ++i) edges[i][k] = -1;
    474   } 
    475 
    476   void build(string &s) { 
    477     link[0] = -1;
    478     length[0] = 0;
    479     last = 0;
    480     sz = 1;
    481     set(0);
    482 
    483     for(int i=0;i<s.size();i++) {
    484       set(sz);
    485       length[sz] = i+1;
    486       link[sz] = 0;
    487       int r = sz;
    488       ++sz;
    489 
    490       int p = last;
    491       while(p >= 0 && edges[s[i]-'a'][p] == -1) {
    492         edges[s[i] - 'a'][p] = r;
    493         p = link[p];
    494       }
    495       if(p != -1) {
    496         int q = edges[s[i] - 'a'][p];
    497         if(length[p] + 1 == length[q]) {
    498           link[r] = q;
    499         } else {
    500           for(int i = 0; i < 26; ++i) {
    501             edges[i][sz] = edges[i][q];
    502           }
    503           length[sz] = length[p] + 1;
    504           link[sz] = link[q];
    505           int qq = sz;
    506           ++sz;
    507           link[q] = qq;
    508           link[r] = qq;
    509           while(p >= 0 && edges[s[i] - 'a'][p] == q) {
    510             edges[s[i] - 'a'][p] = qq;
    511             p = link[p];
    512           }
    513         }
    514       }
    515       last = r;
    516     }
    517     for(int i = 0; i < sz; ++i) isTerminal[i] = 0, dp1[i] = -1; 
    518     int p = last;
    519     while(p > 0) {
    520       isTerminal[p] = 1;
    521       p = link[p];
    522     }
    523   }
    524 
    525   int solve(int pos) {
    526     if(dp1[pos] != -1) return dp1[pos];
    527     dp1[pos] = isTerminal[pos];
    528     for(int i=0; i<26; ++i){
    529       if(edges[i][pos] != -1) dp1[pos] += solve(edges[i][pos]);
    530     }
    531     return dp1[pos];
    532   }
    533 
    534   int run() {
    535     int cur = 0;
    536     for(int i=1; sq[i] != '\0'; ++i) {
    537       auto it = edges[sq[i] - 'a'][cur];
    538       if(it == -1) return 0;
    539       else cur = it;
    540     }
    541     return solve(cur);
    542   }
    543 } SA[800];
    544 
    545 void computeZ() {
    546   int l, r;
    547   z[0] = 0;
    548   l = r = -1;
    549   for(int i=1; zstring[i] != '\0'; ++i) {
    550     z[i]=0;
    551     if(r>i) {
    552       z[i]=min(z[i-l], r-i+1);
    553     }
    554     while(zstring[i+z[i]] == zstring[z[i]]) ++z[i];
    555     if(i+z[i]-1 > r) {
    556       r = i+z[i]-1;
    557       l = i;
    558     }
    559   }
    560 }
    561 
    562 int computeBrute(int l, int r, int sqlen) {
    563   int zslen = 0, ans = 0;
    564   for(int i=1; i<=sqlen; ++i) {
    565     zstring[zslen++] = sq[i];
    566   }
    567   zstring[zslen++] = '$';
    568   for(int i=l; i<=r; ++i) {
    569     zstring[zslen++] = s[i];
    570   }
    571   zstring[zslen] = '\0';
    572   computeZ();
    573   for(int i=1; i<zslen; ++i) {
    574     if(z[i] >= sqlen) {
    575       ++ans;
    576     }
    577   }
    578   return ans;
    579 }
    580 
    581 int main() {
    582   int q, typ, l, r, slen;
    583   char ch;
    584   scanf(" %s", &s[1]);
    585   slen = strlen(&s[1]);
    586   fr(q);
    587   for(int i=0; i<=slen; i+=SQRN) {
    588     temps = "";
    589     int tempr = min(i+SQRN-1, slen);
    590     for(int j=max(1, i); j<=tempr; ++j) {
    591       temps += s[j];
    592     }
    593     SA[i/SQRN].build(temps);
    594   }
    595   while(q--) {
    596     fr(typ);
    597     if(typ == 1) {
    598       scanf("%d %c", &l, &ch);
    599       s[l] = ch;
    600       temps = "";
    601       int bkt = l/SQRN;
    602       int tempr = min(slen, (bkt+1)*SQRN-1);
    603       for(int i=max(1,bkt*SQRN); i<=tempr; ++i) {
    604         temps += s[i];
    605       }
    606       SA[bkt].build(temps);
    607     }
    608     else {
    609       scanf("%d %d %s", &l, &r, &sq[1]);
    610       int sqlen = strlen(&sq[1]);
    611       if(sqlen >= SQRN || r-l <= 2*SQRN) {
    612         printf("%d\n", computeBrute(l, r, sqlen));
    613       }
    614       else {
    615         int lbkt = l/SQRN, rbkt = r/SQRN, ans = 0;
    616         for(int i=lbkt+1; i<rbkt; ++i) {
    617           ans += SA[i].run();
    618         }
    619         ans += computeBrute(l, (lbkt+1)*SQRN-1, sqlen);
    620         ans += computeBrute(rbkt*SQRN, r, sqlen);
    621         for(int i=lbkt+1; i<=rbkt; ++i) {
    622           ans += computeBrute(max(l, i*SQRN - sqlen + 1), min(r, i*SQRN + sqlen - 2), sqlen);
    623         }
    624         printf("%d\n", ans);
    625       }
    626     }
    627   }
    628   return 0;
    629 }
    630 ```
    631 
    632 Tutorial is loading...
    633 
    634 **Author:** [FundamentalEq](/profile/FundamentalEq "Candidate Master FundamentalEq")  
    635 **Tester:** [born2rule](/profile/born2rule "Candidate Master born2rule")
    636 
    637 **Author's code**
    638 
    639 ```
    640 #include <bits/stdc++.h>
    641 #include <ext/pb_ds/assoc_container.hpp>
    642 #include <ext/pb_ds/tree_policy.hpp>
    643 using namespace std;
    644 using namespace __gnu_pbds;
    645 
    646 #define ll long long
    647 #define db long double
    648 #define ii pair<int,int>
    649 #define vi vector<int>
    650 #define fi first
    651 #define se second
    652 #define sz(a) (int)(a).size()
    653 #define all(a) (a).begin(),(a).end()
    654 #define pb push_back
    655 #define mp make_pair
    656 #define FN(i, n) for (int i = 0; i < (int)(n); ++i)
    657 #define FEN(i,n) for (int i = 1;i <= (int)(n); ++i)
    658 #define rep(i,a,b) for(int i=a;i<b;i++)
    659 #define repv(i,a,b) for(int i=b-1;i>=a;i--)
    660 #define SET(A, val) memset(A, val, sizeof(A))
    661 typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>ordered_set ;
    662 // order_of_key (val): returns the no. of values less than val
    663 // find_by_order (k): returns the kth largest element.(0-based)
    664 #define TRACE
    665 #ifdef TRACE
    666 #define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
    667   template <typename Arg1>
    668   void __f(const char* name, Arg1&& arg1){
    669     cerr << name << " : " << arg1 << std::endl;
    670   }
    671   template <typename Arg1, typename... Args>
    672   void __f(const char* names, Arg1&& arg1, Args&&... args){
    673     const char* comma = strchr(names + 1, ','); cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
    674   }
    675 #else
    676 #define trace(...)
    677 #endif
    678 const int L = 17 ;
    679 const int L2 = 1<<L ;
    680 const int mod = 1e9+7 ;
    681 int sbits[L2] ;
    682 vi oddbits ;
    683 inline int add(int x,int y)
    684 {
    685   x+=y;
    686   if(x>=mod) x-=mod;
    687   if(x<0) x+=mod;
    688   return x;
    689 }
    690 inline int mult(int x,int y)
    691 {
    692   ll tmp=(ll)x*y;
    693   if(tmp>=mod) tmp%=mod;
    694   return tmp;
    695 }
    696 inline int pwmod(int x,int y)
    697 {
    698   int ans=1;
    699   while(y){if(y&1)ans=mult(ans,x);y>>=1;x=mult(x,x);}
    700   return ans;
    701 }
    702 vector<ii> nus[L] ;
    703 void zeta(int A[L2])
    704 {
    705   FN(i,L)
    706   {
    707     for(ii m:nus[i]) A[m.fi]=add(A[m.fi],A[m.se]) ;
    708   }
    709 }
    710 
    711 void meu(int A[L2])
    712 {
    713     for(int i:oddbits) A[i] = mod - A[i] ;
    714     zeta(A) ;
    715   for(int i:oddbits) A[i] = mod - A[i] ;
    716 }
    717 void conv(int A[L2],int B[L2])
    718 {
    719      zeta(A), zeta(B);//return
    720      FN(i,L2) A[i]=mult(A[i],B[i]);
    721      meu(A);
    722 }
    723 int t[L+1][L2],t1[L2] ;
    724 void subsetconv(int A[L2],int ans[L2])
    725 {
    726   FN(i,L2) t[sbits[i]][i] = A[i] ;
    727   FN(i,L+1) zeta(t[i]) ;
    728   FN(c,L+1) FN(a,c+1)
    729     {
    730     int *t2 = t[a], *t3 = t[c-a] ;
    731     FN(i,L2) t1[i]=mult(t2[i],t3[i]) ;
    732     meu(t1) ;
    733         FN(i,L2) if(sbits[i] == c) ans[i]=add(ans[i],t1[i]) ;
    734     }
    735 }
    736 vector<ii> su[L] ;
    737 
    738 void transform(int p[L2],bool inv=false){ int u,v;
    739 for(int len=1,l=2;l<=L2;len<<=1,l<<=1)for(int
    740 i=0;i<L2;i+=l) FN(j,len){
    741 u=p[i+j],v=p[i+j+len] ;
    742 if(inv) {p[i+j]=add(u,v),p[i+j+len]=add(u,-v);}
    743 else {p[i+j]=add(u,v),p[i+j+len]=add(u,-v);}}
    744 if(inv){int d=pwmod(L2,mod-2);FN(i,L2)p[i]=mult(p[i],d);} }
    745 
    746 int cnt[L2],fib[L2],A[L2],B[L2],C[L2],a[L2],b[L2],c[L2] ;
    747 
    748 int main()
    749 {
    750   std::ios::sync_with_stdio(false);
    751   cin.tie(NULL) ; cout.tie(NULL) ;
    752   FN(i,L2)
    753   {
    754     sbits[i] = __builtin_popcount(i) ;
    755     if(sbits[i] & 1) oddbits.emplace_back(i) ;
    756     FN(j,L)
    757     {
    758       if(i&(1<<j)) nus[j].emplace_back(mp(i,i^(1<<j))) ;
    759       if((i&(1<<j)) == 0) su[j].emplace_back(mp(i,i^(1<<j))) ;
    760     }
    761   }
    762   FN(i,L) reverse(all(su[i])) ;
    763   fib[1] = 1 ; rep(i,2,L2) fib[i] = add(fib[i-1],fib[i-2]) ;
    764 
    765   int N,x ; cin>>N ;
    766   FN(i,N)
    767   {
    768     cin>>x, ++cnt[x] ;
    769   }
    770 
    771   subsetconv(cnt,A) ;
    772   FN(i,L2) A[i]=mult(A[i],fib[i]) ;
    773 
    774   FN(i,L2) B[i]=mult(cnt[i],fib[i]);
    775   FN(i,L2) C[i]=cnt[i] ;
    776   transform(C) ;
    777   FN(i,L2) C[i]=mult(C[i],C[i]) ;
    778   transform(C,1) ;
    779   FN(i,L2) C[i]=mult(C[i],fib[i]) ;
    780   int ans = 0 ;
    781   FN(p,L)
    782   {
    783     FN(i,L2) a[i]=b[i]=c[i]=0 ;
    784     for(ii m:nus[p]) a[m.se]=A[m.fi],b[m.se]=B[m.fi],c[m.se]=C[m.fi] ;
    785     FN(i,L)
    786     {
    787       for(ii m:su[i])
    788       {
    789         a[m.fi]=add(a[m.fi],a[m.se]) ;
    790         b[m.fi]=add(b[m.fi],b[m.se]) ;
    791         c[m.fi]=add(c[m.fi],c[m.se]) ;
    792       }
    793     }
    794     FN(i,L2) a[i]=mult(a[i],mult(b[i],c[i])) ;
    795     meu(a) ;
    796     ans = add(ans,a[(1<<L)-1]) ;
    797   }
    798   ans = ans == 0 ? 0 : mod - ans ;
    799   cout << ans << "\n" ;
    800   return 0 ;
    801 }
    802 ```
    803 
    804 Tutorial is loading...
    805 
    806 **Author:** [Superty](/profile/Superty "Candidate Master Superty")  
    807 **Tester:** [codelegend](/profile/codelegend "Candidate Master codelegend")
    808 
    809 **Author's code**
    810 
    811 ```
    812 #include <bits/stdc++.h>
    813 using namespace std;
    814 using ll = long long;
    815 
    816 ll mod;
    817 const int maxn = 2e2 + 2;
    818 ll tree[maxn][maxn][maxn];
    819 ll c[maxn][maxn];
    820 
    821 int main() {
    822   ios::sync_with_stdio(false);
    823 
    824   int n, d;
    825   cin >> n >> d >> mod;
    826 
    827   c[0][0] = 1;
    828   for (int i = 1; i <= n; i++) {
    829     c[i][0] = 1;
    830     for (int j = 1; j <= i; j++) {
    831       c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    832     }
    833   }
    834 
    835   tree[1][1][0] = 1;
    836 
    837   for (int i = 1; i < n; i++) { // adding trees of size i
    838     for (int j = 1; j <= n; j++) {
    839       for (int k = 0; k <= d; k++) {
    840         tree[i + 1][j][k] = tree[i][j][k];
    841       }
    842     }
    843     ll tree_i = 0;
    844     for (int j = 0; j < d; j++) {
    845       tree_i = (tree_i + tree[i][i][j]) % mod;
    846     }
    847 
    848     ll ways = 1;
    849     for (int j = 1; i*j <= n && j <= d; j++) { // adding j such trees
    850       ways = (ways * c[i*j - 1][i - 1]) % mod; // ((ij)! tree[i]^(j-1))/(i!^j j!)
    851       for (int k = 1; k + i*j <= n; k++) { // adding to trees of size k
    852         ll cc = (ways * c[k + i*j - 1][k - 1]) % mod;
    853         for (int deg = 0; deg + j <= d; deg++) {
    854           tree[i + 1][k + i*j][deg + j] = (tree[i + 1][k + i*j][deg + j] + cc*((tree[i][k][deg]*tree_i) % mod)) % mod;
    855         }
    856       }
    857       ways = (ways * tree_i) % mod;
    858     }
    859   }
    860 
    861   ll total_trees = 0;
    862   for (int i = 0; i <= n - 1; i++) { // there are i vertices lying on paths increasing from the root
    863     for (int j = 0; j <= d; j++) {
    864       for (int k = 0; j + k <= d; k++) {
    865         if (k == 1) {
    866           continue;
    867         }
    868         total_trees = (total_trees + ((tree[n][i + 1][j]*tree[n][n - i][k]) % mod)) % mod;
    869       }
    870     }
    871   }
    872 
    873   cout << (2*((n*(n-1)) % mod)*total_trees) % mod << '\n';
    874 
    875   return 0;
    876 }
    877 ```