codeforces-scrape

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

2237.md (19515B)


      1 Source: https://codeforces.com/blog/entry/154603
      2 
      3 Thank you for participating! We hope you enjoyed the problems.
      4 
      5 [2237A - Destroying Towers](/contest/2237/problem/A)
      6 
      7 Idea: [_ja](/profile/_ja "Master _ja") Preparation: [_ja](/profile/_ja "Master _ja") & [quacksaysduck](/profile/quacksaysduck "Expert quacksaysduck")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Implementation**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 
     18 using namespace std;
     19 
     20 int main() {
     21     int t;
     22     cin >> t;
     23     while (t--) {
     24         int n;
     25         cin >> n;
     26         int x = 10000, y = 0;
     27         for (int i = 0; i < n; ++i) {
     28             int z;
     29             cin >> z;
     30             x = min(x, z), y += x;
     31         }
     32         cout << y << '\n';
     33     }
     34     return 0;
     35 }
     36 ```
     37 
     38 [2237B - Annoying the Ghost](/contest/2237/problem/B)
     39 
     40 Idea: [quacksaysduck](/profile/quacksaysduck "Expert quacksaysduck") Preparation: [_ja](/profile/_ja "Master _ja") & [quacksaysduck](/profile/quacksaysduck "Expert quacksaysduck") & [Boboge](/profile/Boboge "Grandmaster Boboge")
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 **Implementation**
     47 
     48 ```
     49 #include <bits/stdc++.h>
     50 
     51 using namespace std;
     52 
     53 int main() {
     54     int t;
     55     cin >> t;
     56     while (t--) {
     57         int n;
     58         cin >> n;
     59         vector<int> a(n), c(n);
     60         for (int i = 0; i < n; i++) cin >> a[i];
     61         set<int> s;
     62         for (int i = 0; i < n; i++) {
     63             int x;
     64             cin >> x;
     65             s.insert(x);
     66         }
     67         bool y = true;
     68         for (int i = 0; i < n; ++i) {
     69             auto it = s.lower_bound(a[i]);
     70             if (it == s.end()) {
     71                 y = false;
     72                 break;
     73             }
     74             c[i] = *it;
     75             s.erase(it);
     76         }
     77         if (!y) {
     78             cout << -1 << '\n';
     79             continue;
     80         }
     81         int ans = 0;
     82         for (int i = 0; i < n; ++i) {
     83             for (int j = i + 1; j < n; ++j) {
     84                 if (c[i] > c[j]) {
     85                     ans++;
     86                 }
     87             }
     88         }
     89         cout << ans << '\n';
     90     }
     91     return 0;
     92 }
     93 ```
     94 
     95 [2237C - Duck Surplus](/contest/2237/problem/C)
     96 
     97 Idea: [quacksaysduck](/profile/quacksaysduck "Expert quacksaysduck") Preparation: [Boboge](/profile/Boboge "Grandmaster Boboge")
     98 
     99 **Tutorial**
    100 
    101 Tutorial is loading...
    102 
    103 **Implementation**
    104 
    105 ```
    106 #include <bits/stdc++.h>
    107 
    108 using namespace std;
    109 
    110 using i64 = long long;
    111 
    112 void run() {
    113     int n;
    114     cin >> n;
    115     vector<int> a(n);
    116     for (int i = 0; i < n; ++i) {
    117         cin >> a[i];
    118     }
    119     i64 ans = 0;
    120     for (int i = 0; i < n; ++i) {
    121         if (ans > a[i]) {
    122             ans += a[i];
    123         } else {
    124             ans = a[i];
    125         }
    126     }
    127     cout << ans << '\n';
    128 }
    129 
    130 int main() {
    131     ios_base::sync_with_stdio(false);
    132     cin.tie(nullptr);
    133     int T = 1;
    134     cin >> T;
    135     while (T--) {
    136         run();
    137     }
    138     return 0;
    139 }
    140 ```
    141 
    142 [2237D - Fullmetal Bitchemist](/contest/2237/problem/D)
    143 
    144 Idea: [zeemanz](/profile/zeemanz "Grandmaster zeemanz") Preparation: [__baozii__](/profile/__baozii__ "International Grandmaster __baozii__")
    145 
    146 **Tutorial**
    147 
    148 Tutorial is loading...
    149 
    150 **Implementation(python)**
    151 
    152 ```
    153 for _ in range(int(input())):
    154     n = int(input())
    155     a = [1, 0, 0]
    156     x = 0
    157     ans = 0
    158     pre = ""
    159     y = 0
    160     for c in input():
    161         if c == "0":
    162             x -= 1
    163         else:
    164             x += 1
    165         x %= 3
    166         if c == pre:
    167             y = 1
    168         else:
    169             y += 1
    170         pre = c
    171         ans += sum(a) - a[x]
    172         a[x] += 1
    173         ans -= (y - 1) // 2
    174     print(ans)
    175 ```
    176 
    177 [2237E - Permutation Commutation](/contest/2237/problem/E)
    178 
    179 Idea: [_ja](/profile/_ja "Master _ja") Preparation: [Boboge](/profile/Boboge "Grandmaster Boboge")
    180 
    181 **Tutorial**
    182 
    183 Tutorial is loading...
    184 
    185 **Implementation**
    186 
    187 ```
    188 #include <bits/stdc++.h>
    189 
    190 using namespace std;
    191 
    192 void run(int testCase) {
    193     int n;
    194     cin >> n;
    195     vector<int> a(n), b(n);
    196     for (int i = 0; i < n; ++i) {
    197         cin >> a[i];
    198         a[i]--;
    199     }
    200     for (int i = 0; i < n; ++i) {
    201         cin >> b[i];
    202         if (b[i] != -1) {
    203             b[i]--;
    204         }
    205     }
    206     vector<int> vis(n);
    207     for (int i = 0; i < n; ++i) {
    208         if (b[i] != -1 and !vis[i]) {
    209             int j = i;
    210             while (true) {
    211                 if (vis[j]) break;
    212                 vis[j] = 1;
    213                 if (b[a[j]] == -1) {
    214                     b[a[j]] = a[b[j]];
    215                 } else if (b[a[j]] != a[b[j]]) {
    216                     cout << "NO\n";
    217                     return;
    218                 }
    219                 j = a[j];
    220             }
    221         }
    222     }
    223     vector<int> cnt(n);
    224     for (int i = 0; i < n; ++i) {
    225         if (b[i] == -1) continue;
    226         cnt[b[i]]++;
    227     }
    228     for (int i = 0; i < n; ++i) {
    229         if (cnt[i] > 1) {
    230             cout << "NO\n";
    231             return;
    232         }
    233     }
    234     vector<int> vis1(n), vis2(n);
    235     vector<vector<int>> cycle1(n + 1), cycle2(n + 1);
    236     for (int i = 0; i < n; ++i) {
    237         if (b[i] == -1 and !vis1[i]) {
    238             int j = i, len = 0;
    239             while (!vis1[j]) {
    240                 vis1[j] = 1;
    241                 len++;
    242                 j = a[j];
    243             }
    244             cycle1[len].push_back(i);
    245         }
    246     }
    247     for (int i = 0; i < n; ++i) {
    248         if (cnt[i] == 0 and !vis2[i]) {
    249             int j = i, len = 0;
    250             while (!vis2[j]) {
    251                 vis2[j] = 1;
    252                 len++;
    253                 j = a[j];
    254             }
    255             cycle2[len].push_back(i);
    256         }
    257     }
    258     for (int len = 1; len <= n; ++len) {
    259         for (int i = 0; i < cycle1[len].size(); ++i) {
    260             int x = cycle1[len][i], y = cycle2[len][i];
    261             while (b[x] == -1) {
    262                 b[x] = y;
    263                 x = a[x];
    264                 y = a[y];
    265             }
    266         }
    267     }
    268     cout << "YES\n";
    269     for (int i = 0; i < n; ++i) {
    270         cout << b[i] + 1 << " \n"[i == n - 1];
    271     }
    272 }
    273 
    274 int main() {
    275     ios_base::sync_with_stdio(false);
    276     cin.tie(nullptr);
    277     int T = 1;
    278     cin >> T;
    279     for (int t = 1; t <= T; ++t) {
    280         run(t);
    281     }
    282     return 0;
    283 }
    284 ```
    285 
    286 [2237F - Paint the Array](/contest/2237/problem/F)
    287 
    288 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") Preparation: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") & [Sugar_fan](/profile/Sugar_fan "International Grandmaster Sugar_fan")
    289 
    290 **Tutorial**
    291 
    292 Tutorial is loading...
    293 
    294 **Implementation**
    295 
    296 ```
    297 #include<bits/stdc++.h>
    298 
    299 using namespace std;
    300 int a[500000], pref[500001], suf[500001], dpvl[500001], inf = 1000000000;
    301 
    302 int main() {
    303     ios::sync_with_stdio(false), cin.tie(0);
    304     int T, n, m, i, c;
    305     for (cin >> T; T > 0; T--) {
    306         cin >> n >> m;
    307         for (i = 0; i < n; i++) {
    308             cin >> a[i];
    309             a[i]--;
    310         }
    311         for (i = 0; i <= n; i++) {
    312             pref[i] = -inf;
    313             suf[i] = -inf;
    314             dpvl[i] = -inf;
    315         }
    316         pref[0] = 0;
    317         for (i = 0; i < n; i++) {
    318             c = suf[i];
    319             if (i - a[i] >= 0) {
    320                 c = max(c, dpvl[i - a[i]]);
    321                 c = max(c, pref[i - a[i]]);
    322             }
    323             c++;
    324             pref[i + 1] = max(pref[i], c);
    325             suf[i + 1] = max(suf[i + 1], suf[i]);
    326             if (i - a[i] >= 0)dpvl[i - a[i]] = max(dpvl[i - a[i]], c);
    327             if (i - a[i] + m <= n)suf[i - a[i] + m] = max(suf[i - a[i] + m], c);
    328         }
    329         cout << n - max(suf[n], 0) << '\n';
    330     }
    331     return 0;
    332 }
    333 ```
    334 
    335 [2237G - Send GCDs](/contest/2237/problem/G)
    336 
    337 Idea: [_ja](/profile/_ja "Master _ja") Preparation: [Boboge](/profile/Boboge "Grandmaster Boboge")
    338 
    339 **Tutorial**
    340 
    341 Tutorial is loading...
    342 
    343 **Implementation**
    344 
    345 ```
    346 #include <bits/stdc++.h>
    347 
    348 #define sz(a) (int)(a).size()
    349 
    350 using namespace std;
    351 
    352 using i64 = long long;
    353 
    354 string type;
    355 
    356 constexpr int P = 110;
    357 constexpr int N = 1e6;
    358 constexpr int sz_v = (1 << 18);
    359 
    360 vector<int> ps, pks, v;
    361 array<int, N + 1> idx;
    362 
    363 void init() {
    364     vector<int> max_p(N + 1);
    365     max_p[1] = 1;
    366     for (int i = 2; i <= N; ++i) {
    367         if (max_p[i] == 0) {
    368             ps.push_back(i);
    369             for (int j = i; j <= N; j += i) {
    370                 max_p[j] = i;
    371             }
    372         }
    373     }
    374     ps.resize(P);
    375     for (int p: ps) {
    376         int x = p;
    377         while (x * p <= N) x *= p;
    378         pks.push_back(x);
    379     }
    380     for (int i = 1; i <= N and sz(v) < sz_v; ++i) {
    381         if (max_p[i] <= ps.back()) {
    382             v.push_back(i);
    383         }
    384     }
    385     assert(sz(v) == sz_v);
    386     for (int i = 0; i < sz(v); ++i) idx[v[i]] = i;
    387 }
    388 
    389 void run1() {
    390     int n;
    391     cin >> n;
    392     vector<int> a(n);
    393     for (int i = 0; i < n; ++i) {
    394         cin >> a[i];
    395     }
    396     vector<int> b;
    397     for (int pk: pks) b.push_back(pk);
    398     vector<int> bits;
    399     for (int i = 0; i < n; ++i) {
    400         for (int j = 19; j >= 0; --j) {
    401             bits.push_back(a[i] >> j & 1);
    402         }
    403     }
    404     while (sz(bits) % 18) bits.push_back(0);
    405     for (int i = 0; i < sz(bits); i += 18) {
    406         int now = 0;
    407         for (int j = 0; j < 18; ++j) {
    408             now *= 2;
    409             now += bits[i + j];
    410         }
    411         b.push_back(v[now]);
    412     }
    413     int k = sz(b);
    414     cout << k << '\n';
    415     for (int i = 0; i < k; ++i) cout << b[i] << ' ';
    416     cout << '\n';
    417 }
    418 
    419 void run2() {
    420     int n, k;
    421     cin >> n >> k;
    422     auto ask = [&](int i, int j) {
    423         assert(i != j);
    424         cout << "? " << i + 1 << ' ' << j + 1 << endl;
    425         int g;
    426         cin >> g;
    427         return g;
    428     };
    429     vector<int> bits;
    430     for (int i = P; i < k; ++i) {
    431         int x = 1;
    432         for (int j = 0; j < P; ++j) {
    433             int g = ask(i, j);
    434             x *= g;
    435         }
    436         int now = idx[x];
    437         for (int j = 17; j >= 0; --j) {
    438             bits.push_back(now >> j & 1);
    439         }
    440     }
    441     vector<int> a(n);
    442     for (int i = 0, j = 0; i < n; ++i, j += 20) {
    443         int now = 0;
    444         for (int x = 0; x < 20; ++x) {
    445             now *= 2;
    446             now += bits[j + x];
    447         }
    448         a[i] = now;
    449     }
    450     cout << "!";
    451     for (int i = 0; i < n; ++i) cout << ' ' << a[i];
    452     cout << endl;
    453 }
    454 
    455 int main() {
    456     ios_base::sync_with_stdio(false);
    457     cin.tie(nullptr);
    458     init();
    459     cin >> type;
    460     int T = 1;
    461     cin >> T;
    462     while (T--) {
    463         if (type == "first") {
    464             run1();
    465         } else {
    466             run2();
    467         }
    468     }
    469     return 0;
    470 }
    471 ```
    472 
    473 [2237H - Slime and Queries](/contest/2237/problem/H)
    474 
    475 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") Preparation: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") & [Sugar_fan](/profile/Sugar_fan "International Grandmaster Sugar_fan")
    476 
    477 **Tutorial**
    478 
    479 Tutorial is loading...
    480 
    481 **Implementation**
    482 
    483 ```
    484 #include<bits/stdc++.h>
    485 
    486 using namespace std;
    487 vector<int> line[100000];
    488 int dfn[100000], siz[100000], fa[100000], wp[100000], tp[100000], dep[100000], cdfn;
    489 
    490 void dfs1(int t, int f) {
    491     vector<int>::iterator it;
    492     int mx = -1;
    493     fa[t] = f;
    494     siz[t] = 1;
    495     wp[t] = -1;
    496     for (it = line[t].begin(); it != line[t].end(); it++) {
    497         if ((*it) == f)continue;
    498         dep[*it] = dep[t] + 1;
    499         dfs1(*it, t);
    500         siz[t] += siz[*it];
    501         if (siz[*it] > mx) {
    502             mx = siz[*it];
    503             wp[t] = *it;
    504         }
    505     }
    506 }
    507 
    508 void dfs2(int t, int f) {
    509     vector<int>::iterator it;
    510     dfn[t] = cdfn;
    511     cdfn++;
    512     if (wp[t] == -1)return;
    513     tp[wp[t]] = tp[t];
    514     dfs2(wp[t], t);
    515     for (it = line[t].begin(); it != line[t].end(); it++) {
    516         if ((*it) == f)continue;
    517         if (*it == wp[t])continue;
    518         tp[*it] = *it;
    519         dfs2(*it, t);
    520     }
    521 }
    522 
    523 map<int, int> mp, sg;
    524 
    525 void access(int p) {
    526     map<int, int>::iterator it;
    527     int x;
    528     it = sg.upper_bound(p);
    529     it--;
    530     x = (*it).second;
    531     sg[p] = x;
    532 }
    533 
    534 int chkmap(int c, int vl) {
    535     map<int, int>::iterator it;
    536     int d;
    537     while (1) {
    538         it = mp.upper_bound(vl);
    539         if (it == mp.begin())break;
    540         it--;
    541         d = min((*it).second, c);
    542         c -= d;
    543         (*it).second -= d;
    544         if ((*it).second == 0)mp.erase(it);
    545         if (c == 0)break;
    546     }
    547     return c;
    548 }
    549 
    550 int upd(int l, int r, int p) {
    551     int ans = 0, lst, lvl;
    552     map<int, int>::iterator it;
    553     access(l);
    554     access(r);
    555     lst = l;
    556     lvl = sg[l];
    557     while (1) {
    558         it = sg.upper_bound(l);
    559         ans += chkmap((*it).first - lst, lvl);
    560         lst = (*it).first;
    561         lvl = (*it).second;
    562         if ((*it).first == r)break;
    563         sg.erase(it);
    564     }
    565     sg[l] = p;
    566     mp[p] += r - l - ans;
    567     return ans;
    568 }
    569 
    570 int main() {
    571     ios::sync_with_stdio(false), cin.tie(0);
    572     int T, n, m, q, i, u, v, p;
    573     long long ans;
    574     for (cin >> T; T > 0; T--) {
    575         cin >> n >> m >> q;
    576         for (i = 0; i < n - 1; i++) {
    577             cin >> u >> v;
    578             line[u - 1].push_back(v - 1);
    579             line[v - 1].push_back(u - 1);
    580         }
    581         dep[0] = 0;
    582         dfs1(0, -1);
    583         cdfn = 0;
    584         tp[0] = 0;
    585         dfs2(0, -1);
    586         sg[0] = -1;
    587         sg[n] = -1;
    588         for (i = 0; i < m; i++) {
    589             cin >> p;
    590             p--;
    591             access(dfn[p] + 1);
    592             sg[dfn[p]] = 0;
    593         }
    594         mp[0] = m;
    595         ans = 0;
    596         for (i = 1; i <= q; i++) {
    597             u = p;
    598             cin >> p;
    599             p--;
    600             p = (p + ans) % n;
    601             v = p;
    602             while (1) {
    603                 if (tp[u] == tp[v]) {
    604                     if (dep[v] > dep[u])swap(u, v);
    605                     ans += upd(dfn[v], dfn[u] + 1, i);
    606                     break;
    607                 }
    608                 if (dep[tp[v]] > dep[tp[u]])swap(u, v);
    609                 ans += upd(dfn[tp[u]], dfn[u] + 1, i);
    610                 u = fa[tp[u]];
    611             }
    612             cout << ans << ' ';
    613         }
    614         cout << '\n';
    615         for (i = 0; i < n; i++)line[i].clear();
    616         mp.clear();
    617         sg.clear();
    618     }
    619     return 0;
    620 }
    621 ```
    622 
    623 [2237I1 - DBFS Order (Easy Version)](/contest/2237/problem/I1)
    624 
    625 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") Preparation: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") & [Sugar_fan](/profile/Sugar_fan "International Grandmaster Sugar_fan") & [Boboge](/profile/Boboge "Grandmaster Boboge")
    626 
    627 **Tutorial**
    628 
    629 Tutorial is loading...
    630 
    631 [2237I2 - DBFS Order (Hard Version)](/contest/2237/problem/I2)
    632 
    633 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") Preparation: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk") & [Sugar_fan](/profile/Sugar_fan "International Grandmaster Sugar_fan") & [Boboge](/profile/Boboge "Grandmaster Boboge")
    634 
    635 **Tutorial**
    636 
    637 Tutorial is loading...
    638 
    639 **Implementation**
    640 
    641 ```
    642 #include<bits/stdc++.h>
    643 
    644 using namespace std;
    645 const long long mod = 1000000007;
    646 vector<int> line[3000];
    647 string s;
    648 long long dp[4][3000][3001], dpc[4][3000][3001], tdp[4][3001], tdpc[4][3001];
    649 int dep[3000], vis1[3000], vislink[3000];
    650 
    651 void merge(int u, int v, int pu, int pv, int pt) {
    652     int i, j;
    653     for (i = 0; i <= dep[u]; i++) {
    654         for (j = 0; j <= dep[v]; j++) {
    655             tdp[pt][max(i, j)] = (tdp[pt][max(i, j)] + dp[pu][u][i] * dp[pv][v][j]) % mod;
    656             if (i <= j)tdpc[pt][j] = (tdpc[pt][j] + dp[pu][u][i] * dpc[pv][v][j]) % mod;
    657             if (i > j)tdpc[pt][i] = (tdpc[pt][i] + dpc[pu][u][i] * dp[pv][v][j]) % mod;
    658         }
    659     }
    660 }
    661 
    662 void dfs(int t) {
    663     vector<int>::iterator it;
    664     int i, j, p, x, y, r0 = 0;
    665     long long vl;
    666     dp[0][t][0] = 1;
    667     dep[t] = 0;
    668     vis1[t] = 0;
    669     vislink[t] = 0;
    670     for (it = line[t].begin(); it != line[t].end(); it++) {
    671         if (s[*it] == '0')r0++;
    672     }
    673     for (it = line[t].begin(); it != line[t].end(); it++) {
    674         dfs(*it);
    675         if (s[*it] == '0')r0--;
    676         merge(t, *it, 0, 0, 0);
    677         if (s[*it] == '1') {
    678             merge(t, *it, 3, 1, 2);
    679             merge(t, *it, 3, 1, 3);
    680         } else {
    681             merge(t, *it, 2, 1, 2);
    682             merge(t, *it, 3, 1, 3);
    683         }
    684         if (vis1[t] == 0 && r0 == 0 && vislink[*it]) {
    685             if (vislink[t] == 0) {
    686                 vislink[t] = 1;
    687                 for (i = 0; i <= dep[*it]; i++) {
    688                     tdp[2][i] = (tdp[2][i] + dp[2][*it][i]) % mod;
    689                     tdpc[2][i] = (tdpc[2][i] + dpc[2][*it][i]) % mod;
    690                     tdp[3][i] = (tdp[3][i] + dp[3][*it][i]) % mod;
    691                     tdpc[3][i] = (tdpc[3][i] + dpc[3][*it][i]) % mod;
    692                 }
    693             } else {
    694                 for (i = 0; i <= dep[*it]; i++) {
    695                     tdp[2][i] = (tdp[2][i] + dp[2][*it][i]) % mod;
    696                     tdpc[2][i] = (tdpc[2][i] + dpc[2][*it][i]) % mod;
    697                     tdp[3][i] = (tdp[3][i] + dp[2][*it][i]) % mod;
    698                     tdpc[3][i] = (tdpc[3][i] + dpc[2][*it][i]) % mod;
    699                     if (s[*it] == '1') {
    700                         tdp[2][i] = (tdp[2][i] + dp[1][*it][i]) % mod;
    701                         tdpc[2][i] = (tdpc[2][i] + dpc[1][*it][i]) % mod;
    702                         tdp[3][i] = (tdp[3][i] + dp[1][*it][i]) % mod;
    703                         tdpc[3][i] = (tdpc[3][i] + dpc[1][*it][i]) % mod;
    704                     }
    705                 }
    706             }
    707         }
    708         vis1[t] |= vis1[*it];
    709         dep[t] = max(dep[t], dep[*it]);
    710         for (p = 0; p < 4; p++) {
    711             for (i = 0; i <= dep[t]; i++) {
    712                 dp[p][t][i] = tdp[p][i];
    713                 dpc[p][t][i] = tdpc[p][i];
    714                 tdp[p][i] = 0;
    715                 tdpc[p][i] = 0;
    716             }
    717         }
    718     }
    719     if (s[t] == '0') {
    720         dep[t]++;
    721         return;
    722     }
    723     for (i = 0; i <= dep[t]; i++) {
    724         tdp[0][i + 1] = (tdp[0][i + 1] + dp[0][t][i]) % mod;
    725         tdpc[0][i + 1] = (tdpc[0][i + 1] + dpc[0][t][i]) % mod;
    726     }
    727     vl = 0;
    728     for (i = 0; i <= dep[t]; i++) {
    729         vl = (vl + dp[2][t][i]) % mod;
    730         vl = (vl + mod - dpc[2][t][i]) % mod;
    731     }
    732     tdpc[0][1] = (tdpc[0][1] + vl) % mod;
    733     dep[t]++;
    734     vislink[t] = 1;
    735     if (s[t] == '1') {
    736         vis1[t] = 1;
    737         for (i = 0; i <= dep[t]; i++) {
    738             dp[0][t][i] = tdp[0][i];
    739             dpc[0][t][i] = tdpc[0][i];
    740             dp[1][t][i] = tdp[0][i];
    741             dpc[1][t][i] = tdpc[0][i];
    742             dp[2][t][i] = 0;
    743             dpc[2][t][i] = 0;
    744             dp[3][t][i] = 0;
    745             dpc[3][t][i] = 0;
    746         }
    747     } else {
    748         for (i = 0; i <= dep[t]; i++) {
    749             dp[0][t][i] = (dp[0][t][i] + tdp[0][i]) % mod;
    750             dpc[0][t][i] = (dpc[0][t][i] + tdpc[0][i]) % mod;
    751             dp[1][t][i] = tdp[0][i];
    752             dpc[1][t][i] = tdpc[0][i];
    753             dp[3][t][i] = dp[2][t][i];
    754             dpc[3][t][i] = dpc[2][t][i];
    755             dp[2][t][i] = (dp[2][t][i] + tdp[0][i]) % mod;
    756             dpc[2][t][i] = (dpc[2][t][i] + tdpc[0][i]) % mod;
    757         }
    758     }
    759     for (i = 0; i <= dep[t]; i++) {
    760         tdp[0][i] = 0;
    761         tdpc[0][i] = 0;
    762     }
    763 }
    764 
    765 int main() {
    766     ios::sync_with_stdio(false), cin.tie(0);
    767     int T, n, i, j, p, c;
    768     long long ans;
    769     for (cin >> T; T > 0; T--) {
    770         cin >> n >> s;
    771         s = '1' + s;
    772         for (i = 0; i < n; i++) {
    773             cin >> c;
    774             for (j = 0; j < c; j++) {
    775                 cin >> p;
    776                 line[i].push_back(p - 1);
    777             }
    778         }
    779         for (p = 0; p < 4; p++) {
    780             for (i = 0; i < n; i++) {
    781                 for (j = 0; j <= n; j++) {
    782                     dp[p][i][j] = 0;
    783                     dpc[p][i][j] = 0;
    784                 }
    785             }
    786         }
    787         dfs(0);
    788         ans = 0;
    789         for (i = 0; i <= dep[0]; i++) {
    790             ans = (ans + dp[0][0][i]) % mod;
    791             ans = (ans + mod - dpc[0][0][i]) % mod;
    792         }
    793         cout << ans << '\n';
    794         for (i = 0; i < n; i++)line[i].clear();
    795     }
    796     return 0;
    797 }
    798 ```