codeforces-scrape

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

1604.md (12153B)


      1 Source: https://codeforces.com/blog/entry/96460
      2 
      3 Thanks for participating in my contest [![blobheart](/predownloaded/d7/cc/d7cc8b5ea81178880175de5a048032c05631f9b7.png)](https://emoji.gg/emoji/8771_blobheart). I hope you liked the problems. I would love to hear your feedback in the comments.
      4 
      5 If you find anything wrong in the editorial which is more likely to happen because I have written a rather long editorial to make you understand the solutions better, then comment below.
      6 
      7 Also, don't forget to upvote to pay for the editorial. See you in my next contest!
      8 
      9 Tutorial is loading...
     10 
     11 **Code**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 using namespace std;
     16  
     17 int main() {
     18   int t; cin >> t;
     19   while (t--) {
     20     int n; cin >> n;
     21     int ans = 0;
     22     for (int i = 1; i <= n; i++) {
     23       int k; cin >> k;
     24       ans = max(ans, k - i);
     25     }
     26     cout << ans << '\n';
     27   }
     28   return 0;
     29 }
     30 ```
     31 
     32 Tutorial is loading...
     33 
     34 **Code**
     35 
     36 ```
     37 #include<bits/stdc++.h>
     38 using namespace std;
     39  
     40 int main() {
     41   ios_base::sync_with_stdio(0);
     42   cin.tie(0);
     43   int t; cin >> t;
     44   while (t--) {
     45     int n; cin >> n;
     46     vector<int> a(n + 1);
     47     bool inc = true;
     48     for (int i = 1; i <= n; i++) {
     49       cin >> a[i];
     50       inc &= a[i] > a[i - 1];
     51     }
     52     if (n % 2 == 0 or !inc) {
     53       cout << "YES\n";
     54     }
     55     else {
     56       cout << "NO\n";
     57     }
     58   }
     59   return 0;
     60 }
     61 ```
     62 
     63 Tutorial is loading...
     64 
     65 **Code**
     66 
     67 ```
     68 #include<bits/stdc++.h>
     69 using namespace std;
     70  
     71 int main() {
     72   ios_base::sync_with_stdio(0);
     73   cin.tie(0);
     74   int t; cin >> t;
     75   while (t--) {
     76     int n; cin >> n;
     77     bool ok = true;
     78     for (int i = 1; i <= n; i++) {
     79       int x; cin >> x;
     80       bool found = false;
     81       for (int j = i + 1; j >= 2; j--) { // this loop will run not more than 22 times, in practice its much lower than that
     82         if (x % j) {
     83           found = true;
     84           break;
     85         }
     86       }
     87       ok &= found;
     88     }
     89     if (ok) {
     90       cout << "YES\n";
     91     }
     92     else {
     93       cout << "NO\n";
     94     }
     95   }
     96   return 0;
     97 }
     98 ```
     99 
    100 Tutorial is loading...
    101 
    102 **Code**
    103 
    104 ```
    105 #include<bits/stdc++.h>
    106 using namespace std;
    107  
    108 int main() {
    109   ios_base::sync_with_stdio(0);
    110   cin.tie(0);
    111   int t; cin >> t;
    112   while (t--) {
    113     int x, y; cin >> x >> y;
    114     if (x <= y) {
    115       cout << y - y % x / 2 << '\n';
    116     }
    117     else {
    118       cout << x + y << '\n';
    119     }
    120   }
    121   return 0;
    122 }
    123 ```
    124 
    125 Tutorial is loading...
    126 
    127 **Code**
    128 
    129 ```
    130 #include<bits/stdc++.h>
    131 using namespace std;
    132  
    133 const int N = 1e5 + 9, mod = 998244353;
    134 vector<int> v[2];
    135 int dp[2][N];
    136 int a[N];
    137 int32_t main() {
    138   ios_base::sync_with_stdio(0);
    139   cin.tie(0);
    140   int t; cin >> t;
    141   while (t--) {
    142     int n; cin >> n;
    143     for (int i = 1; i <= n; i++) {
    144       cin >> a[i];
    145     }
    146     long long ans = 0;
    147     for (int i = n; i >= 1; i--) {
    148       int k = i & 1;
    149       v[k].push_back(a[i]);
    150       dp[k][a[i]] = 1;
    151       int last = a[i];
    152       for (auto x: v[k ^ 1]) {
    153         int y = dp[k ^ 1][x];
    154         int split = (a[i] + x - 1) / x;
    155         int st = a[i] / split;
    156         ans += 1LL * (split - 1) * y * i;
    157         dp[k][st] += y;
    158         if (last != st) {
    159           v[k].push_back(st), last = st;
    160         }
    161       }
    162       for (auto x: v[k ^ 1]) dp[k ^ 1][x] = 0;
    163       v[k ^ 1].clear();
    164       ans %= mod;
    165     }
    166     cout << ans << '\n';
    167     for (auto x: v[0]) dp[0][x] = 0;
    168     for (auto x: v[1]) dp[1][x] = 0;
    169     v[0].clear(); v[1].clear();
    170   }
    171   return 0;
    172 }
    173 ```
    174 
    175 Tutorial is loading...
    176 
    177 **Code (1D1D DP)**
    178 
    179 ```
    180 #include<bits/stdc++.h>
    181 using namespace std;
    182  
    183 const int N = 1e5 + 9;
    184 const long long inf = 1e12;
    185 using ll = long long;
    186 int phi[N];
    187 void totient() {
    188   for (int i = 1; i < N; i++) phi[i] = i;
    189   for (int i = 2; i < N; i++) {
    190     if (phi[i] == i) {
    191       for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
    192     }
    193   }
    194 }
    195 ll a[N], s1[N][320], s2[N][320];
    196 int root[N];
    197 ll c(int l, int r) {
    198   if (l > r) return inf;
    199   ll ans = 0;
    200   if (r / l <= root[r]) {
    201     return s1[r][r / l] - a[r / l] * (l - 1 - r / ((r / l) + 1));
    202   }
    203   else {
    204     return s2[r][l];
    205   }
    206   return ans;
    207 }
    208 ll dp[N][17];
    209 int32_t main() {
    210   ios_base::sync_with_stdio(0);
    211   cin.tie(0);
    212   totient();
    213   for (int i = 1; i < N; i++) {
    214     a[i] = a[i - 1] + phi[i];
    215   }
    216   for (int i = 1; i < N; i++) {
    217     root[i] = 0;
    218     for (int j = 1; j * j <= i; j++) {
    219       s1[i][j] = s1[i][j - 1] + a[j] * (i / j - i / (j + 1));
    220       root[i] = j;
    221     }
    222     s2[i][i / (root[i] + 1) + 1] = s1[i][root[i]];
    223     for (int j = i / (root[i] + 1); j >= 1; j--) {
    224       s2[i][j] = s2[i][j + 1] + a[i / j];
    225     }
    226   }
    227   int n = 100000;
    228   dp[0][0] = 0;
    229   for (int i = 1; i <= n; i++) {
    230     dp[i][0] = inf;
    231   }
    232   for (int k = 1; (1 << k) <= n; k++) {
    233     dp[0][k] = 0;
    234     vector<pair<int, int> > v; // (start pos, best j)
    235     v.push_back(make_pair(0, 0));
    236     for (int x = 1; x <= n; x++) {
    237       int j = (--lower_bound(v.begin(), v.end(), make_pair(x + 1, 0)))->second;
    238       dp[x][k] = dp[j][k - 1] + c(j + 1, x);
    239       for (int i = (int)v.size() - 1; i >= 0; i--) {
    240         int y = v[i].first, oldj = v[i].second;
    241         if (y > x && dp[x][k - 1] + c(x + 1, y) < dp[oldj][k - 1] + c(oldj + 1, y)) v.pop_back();
    242         else {
    243           int l = y + 1, r = n + 1;
    244           while (l < r) {
    245             int mid = (l + r) / 2;
    246             if (dp[x][k - 1] + c(x + 1, mid) < dp[oldj][k - 1] + c(oldj + 1, mid)) r = mid;
    247             else l = mid + 1;
    248           }
    249           if (r != n + 1) v.push_back(make_pair(r, x));
    250           break;
    251         }
    252       }
    253       if (v.size() == 0) v.push_back(make_pair(0, x));
    254     }
    255   }
    256   int q; cin >> q;
    257   while (q--) {
    258     int n, k; cin >> n >> k;
    259     if (k >= 20 or (1 << k) > n) {
    260       cout << n << '\n';
    261     }
    262     else {
    263       cout << dp[n][k] << '\n';
    264     }
    265   }
    266   return 0;
    267 }
    268 ```
    269 
    270 **Code (D&C DP)**
    271 
    272 ```
    273 #include<bits/stdc++.h>
    274 using namespace std;
    275  
    276 const int N = 1e5 + 9;
    277 const long long inf = 1e12;
    278 using ll = long long;
    279 int phi[N];
    280 void totient() {
    281   for (int i = 1; i < N; i++) phi[i] = i;
    282   for (int i = 2; i < N; i++) {
    283     if (phi[i] == i) {
    284       for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
    285     }
    286   }
    287 }
    288 ll a[N];
    289 ll c(int l, int r) {
    290   if (l > r) return inf;
    291   ll ans = 0;
    292   for (int i = l, last; i <= r; i = last + 1) {
    293     last = r / (r / i);
    294     int x = 0;
    295     if (i >= l) x = last - i + 1;
    296     else if (last >= l) x = last - l + 1;
    297     ans += a[r / i] * x;
    298   }
    299   return ans;
    300 }
    301 ll dp[N][17];
    302 void yo(int i, int l, int r, int optl, int optr) {
    303   if(l > r) return;
    304   int mid = (l + r) / 2;
    305   dp[mid][i] = inf;
    306   int opt = optl;
    307   ll cost = c(min(mid, optr) + 1, mid);
    308   for(int k = min(mid, optr); k >= optl ; k--) {
    309     ll cc = dp[k][i - 1] + cost;
    310     if (cc <= dp[mid][i]) {
    311       dp[mid][i] = cc;
    312       opt = k;
    313     }
    314     if (k <= mid) {
    315       if (cost == inf) cost = a[mid / k];
    316       else cost += a[mid / k];
    317     }
    318   }
    319   yo(i, l, mid - 1, optl, opt);
    320   yo(i, mid + 1, r, opt, optr);
    321 }
    322 int32_t main() {
    323   ios_base::sync_with_stdio(0);
    324   cin.tie(0);
    325   totient();
    326   for (int i = 1; i < N; i++) {
    327     a[i] = a[i - 1] + phi[i];
    328   }
    329   int n = 100000;
    330   dp[0][0] = 0;
    331   for (int i = 1; i <= n; i++) {
    332     dp[i][0] = inf;
    333   }
    334   for(int i = 1; i <= n; i++) dp[i][1] = 1LL * i * (i + 1) / 2;
    335   for(int i = 2; i <= 16; i++) yo(i, 1, n, 1, n);
    336   int q; cin >> q;
    337   while (q--) {
    338     int n, k; cin >> n >> k;
    339     if (k >= 20 or (1 << k) > n) {
    340       cout << n << '\n';
    341     }
    342     else {
    343       cout << dp[n][k] << '\n';
    344     }
    345   }
    346   return 0;
    347 }
    348 ```
    349 
    350 Tutorial is loading...
    351 
    352 **Code**
    353 
    354 ```
    355 #include<bits/stdc++.h>
    356 using namespace std;
    357  
    358 const int N = 205;
    359 int mod;
    360  
    361 int power(long long n, long long k) {
    362   int ans = 1 % mod; n %= mod; if (n < 0) n += mod;
    363   while (k) {
    364     if (k & 1) ans = (long long) ans * n % mod;
    365     n = (long long) n * n % mod;
    366     k >>= 1;
    367   }
    368   return ans;
    369 }
    370 int dp[N][N][40], fac[N], ifac[N];
    371 int vis[N][N][40];
    372 int n, a1;
    373 /*
    374 number of solutions to the equation b1 + b2 + ... bn <= a1
    375 s.t. 0<=bi<=n+1-a1 
    376 and there is at least 1 number >= n + 1 - a1, 
    377 at least 2 numbers >= (n - a1), ..., at least (n - a1) numbers >= 2
    378 */
    379 int yo(int i, int sum, int k) { // k <= 2 * sqrt(n)
    380   if (i == n) return fac[n];
    381   if (k == 0) return 1LL * fac[n] * ifac[n - i] % mod;
    382   if (vis[i][sum][k] == a1) return dp[i][sum][k];
    383   vis[i][sum][k] = a1;
    384   int &ans = dp[i][sum][k];
    385   ans = 0;
    386   int r = (a1 - sum) / k;
    387   for (int cnt = r; cnt >= 0; cnt--) {
    388     if (k > 1 and i + cnt < n - a1 + 1 - k + 1) continue;
    389     ans += 1LL * yo(i + cnt, sum + cnt * k, k - 1) * ifac[cnt] % mod;
    390     ans %= mod;
    391   }
    392   return ans;
    393 }
    394 int32_t main() {
    395   ios_base::sync_with_stdio(0);
    396   cin.tie(0);
    397   cin >> n >> mod;
    398   fac[0] = 1;
    399   ifac[0] = 1;
    400   for (int i = 1; i < N; i++) {
    401     fac[i] = 1LL * fac[i - 1] * i % mod;
    402     ifac[i] = power(fac[i], mod - 2);
    403   }
    404   int ans = 0;
    405   int lim = 2 * sqrt(n) + 1;
    406   for (a1 = max(1, n - lim); a1 <= n; a1++) {
    407     ans += yo(0, 0, n + 1 - a1);
    408     ans %= mod;
    409   }
    410   ans %= mod;
    411   cout << ans << '\n';
    412   return 0;
    413 }
    414 ```
    415 
    416 Tutorial is loading...
    417 
    418 **Code**
    419 
    420 ```
    421 #include<bits/stdc++.h>
    422 using namespace std;
    423  
    424 const int N = 1e7 + 9, mod = 998244353;
    425 template <const int32_t MOD>
    426 struct modint {
    427   int32_t value;
    428   modint() = default;
    429   modint(int32_t value_) : value(value_) {}
    430   inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
    431   inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c <    0 ? c + MOD : c); }
    432   inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
    433   inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    434   inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
    435   inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
    436   inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); }
    437   modint<MOD> pow(uint64_t k) const { modint<MOD> x = *this, y = 1; for (; k; k >>= 1) { if (k & 1) y *= x; x *= x; } return y; }
    438   modint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
    439   inline modint<MOD> operator /  (modint<MOD> other) const { return *this *  other.inv(); }
    440   inline modint<MOD> operator /= (modint<MOD> other)       { return *this *= other.inv(); }
    441   inline bool operator == (modint<MOD> other) const { return value == other.value; }
    442   inline bool operator != (modint<MOD> other) const { return value != other.value; }
    443   inline bool operator < (modint<MOD> other) const { return value < other.value; }
    444   inline bool operator > (modint<MOD> other) const { return value > other.value; }
    445 };
    446 template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
    447 template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
    448 template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; }
    449 template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; }
    450  
    451 using mint = modint<mod>;
    452  
    453 mint pw[N];
    454 mint genius(int n, int k) {
    455   if (k == 0) return 1;
    456   vector<mint> c(k, 0), d(k + 1, 0);
    457   d[k] = 1;
    458   for (int i = k - 1; i >= 0; i--) {
    459     c[i] = pw[i] * d[i + 1];
    460     d[i] = (pw[i] - 1) * d[i + 1];
    461   }
    462   mint ans = 0, pwn = mint(2).pow(n), cur = 1;
    463   for (int i = 0; i < k; i++) {
    464     ans += ((k - 1 - i) & 1 ? mod - 1 : 1) * c[i] * cur;
    465     cur *= pwn;
    466   }
    467   return ans;
    468 }
    469 mint f(int n, int k) {
    470   if (k == 0 or n > k) return 0;
    471   mint ans = 1;
    472   for (int i = 0; i < n; i++) {
    473     ans *= pw[k] - pw[i];
    474   }
    475   return ans;
    476 }
    477 int32_t main() {
    478   ios_base::sync_with_stdio(0);
    479   cin.tie(0);
    480   pw[0] = 1;
    481   for (int i = 1; i < N; i++) {
    482     pw[i] = pw[i - 1] * 2;
    483   }
    484   int t; cin >> t;
    485   while (t--) {
    486     int n, k, x; cin >> n >> k >> x;
    487     if (x) {
    488       cout << genius(n, k) << '\n';
    489     }
    490     else {
    491       cout << f(n, k) << '\n';
    492     }
    493   }
    494   return 0;
    495 }
    496 ```