codeforces-scrape

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

1836.md (24440B)


      1 Source: https://codeforces.com/blog/entry/117394
      2 
      3 [1836A - Destroyer](/contest/1836/problem/A "Codeforces Round 880 (Div. 2)")
      4 
      5 * Author: [kempusss](/profile/kempusss "Master kempusss")
      6 * Developer: [kempusss](/profile/kempusss "Master kempusss")
      7 * First solve: [Goonless](/profile/Goonless "Specialist Goonless")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution**
     14 
     15 ```
     16 #include <bits/stdc++.h>
     17 using namespace std;
     18  
     19 const int N = 1e6;
     20  
     21 int main()
     22 {
     23     int cases;
     24     scanf("%d", &cases);
     25     
     26     while (cases--) {
     27     	int n;
     28     	scanf ("%d", &n);
     29     	
     30     	vector <int> cnt(n + 1);
     31     	for (int i = 0; i < n; i++) {
     32     		int d;
     33     		scanf("%d", &d);
     34     		if (d < n) {
     35         		cnt[d]++;
     36     		} else {
     37     		    cnt[n] = N;
     38     		}
     39     	}
     40     	
     41     	bool good = true;
     42     	for (int i = 1; i <= n; i++) if (cnt[i] > cnt[i-1]) {
     43     	    good = false;
     44     	    break;
     45     	}
     46     	
     47     	puts(good ? "YES" : "NO");
     48     }
     49 }
     50 ```
     51 
     52 [1836B - Astrophysicists](/contest/1836/problem/B "Codeforces Round 880 (Div. 2)")
     53 
     54 * Author: [Fly_37](/profile/Fly_37 "Master Fly_37")
     55 * Developer: [Okrut](/profile/Okrut "Grandmaster Okrut")
     56 * First solve: [NTR_Lover](/profile/NTR_Lover "Specialist NTR_Lover")
     57 
     58 **Tutorial**
     59 
     60 Tutorial is loading...
     61 
     62 **Solution**
     63 
     64 ```
     65 #include "bits/stdc++.h"
     66 using namespace std;
     67  
     68 int main()
     69 {
     70 	int t;
     71 	scanf ("%d", &t);
     72 	while (t--) {
     73 		long long n, k, g;
     74 		scanf ("%lld %lld %lld", &n, &k, &g);
     75  
     76 		long long stolen = min((g - 1) / 2 * n, k * g);
     77 		long long rest = (k * g - stolen) % g;
     78  
     79 		if (rest > 0) {
     80 		    stolen -= (g - 1) / 2;
     81 		    long long last = ((g - 1) / 2 + rest) % g;
     82  
     83 		    if (last * 2 < g) {
     84 		        stolen += last;
     85 		    } else {
     86 		        stolen -= g - last;
     87 		    }
     88 		}
     89  
     90 		printf ("%lld\n", stolen);
     91 	}
     92 }
     93 ```
     94 
     95 [1836C - k-th equality](/contest/1836/problem/C "Codeforces Round 880 (Div. 2)") / [1835A - k-th equality](/contest/1835/problem/A "Codeforces Round 880 (Div. 1)")
     96 
     97 * Author: [Okrut](/profile/Okrut "Grandmaster Okrut")
     98 * Developer: [w0nsh](/profile/w0nsh "Grandmaster w0nsh")
     99 * First solve: [NTR_Lover](/profile/NTR_Lover "Specialist NTR_Lover") / [ksun48](/profile/ksun48 "Legendary Grandmaster ksun48")
    100 
    101 **Tutorial**
    102 
    103 Tutorial is loading...
    104 
    105 **Solution**
    106 
    107 ```
    108 #include <bits/stdc++.h>
    109 
    110 int power(int a, int e) {
    111     if (e == 0) return 1;
    112     return e == 1 ? a : a * power(a, e-1);
    113 }
    114 
    115 void answer(int a, int b) {
    116     std::cout << a << " + " << b << " = " << a+b << std::endl;
    117 }
    118 
    119 int main() {
    120     using ll = long long;
    121     
    122     int t;
    123     std::cin >> t;
    124     while (t--) {
    125 
    126         int a, b, c;
    127         ll k;
    128         std::cin >> a >> b >> c >> k;
    129         
    130         bool good = false;
    131     
    132         for (int i = power(10, a-1); i < power(10, a); ++i) {
    133             int left = std::max(power(10, b-1), power(10, c-1) - i);
    134             int right = std::min(power(10, b)-1, power(10, c) - 1 - i);
    135             if (left > right) continue;
    136     
    137             int have = right - left + 1;
    138             if (k <= have) {
    139                 answer(i, left + k - 1);
    140                 good = true;
    141                 break;
    142             }
    143     
    144             k -= have;
    145         }
    146     
    147         if (!good) std::cout << "-1" << std::endl;
    148     }
    149 
    150     return 0;
    151 }
    152 ```
    153 
    154 [1836D - Lottery](/contest/1836/problem/D "Codeforces Round 880 (Div. 2)") / [1835B - Lottery](/contest/1835/problem/B "Codeforces Round 880 (Div. 1)")
    155 
    156 * Author: [Arti1990](/profile/Arti1990 "Candidate Master Arti1990")
    157 * Developer: [Arti1990](/profile/Arti1990 "Candidate Master Arti1990")
    158 * First solve: [Nobody.Emissary](/profile/Nobody.Emissary "Newbie Nobody.Emissary") / [ecnerwala](/profile/ecnerwala "Legendary Grandmaster ecnerwala")
    159 
    160 **Tutorial**
    161 
    162 Tutorial is loading...
    163 
    164 **Solution**
    165 
    166 ```
    167 #include <bits/stdc++.h>
    168  
    169 #define forr(i, n) for (int i = 0; i < n; i++)
    170 #define FOREACH(iter, coll) for (auto iter = coll.begin(); iter != coll.end(); ++iter)
    171 #define FOREACHR(iter, coll) for (auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
    172 #define lbound(P, K, FUN) ({auto SSS=P, PPP = P-1, KKK=(K)+1; while(PPP+1!=KKK) {SSS = (PPP+(KKK-PPP)/2); if(FUN(SSS)) KKK = SSS; else PPP = SSS;} PPP; })
    173 #define testy()    \
    174     int _tests;    \
    175     cin >> _tests; \
    176     FOR(_test, 1, _tests)
    177 #define CLEAR(tab) memset(tab, 0, sizeof(tab))
    178 #define CONTAIN(el, coll) (coll.find(el) != coll.end())
    179 #define FOR(i, a, b) for (int i = a; i <= b; i++)
    180 #define FORD(i, a, b) for (int i = a; i >= b; i--)
    181 #define MP make_pair
    182 #define PB push_back
    183 #define ff first
    184 #define ss second
    185 #define deb(X) X;
    186 #define SIZE(coll) ((int)coll.size())
    187  
    188 #define M 1000000007
    189 #define INF 1000000007LL
    190  
    191 using namespace std;
    192  
    193 long long n, m, k;
    194 long long poz_l, poz_p;
    195 vector<long long> v;
    196  
    197 long long policz_ile(long long strzal)
    198 {
    199     while (poz_l < n && v[poz_l] < strzal)
    200         poz_l++;
    201     while (poz_p < n && v[poz_p] <= strzal)
    202         poz_p++;
    203  
    204     long long pocz = poz_p < k ? 0 : (strzal + v[poz_p - k]) / 2 + 1;
    205     long long kon = poz_l + k - 1 >= n ? m : (v[poz_l + k - 1] + strzal - 1) / 2;
    206  
    207     return max(0ll, kon - pocz + 1);
    208 }
    209  
    210 int solve()
    211 {
    212     cin >> n >> m >> k;
    213     long long a;
    214     forr(i, n)
    215     {
    216         cin >> a;
    217         v.PB(a);
    218     }
    219     sort(v.begin(), v.end());
    220     v.PB(m + 1);
    221     long long res = policz_ile(0), best = 0;
    222     forr(i, n)
    223     {
    224         long long pocz = i == 0 ? max(0ll, v[i] - 2) : max(v[i] - 2, v[i - 1] + 3);
    225         long long kon = min(m, v[i] + 2);
    226         for (long long s = pocz; s <= kon; s++)
    227         {
    228             long long ile = policz_ile(s);
    229  
    230             if (ile > res)
    231             {
    232                 res = ile;
    233                 best = s;
    234             }
    235         }
    236     }
    237     cout << res << " " << best << '\n';
    238  
    239     return 0;
    240 }
    241  
    242 int main()
    243 {
    244     std::ios_base::sync_with_stdio(0);
    245     cin.tie(0);
    246     cout.tie(0);
    247  
    248     solve();
    249  
    250     return 0;
    251 }
    252 ```
    253 
    254 [1836E - Twin Clusters](/contest/1836/problem/E "Codeforces Round 880 (Div. 2)") / [1835C - Twin Clusters](/contest/1835/problem/C "Codeforces Round 880 (Div. 1)")
    255 
    256 * Author: [Anadi](/profile/Anadi "International Grandmaster Anadi"), [w0nsh](/profile/w0nsh "Grandmaster w0nsh")
    257 * Developer: [Fly_37](/profile/Fly_37 "Master Fly_37")
    258 * First solve: [GULAL_S_ZHENOY_UMNIKA](/profile/GULAL_S_ZHENOY_UMNIKA "Specialist GULAL_S_ZHENOY_UMNIKA") / [Um_nik](/profile/Um_nik "Legendary Grandmaster Um_nik")
    259 
    260 **Tutorial**
    261 
    262 Tutorial is loading...
    263 
    264 **Solution**
    265 
    266 ```
    267 #include <bits/stdc++.h>
    268 
    269 using namespace std;
    270 
    271 void solve()
    272 {
    273     int k, n;
    274     scanf("%d", &k);
    275 
    276     n = 2 << k;
    277 
    278     vector <long long> input(n + 1);
    279     vector <int> memHighBits(1 << k, -1);
    280     vector <pair <int, int> > memLowBits(1 << k, {-1, -1});
    281     
    282     auto addInterval = [&memLowBits, &input](int s, int e) {
    283         const int remXor = input[e] ^ input[s - 1];
    284         auto &[os, oe] = memLowBits[remXor];
    285 
    286         if (os == -1) {
    287             os = s, oe = e;
    288             return false;
    289         }
    290 
    291         if (oe < s) {
    292             printf("%d %d %d %d\n", os, oe, s, e);
    293         } else {
    294             printf("%d %d %d %d\n", min(s, os), max(s, os) - 1, oe + 1, e);
    295         }
    296 
    297         return true;
    298     };
    299 
    300     memHighBits[0] = 0;
    301     for (int i = 1; i <= n; ++i) {
    302         scanf("%lld", &input[i]);
    303         input[i] ^= input[i - 1];
    304     }
    305 
    306     for (int i = 1; i <= n; ++i) {
    307         if (memHighBits[input[i] >> k] != -1) {
    308             if (addInterval(memHighBits[input[i] >> k] + 1, i)) {
    309                 break;
    310             }
    311         }
    312 
    313         memHighBits[input[i] >> k] = i;
    314     }
    315 }
    316 
    317 int main()
    318 {
    319     int cases;
    320     scanf("%d", &cases);
    321 
    322     while (cases--) {
    323         solve();
    324     }
    325 
    326     return 0;
    327 }
    328 ```
    329 
    330 [1836F - Doctor's Brown Hypothesis](/contest/1836/problem/F "Codeforces Round 880 (Div. 2)") / [1835D - Doctor's Brown Hypothesis](/contest/1835/problem/D "Codeforces Round 880 (Div. 1)")
    331 
    332 * Author: [Okrut](/profile/Okrut "Grandmaster Okrut")
    333 * Developer: [Okrut](/profile/Okrut "Grandmaster Okrut")
    334 * First solve: None / [ksun48](/profile/ksun48 "Legendary Grandmaster ksun48")
    335 
    336 **Tutorial**
    337 
    338 Tutorial is loading...
    339 
    340 **Solution**
    341 
    342 ```
    343 #include<bits/stdc++.h>
    344 using namespace std;
    345  
    346 #define sz(s) (int)s.size()
    347 #define all(s) s.begin(), s.end()
    348 #define pb push_back
    349 #define FOR(i, n) for(int i = 0; i < n; i++)
    350  
    351 using vi = vector<int>;
    352 using vvi = vector<vi>;
    353  
    354 struct SCC {
    355     int cnt = 0;
    356     vi vis, scc_nr;
    357     vvi scc_list, DAG;
    358  
    359     SCC(){}
    360  
    361     SCC(vvi & G){
    362         // G is 0 indexed!
    363         int n = sz(G);
    364         vvi G_rev(n);
    365         vis = scc_nr = vi(n);
    366  
    367         vi postorder;
    368         for(int i = 0; i < n; i++)
    369             if(!vis[i])
    370                 dfs_post(i, G, G_rev, postorder);
    371         
    372         vis = vi(n);
    373         while(sz(postorder)){
    374             auto akt = postorder.back();
    375             postorder.pop_back();
    376             if(!vis[akt]){
    377                 DAG.emplace_back();
    378                 scc_list.emplace_back();
    379                 dfs_rev(akt, G_rev);
    380                 cnt++;
    381             }
    382         }
    383  
    384         // optional
    385         for(int i = 0; i < sz(DAG); i++){
    386             sort(all(DAG[i]));
    387             DAG[i].resize(unique(all(DAG[i])) - DAG[i].begin());
    388         }
    389     }
    390  
    391     void dfs_post(int start, vvi & G, vvi & G_rev, vi & postorder){
    392         vis[start] = 1;
    393         for(auto & u : G[start]){
    394             G_rev[u].pb(start);
    395             if(!vis[u])
    396                 dfs_post(u, G, G_rev, postorder);
    397         }
    398         
    399         postorder.pb(start);
    400     }
    401  
    402     void dfs_rev(int start, vvi & G_rev){
    403         vis[start] = true;
    404         scc_list.back().pb(start);
    405         scc_nr[start] = cnt;
    406  
    407         for(auto & u : G_rev[start])
    408             if(!vis[u])
    409                 dfs_rev(u, G_rev);
    410             else if(scc_nr[u] != cnt)
    411                 DAG[scc_nr[u]].pb(cnt);
    412     }
    413 };
    414  
    415 int main()
    416 {
    417     ios::sync_with_stdio(0);
    418     cin.tie(0);
    419  
    420     long long n, m, k;
    421     cin >> n >> m >> k;
    422  
    423     vvi G(n);
    424  
    425     set<pair<int, int>> edges;
    426     for (int i = 0; i < m; i++)
    427     {
    428         int a, b;
    429         cin >> a >> b;
    430         a--, b--;
    431         G[a].pb(b);
    432         edges.insert({a, b});
    433     }
    434  
    435     SCC scc(G);
    436     vi coloring(n, -1);
    437  
    438     auto try_coloring = [&](int num_col, const vi& group)
    439     {
    440         vi visited;
    441         function<bool(int)> dfs = [&](int start){
    442             visited.pb(start);
    443             
    444             bool good_coloring = true;
    445             for (auto & u : G[start])
    446             {
    447                 if (scc.scc_nr[u] != scc.scc_nr[start])
    448                 {
    449                     continue;
    450                 }
    451                 if (coloring[u] == -1)
    452                 {
    453                     coloring[u] = (coloring[start] + 1) % num_col;
    454                     good_coloring &= dfs(u);
    455                 }
    456                 else
    457                 {
    458                     good_coloring &= coloring[u] == (coloring[start] + 1) % num_col;
    459                 }
    460  
    461                 if (not good_coloring)
    462                 {
    463                     break;    
    464                 }
    465             }
    466  
    467             return good_coloring;
    468         };
    469  
    470         coloring[group[0]] = 0;
    471         if (not dfs(group[0]))
    472         {
    473             for (auto & u : visited)
    474             {
    475                 coloring[u] = -1;
    476             }
    477             return vvi();
    478         }
    479         else
    480         {
    481             vvi ret(num_col);
    482             for (auto & u : visited)
    483             {
    484                 ret[coloring[u]].push_back(u);
    485             }
    486             return ret;
    487         }
    488     };
    489  
    490     long long ans = 0;
    491     vi depths(n, -1);
    492  
    493     for (vi& group : scc.scc_list)
    494     {
    495         n = sz(group);
    496  
    497         if (n == 1 and edges.count({group[0], group[0]}) == 0)
    498         {
    499             continue;
    500         }
    501         int gcd = -1;
    502         function<void(int)> dfs_depths = [&](int start)
    503         {
    504             for (auto & u : G[start])
    505             {
    506                 if (scc.scc_nr[u] != scc.scc_nr[start])
    507                 {
    508                     continue;
    509                 }
    510  
    511                 if (depths[u] == -1)
    512                 {
    513                     depths[u] = depths[start] + 1;
    514                     dfs_depths(u);
    515                 }
    516                 else {
    517                     int diff = abs(depths[u] - (depths[start] + 1));
    518                     if (diff)
    519                     {
    520                         if (gcd == -1)
    521                         {
    522                             gcd = diff;
    523                         }
    524                         else
    525                         {
    526                             gcd = __gcd(gcd, diff);
    527                         }
    528                     }
    529                 }
    530             }
    531         };
    532  
    533         depths[group[0]] = 0;
    534         dfs_depths(group[0]);
    535         assert(gcd != -1);
    536  
    537         vvi by_color = try_coloring(gcd, group);
    538  
    539         assert(sz(by_color) != 0);
    540         if (k % gcd == 0)
    541         {
    542             FOR (i, gcd)
    543             {
    544                 ans += sz(by_color[i]) + 1ll * sz(by_color[i]) * (sz(by_color[i]) - 1) / 2;
    545             }
    546         }
    547         else if (k % gcd * 2 == gcd)
    548         {
    549             FOR (i, gcd / 2)
    550             {
    551                 ans += 1ll * sz(by_color[i]) * sz(by_color[i + gcd / 2]);
    552             }
    553         }
    554     }
    555     cout << ans << '\n';
    556 }
    557 ```
    558 
    559 [1835E - Old Mobile](/contest/1835/problem/E "Codeforces Round 880 (Div. 1)")
    560 
    561 * Author: [Fly_37](/profile/Fly_37 "Master Fly_37")
    562 * Developer: [maras](/profile/maras "Master maras")
    563 * First solve: [tourist](/profile/tourist "Legendary Grandmaster tourist")
    564 
    565 **Tutorial**
    566 
    567 Tutorial is loading...
    568 
    569 **Solution**
    570 
    571 ```
    572 #include <bits/stdc++.h>
    573  
    574 using namespace std;
    575  
    576 constexpr int MAX_M = 1000 + 7;
    577 constexpr int PRECISION = 9;
    578 constexpr long long MOD = 1e9 + 7;
    579  
    580 long long mod_inv[MAX_M];
    581 long long DP[MAX_M][MAX_M][2][2];
    582 long long DPprob[MAX_M][MAX_M][2][2];
    583 bool updated[MAX_M][MAX_M][2][2];
    584 // DP[correct][incorrect][backspace][bad suffix]
    585  
    586 long long calc_mod_inv(long long n)
    587 {
    588     long long res = 1;
    589     long long exp = MOD - 2;
    590  
    591     while (exp)
    592     {
    593         if (exp & 1)
    594         {
    595             res = (res * n) % MOD;
    596         }
    597  
    598         exp >>= 1;
    599         n = (n * n) % MOD;
    600     }
    601  
    602     return res;
    603 }
    604  
    605 void calc_DP(int digits, int needed)
    606 {
    607     DP[0][0][0][0] = 0;
    608     DPprob[0][0][0][0] = 1;
    609  
    610     struct ID
    611     {
    612         int x, y, z, s;
    613     };
    614  
    615     queue <ID> dp_queue;
    616     dp_queue.push({0, 0, 0, 0});
    617  
    618     while(!dp_queue.empty())
    619     {
    620         auto [x, y, z, s] = dp_queue.front();
    621         dp_queue.pop();
    622  
    623         if (updated[x][y][z][s])
    624         {
    625             continue;
    626         }
    627  
    628         updated[x][y][z][s] = true;
    629  
    630         long long left = digits + 1 - x - y - z;
    631         long long corr = needed - x;
    632         long long incorr = digits - needed - y;
    633         long long prob = DPprob[x][y][z][s];
    634  
    635         if (corr == 0 and s == 0)
    636         {
    637             // done
    638             continue;
    639         }
    640  
    641         // correct suffix
    642         if (s == 0)
    643         {
    644             if (corr > 0)
    645             {
    646                 // found the one correct digit (no need to delete)
    647                 long long opt_prob = (prob * mod_inv[left]) % MOD;
    648                 DPprob[x + 1][y][z][0] = (DPprob[x + 1][y][z][0] + opt_prob) % MOD;
    649                 DP[x + 1][y][z][0] = (DP[x + 1][y][z][0] + DP[x][y][z][0] * mod_inv[left]) % MOD;
    650  
    651                 // found a needed but currently wrong digit (needs to be deleted)
    652                 if (corr > 1)
    653                 {
    654                     if (z == 0) // if backspace is not known, the suffix is bad
    655                     {
    656                         long long opt_prob = ((prob * (corr - 1) % MOD) * mod_inv[left]) % MOD;
    657                         DPprob[x + 1][y][z][1] = (DPprob[x + 1][y][z][1] + opt_prob) % MOD;
    658  
    659                         DP[x + 1][y][z][1] = (DP[x + 1][y][z][1] + ((corr - 1) * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
    660                         dp_queue.push({x + 1, y, z, 1});
    661                     }
    662                     else // if backspace is known, the suffix can be instantly repaired
    663                     {
    664                         long long opt_prob = ((prob * (corr - 1) % MOD) * mod_inv[left]) % MOD;
    665                         DPprob[x + 1][y][z][0] = (DPprob[x + 1][y][z][0] + opt_prob) % MOD;
    666                         DP[x + 1][y][z][0] = (DP[x + 1][y][z][0] + ((corr - 1) * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
    667                     }
    668                 }
    669  
    670                 dp_queue.push({x + 1, y, z, 0});
    671             }
    672  
    673             if (incorr > 0)
    674             {
    675                 // found an incorrect digit
    676                 if (z == 0)
    677                 {
    678                     long long opt_prob = (prob * incorr % MOD) * mod_inv[left] % MOD;
    679                     DPprob[x][y + 1][z][1] = (DPprob[x][y + 1][z][1] + opt_prob) % MOD;
    680                     DP[x][y + 1][z][1] = (DP[x][y + 1][z][1] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
    681                     dp_queue.push({x, y + 1, z, 1});
    682                 }
    683                 else // suffix can be repaired
    684                 {
    685                     long long opt_prob = ((prob * incorr % MOD) * mod_inv[left]) % MOD;
    686                     DPprob[x][y + 1][z][0] = (DPprob[x][y + 1][z][0] + opt_prob) % MOD;
    687                     DP[x][y + 1][z][0] = (DP[x][y + 1][z][0] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD;
    688                     dp_queue.push({x, y + 1, z, 0});
    689                 }
    690             }
    691  
    692             if (z == 0)
    693             {
    694                 if (x > 0) // deleted correct digit
    695                 {
    696                     long long opt_prob = prob * mod_inv[left] % MOD;
    697                     DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
    698                     DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][0] + 2 * opt_prob) % MOD;
    699                 }
    700                 else // deleted nothing
    701                 {
    702                     long long opt_prob = prob * mod_inv[left] % MOD;
    703                     DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
    704                     DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][0] + opt_prob) % MOD;
    705                 }
    706  
    707                 dp_queue.push({x, y, 1, 0});
    708             }
    709         }
    710  
    711         if (s == 1)
    712         {
    713             if (corr > 0)
    714             {
    715                 // found a needed but currently wrong digit (needs to be deleted)
    716                 long long opt_prob = (prob * corr % MOD) * mod_inv[left] % MOD;
    717                 DPprob[x + 1][y][z][1] = (DPprob[x + 1][y][z][1] + opt_prob) % MOD;
    718                 DP[x + 1][y][z][1] = (DP[x + 1][y][z][1] + (corr * mod_inv[left] % MOD) * DP[x][y][z][1] + 2 * opt_prob) % MOD;
    719                 dp_queue.push({x + 1, y, z, 1});
    720             }
    721  
    722             if (incorr > 0)
    723             {
    724                 // found an incorrect digit
    725                 long long opt_prob = (prob * incorr % MOD) * mod_inv[left] % MOD;
    726                 DPprob[x][y + 1][z][1] = (DPprob[x][y + 1][z][1] + opt_prob) % MOD;
    727                 DP[x][y + 1][z][1] = (DP[x][y + 1][z][1] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][1] + 2 * opt_prob) % MOD;
    728                 dp_queue.push({x, y + 1, z, 1});
    729             }
    730  
    731             if (z == 0)
    732             {
    733                 // deleted bad suffix
    734                 long long opt_prob = prob * mod_inv[left] % MOD;
    735                 DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD;
    736                 DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][1]) % MOD;
    737                 dp_queue.push({x, y, 1, 0});
    738             }
    739         }
    740     }
    741 }
    742  
    743 int main()
    744 {
    745     ios::sync_with_stdio(0);
    746     cin.tie(0);
    747     cout.tie(0);
    748  
    749     mod_inv[0] = 1;
    750     for (int i = 1; i < MAX_M; ++i) {
    751         mod_inv[i] = calc_mod_inv(i);
    752         assert (mod_inv[i] * i % MOD == 1);
    753     }
    754  
    755     int n, m;
    756     cin >> n >> m;
    757  
    758     set <int> different_digits;
    759  
    760     for (int i = 0; i < n; ++i)
    761     {
    762         int p;
    763         cin >> p;
    764  
    765         different_digits.insert(p);
    766     }
    767  
    768     int needed = different_digits.size();
    769  
    770     calc_DP(m, needed);
    771  
    772     long long result = 0;
    773  
    774     for (int i = 0; i <= MAX_M; ++i)
    775     {
    776         result = (result + DP[needed][i][0][0]) % MOD;
    777         result = (result + DP[needed][i][1][0]) % MOD;
    778     }
    779  
    780     cout << (result + n) % MOD << "\n";
    781  
    782     return 0;
    783 }
    784 ```
    785 
    786 [1835F - Good Graph](/contest/1835/problem/F "Codeforces Round 880 (Div. 1)")
    787 
    788 * Author: [Anadi](/profile/Anadi "International Grandmaster Anadi")
    789 * Developer: [Arti1990](/profile/Arti1990 "Candidate Master Arti1990")
    790 * First solve: [rainboy](/profile/rainboy "Candidate Master rainboy")
    791 
    792 **Tutorial**
    793 
    794 Tutorial is loading...
    795 
    796 **Solution**
    797 
    798 ```
    799 #include <bits/stdc++.h>
    800 
    801 #define forr(i, n) for (int i = 0; i < n; i++)
    802 #define FOREACH(iter, coll) for (auto iter = coll.begin(); iter != coll.end(); ++iter)
    803 #define FOREACHR(iter, coll) for (auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
    804 #define lbound(P, K, FUN) ({auto SSS=P, PPP = P-1, KKK=(K)+1; while(PPP+1!=KKK) {SSS = (PPP+(KKK-PPP)/2); if(FUN(SSS)) KKK = SSS; else PPP = SSS;} PPP; })
    805 #define testy()    \
    806     int _tests;    \
    807     cin >> _tests; \
    808     FOR(_test, 1, _tests)
    809 #define CLEAR(tab) memset(tab, 0, sizeof(tab))
    810 #define CONTAIN(el, coll) (coll.find(el) != coll.end())
    811 #define FOR(i, a, b) for (int i = a; i <= b; i++)
    812 #define FORD(i, a, b) for (int i = a; i >= b; i--)
    813 #define MP make_pair
    814 #define PB push_back
    815 #define ff first
    816 #define ss second
    817 #define deb(X) X;
    818 #define SIZE(coll) ((int)coll.size())
    819 
    820 using namespace std;
    821 
    822 const int MXN = 1007;
    823 int n, m;
    824 vector<int> G[MXN];
    825 bitset<MXN> bs[MXN], edge[MXN];
    826 
    827 // MATCHING
    828 
    829 const int MXM = 1007 * 2;
    830 int skojX[MXM], skojY[MXM];
    831 bool vis[MXM];
    832 
    833 bool dfs_m(int x)
    834 {
    835     vis[x] = 1;
    836     FOREACH(it, G[x])
    837     if (!skojY[*it] || (!vis[skojY[*it]] && dfs_m(skojY[*it])))
    838     {
    839         skojX[x] = *it;
    840         skojY[*it] = x;
    841         return 1;
    842     }
    843     return 0;
    844 }
    845 
    846 bool skoj()
    847 {
    848     int czy = 1;
    849     int res = 0;
    850     while (czy)
    851     {
    852         czy = 0;
    853         CLEAR(vis);
    854         FOR(i, 1, n)
    855         if (!vis[i] && !skojX[i] && dfs_m(i))
    856         {
    857             czy = 1;
    858             res++;
    859         }
    860     }
    861     return res == n;
    862 }
    863 
    864 // END OF MATCHING
    865 
    866 void dfs(int nr, bitset<MXN> &visited, bitset<MXN> &to_visit)
    867 {
    868     visited[nr] = 1;
    869     to_visit[nr] = 0;
    870     to_visit = to_visit | (edge[nr] & (~visited));
    871     for (int i = to_visit._Find_first(); i < SIZE(to_visit); i = to_visit._Find_next(i))
    872         dfs(i, visited, to_visit);
    873 }
    874 
    875 int solve()
    876 {
    877     cin >> n >> m;
    878     forr(i, m)
    879     {
    880         int a, b;
    881         cin >> a >> b;
    882         G[a].PB(b);
    883     }
    884 
    885     int rres = skoj();
    886     if (rres)
    887     {
    888         FOR(i, 1, n)
    889         {
    890             for (auto j : G[i])
    891             {
    892                 edge[i][skojY[j]] = 1;
    893             }
    894         }
    895         unordered_map<bitset<MXN>, vector<int>> mapa;
    896         vector<pair<int, int>> vec, res;
    897         FOR(i, 1, n)
    898         {
    899             bitset<MXN> to_visit;
    900             dfs(i, bs[i], to_visit);
    901             mapa[bs[i]].PB(i);
    902         }
    903 
    904         for (auto p : mapa)
    905         {
    906             vector<int> l = p.ss;
    907             vec.PB({bs[l[0]].count(), l[0]});
    908             if (l.size() == 1)
    909             {
    910                 res.PB({l[0], l[0]});
    911                 continue;
    912             }
    913             for (int i = 0; i < SIZE(l); i++)
    914             {
    915                 res.PB({l[i], l[i]});
    916                 res.PB({l[i], l[(i + 1) % SIZE(l)]});
    917             }
    918         }
    919         sort(vec.begin(), vec.end());
    920         forr(i, SIZE(vec))
    921         {
    922             int nr = vec[i].ss;
    923             bitset<MXN> b;
    924             for (int j = i - 1; j >= 0; j--)
    925                 if (vec[j].ff < vec[i].ff)
    926                 {
    927                     int nr2 = vec[j].ss;
    928                     if (bs[nr][nr2] && !b[nr2])
    929                     {
    930                         b |= bs[nr2];
    931                         res.PB({nr, nr2});
    932                     }
    933                 }
    934         }
    935 
    936         cout << "YES" << '\n';
    937         cout << res.size() << '\n';
    938         for (auto p : res)
    939             cout << p.ff << " " << p.ss + n << '\n';
    940     }
    941     else
    942     {
    943         CLEAR(vis);
    944         FOR(i, 1, n)
    945         {
    946             if (skojX[i] == 0)
    947             {
    948                 dfs_m(i);
    949                 break;
    950             }
    951         }
    952         vector<int> v;
    953         FOR(i, 1, n)
    954         {
    955             if (vis[i])
    956                 v.PB(i);
    957         }
    958         cout << "NO" << '\n';
    959         cout << v.size() << '\n';
    960         for (auto el : v)
    961             cout << el << " ";
    962         cout << '\n';
    963     }
    964 
    965     return 0;
    966 }
    967 
    968 int main()
    969 {
    970     std::ios_base::sync_with_stdio(0);
    971     cin.tie(0);
    972     cout.tie(0);
    973 
    974     solve();
    975 
    976     return 0;
    977 }
    978 ```