codeforces-scrape

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

1096.md (12552B)


      1 Source: https://codeforces.com/blog/entry/64156
      2 
      3 [1096A - Find Divisible](/contest/1096/problem/A "Educational Codeforces Round 57 (Rated for Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Solution (PikMike)**
     10 
     11 ```
     12 T = int(input())
     13 for i in range(T):
     14 	l, r = map(int, input().split())
     15 	print(l, l * 2)
     16 ```
     17 
     18 [1096B - Substring Removal](/contest/1096/problem/B "Educational Codeforces Round 57 (Rated for Div. 2)")
     19 
     20 **Tutorial**
     21 
     22 Tutorial is loading...
     23 
     24 **Solution (Vovuh)**
     25 
     26 ```
     27 #include <bits/stdc++.h>
     28 
     29 using namespace std;
     30 
     31 int main() {
     32 #ifdef _DEBUG
     33 	freopen("input.txt", "r", stdin);
     34 //	freopen("output.txt", "w", stdout);
     35 #endif
     36 	
     37 	int n;
     38 	string s;
     39 	cin >> n >> s;
     40 	int cntl = 0, cntr = 0;
     41 	for (int i = 0; i < n; ++i) {
     42 		if (s[i] == s[0]) {
     43 			++cntl;
     44 		} else {
     45 			break;
     46 		}
     47 	}
     48 	for (int i = n - 1; i >= 0; --i) {
     49 		if (s[i] == s[n - 1]) {
     50 			++cntr;
     51 		} else {
     52 			break;
     53 		}
     54 	}
     55 	if (s[0] == s[n - 1]) {
     56 		cout << ((cntl + 1) * 1ll * (cntr + 1)) % 998244353 << endl;
     57 	} else {
     58 		cout << (cntl + cntr + 1) % 998244353;
     59 	}
     60 	
     61 	return 0;
     62 }
     63 ```
     64 
     65 [1096C - Polygon for the Angle](/contest/1096/problem/C "Educational Codeforces Round 57 (Rated for Div. 2)")
     66 
     67 **Tutorial**
     68 
     69 Tutorial is loading...
     70 
     71 **Solution (adedalic)**
     72 
     73 ```
     74 #include<bits/stdc++.h>
     75 using namespace std;
     76 
     77 int ang;
     78 
     79 inline bool read() {
     80 	if(!(cin >> ang))
     81 		return false;
     82 	return true;
     83 }
     84 
     85 inline void solve() {
     86 	int g = __gcd(ang, 180);
     87 	int k = ang / g;
     88 	int n = 180 / g;
     89 	
     90 	if(k + 1 == n)
     91 		k *= 2, n *= 2;
     92 	cout << n << endl;
     93 }
     94 
     95 int main() {
     96 #ifdef _DEBUG
     97 	freopen("input.txt", "r", stdin);
     98 	int tt = clock();
     99 #endif
    100 	cout << fixed << setprecision(15);
    101 	
    102 	int tc; cin >> tc;
    103 	while(tc--) {
    104 		assert(read());
    105 		solve();
    106 		
    107 #ifdef _DEBUG
    108 		cerr << "TIME = " << clock() - tt << endl;
    109 		tt = clock();
    110 #endif
    111 	}
    112 	return 0;
    113 }
    114 ```
    115 
    116 [1096D - Easy Problem](/contest/1096/problem/D "Educational Codeforces Round 57 (Rated for Div. 2)")
    117 
    118 **Tutorial**
    119 
    120 Tutorial is loading...
    121 
    122 **Solution (PikMike)**
    123 
    124 ```
    125 #include <bits/stdc++.h>
    126 
    127 #define forn(i, n) for (int i = 0; i < int(n); i++)
    128 
    129 using namespace std;
    130 
    131 const int N = 100 * 1000 + 13;
    132 const long long INF64 = 1e18;
    133 
    134 int n;
    135 string s;
    136 int a[N];
    137 long long dp[N][5];
    138 
    139 const string h = "hard";
    140 
    141 int main() {
    142 	scanf("%d", &n);
    143 	static char buf[N];
    144 	scanf("%s", buf);
    145 	s = buf;
    146 	forn(i, n)
    147 		scanf("%d", &a[i]);
    148 	
    149 	forn(i, N) forn(j, 5) dp[i][j] = INF64;
    150 	dp[0][0] = 0;
    151 	forn(i, n) forn(j, 4){
    152 		dp[i + 1][j + (s[i] == h[j])] = min(dp[i + 1][j + (s[i] == h[j])], dp[i][j]);
    153 		dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + a[i]);
    154 	}
    155 	
    156 	printf("%lld\n", *min_element(dp[n], dp[n] + 4));
    157 	return 0;
    158 }
    159 ```
    160 
    161 [1096E - The Top Scorer](/contest/1096/problem/E "Educational Codeforces Round 57 (Rated for Div. 2)")
    162 
    163 **Tutorial**
    164 
    165 Tutorial is loading...
    166 
    167 **Solution (PikMike)**
    168 
    169 ```
    170 #include <bits/stdc++.h>
    171 
    172 #define forn(i, n) for (int i = 0; i < int(n); i++)
    173 
    174 using namespace std;
    175 
    176 const int MOD = 998244353;
    177 const int N = 10 * 1000 + 7;
    178 const int M = 100 + 7;
    179 
    180 int fact[N], rfact[N];
    181 
    182 int add(int a, int b){
    183 	a += b;
    184 	if (a >= MOD) a -= MOD;
    185 	if (a < 0) a += MOD;
    186 	return a;
    187 }
    188 
    189 int mul(int a, int b){
    190 	return (a * 1ll * b) % MOD;
    191 }
    192 
    193 int binpow(int a, int b){
    194 	int res = 1;
    195 	while (b){
    196 		if (b & 1)
    197 			res = mul(res, a);
    198 		a = mul(a, a);
    199 		b >>= 1;
    200 	}
    201 	return res;
    202 }
    203 
    204 int cnk(int n, int k){
    205 	if (n == k) return 1;
    206 	if (k < 0 || k > n) return 0;
    207 	return mul(fact[n], mul(rfact[k], rfact[n - k]));
    208 }
    209 
    210 int g(int s, int p, int m){
    211 	int res = 0;
    212 	forn(i, p + 1)
    213 		res = add(res, mul(i & 1 ? MOD - 1 : 1, mul(cnk(p, i), cnk(s + p - 1 - i * (m + 1), p - 1))));
    214 	return res;
    215 }
    216 
    217 int inv(int x){
    218 	return mul(rfact[x], fact[x - 1]);
    219 }
    220 
    221 int main() {
    222 	fact[0] = 1;
    223 	for (int i = 1; i < N; ++i) fact[i] = mul(fact[i - 1], i);
    224 	rfact[N - 1] = binpow(fact[N - 1], MOD - 2);
    225 	for (int i = N - 2; i >= 0; --i) rfact[i] = mul(rfact[i + 1], i + 1);
    226 	
    227 	int p, s, r;
    228 	scanf("%d%d%d", &p, &s, &r);
    229 	
    230 	int Q = cnk(s - r + p - 1, p - 1);
    231 	int P = 0;
    232 	for (int t = r; t <= s; ++t) for (int q = 1; q <= p; ++q)
    233 		P = add(P, mul(mul(cnk(p - 1, q - 1), inv(q)), g(s - q * t, p - q, t - 1)));
    234 	
    235 	printf("%d\n", mul(P, binpow(Q, MOD - 2)));
    236 	return 0;
    237 }
    238 ```
    239 
    240 [1096F - Inversion Expectation](/contest/1096/problem/F "Educational Codeforces Round 57 (Rated for Div. 2)")
    241 
    242 **Tutorial**
    243 
    244 Tutorial is loading...
    245 
    246 **Solution (PikMike)**
    247 
    248 ```
    249 #include <bits/stdc++.h>
    250 
    251 #define forn(i, n) for (int i = 0; i < int(n); i++)
    252 
    253 using namespace std;
    254 
    255 const int N = 200 * 1000 + 13;
    256 const int MOD = 998244353;
    257 
    258 int n;
    259 int p[N];
    260 bool used[N];
    261 int gt[N];
    262 
    263 int add(int a, int b){
    264 	a += b;
    265 	if (a >= MOD)
    266 		a -= MOD;
    267 	return a;
    268 }
    269 
    270 int mul(int a, int b){
    271 	return (a * 1ll * b) % MOD;
    272 }
    273 
    274 int binpow(int a, int b){
    275 	int res = 1;
    276 	while (b){
    277 		if (b & 1)
    278 			res = mul(res, a);
    279 		a = mul(a, a);
    280 		b >>= 1;
    281 	}
    282 	return res;
    283 }
    284 
    285 int f[N];
    286 
    287 void upd(int x){
    288 	for (int i = x; i < N; i |= i + 1)
    289 		++f[i];
    290 }
    291 
    292 int get(int x){
    293 	int sum = 0;
    294 	for (int i = x; i >= 0; i = (i & (i + 1)) - 1)
    295 		sum += f[i];
    296 	return sum;
    297 }
    298 
    299 int main() {
    300 	scanf("%d", &n);
    301 	forn(i, n){
    302 		scanf("%d", &p[i]);
    303 		if (p[i] != -1)
    304 			used[p[i]] = true;
    305 	}
    306 	
    307 	int cur = 0;
    308 	for (int i = n; i >= 1; --i){
    309 		gt[i] = cur;
    310 		cur += !used[i];
    311 	}
    312 	
    313 	// case 1
    314 	int ans = mul(mul(cur, cur - 1), binpow(4, MOD - 2));
    315 	
    316 	int inv = binpow(cur, MOD - 2);
    317 	
    318 	// case 2
    319 	int lft = 0;
    320 	forn(i, n){
    321 		if (p[i] == -1)
    322 			++lft;
    323 		else
    324 			ans = add(ans, mul(lft, mul(gt[p[i]], inv)));
    325 	}
    326 	
    327 	// case 3
    328 	int rgh = 0;
    329 	for (int i = n - 1; i >= 0; --i){
    330 		if (p[i] == -1)
    331 			++rgh;
    332 		else
    333 			ans = add(ans, mul(rgh, mul(cur - gt[p[i]], inv)));
    334 	}
    335 	
    336 	// case 4	
    337 	int tmp = 0;
    338 	forn(i, n) if (p[i] != -1){
    339 		ans = add(ans, tmp - get(p[i]));
    340 		upd(p[i]);
    341 		++tmp;
    342 	}
    343 	
    344 	printf("%d\n", ans);
    345 	return 0;
    346 }
    347 ```
    348 
    349 [1096G - Lucky Tickets](/contest/1096/problem/G "Educational Codeforces Round 57 (Rated for Div. 2)")
    350 
    351 **Tutorial**
    352 
    353 Tutorial is loading...
    354 
    355 **Solution 1 (adedalic)**
    356 
    357 ```
    358 #include<bits/stdc++.h>
    359 
    360 using namespace std;
    361 
    362 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    363 #define forn(i, n) fore(i, 0, n)
    364 
    365 #define sz(a) int((a).size())
    366 #define all(a) (a).begin(), (a).end()
    367 
    368 #define mp make_pair
    369 #define pb push_back
    370 
    371 #define x first
    372 #define y second
    373 
    374 typedef long long li;
    375 typedef long double ld;
    376 typedef pair<int, int> pt;
    377 
    378 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
    379 	return out << "(" << p.x << ", " << p.y << ")";
    380 }
    381 
    382 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
    383 	out << "[";
    384 	forn(i, sz(v)) {
    385 		if(i) out << ", ";
    386 		out << v[i];
    387 	}
    388 	return out << "]";
    389 }
    390 
    391 const int INF = int(1e9);
    392 const li INF64 = li(1e18);
    393 const ld EPS = 1e-9;
    394 
    395 const int N = 2500 * 1000 + 555;
    396 const int LOGN = 22;
    397 
    398 const int MOD = 998244353;
    399 int g = 3;
    400 
    401 inline int mul(int a, int b){
    402 	return int(a * 1ll * b % MOD);
    403 }
    404 
    405 inline int norm(int a) {
    406 	if(a >= MOD)
    407 		a -= MOD;
    408 	if(a < 0)
    409 		a += MOD;
    410 	return a;
    411 }
    412 
    413 inline int binPow(int a, int k) {
    414 	int ans = 1;
    415 	while(k > 0) {
    416 		if(k & 1)
    417 			ans = mul(ans, a);
    418 		a = mul(a, a);
    419 		k >>= 1;
    420 	}
    421 	return ans;
    422 }
    423 
    424 inline int inv(int a) {
    425 	return binPow(a, MOD - 2);
    426 }
    427 
    428 vector<int> w[LOGN];
    429 vector<int> rv[LOGN];
    430 
    431 void precalc() {
    432     int wb = binPow(g, (MOD - 1) / (1 << LOGN));
    433 
    434     for(int st = 0; st < LOGN - 1; st++) {
    435         w[st].assign(1 << st, 1);
    436 
    437         int bw = binPow(wb, 1 << (LOGN - st - 1));
    438         int cw = 1;
    439 
    440         for (int k = 0; k < (1 << st); k++) {
    441             w[st][k] = cw;
    442             cw = mul(cw, bw);
    443         }
    444     }
    445     for(int st = 0; st < LOGN; st++) {
    446         rv[st].assign(1 << st, 0);
    447 
    448         if(st == 0) {
    449             rv[st][0] = 0;
    450             continue;
    451         }
    452         int h = (1 << (st - 1));
    453         for(int k = 0; k < (1 << st); k++)
    454             rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    455     }
    456 }
    457 
    458 inline void fft(int a[N], int n, bool inverse) {
    459     int ln = 0;
    460     while((1 << ln) < n)
    461         ln++;
    462 
    463     assert((1 << ln) < N);
    464     n = (1 << ln);
    465 
    466     forn(i, n) {
    467         int ni = rv[ln][i];
    468         if(i < ni)
    469             swap(a[i], a[ni]);
    470     }
    471 
    472     for(int st = 0; (1 << st) < n; st++) {
    473         int len = (1 << st);
    474         for(int k = 0; k < n; k += (len << 1)) {
    475             for(int pos = k; pos < k + len; pos++) {
    476                 int l = a[pos];
    477                 int r = mul(a[pos + len], w[st][pos - k]);
    478 
    479                 a[pos] = norm(l + r);
    480                 a[pos + len] = norm(l - r);
    481             }
    482         }
    483     }
    484 
    485     if(inverse) {
    486         int in = inv(n);
    487         forn(i, n)
    488             a[i] = mul(a[i], in);
    489         reverse(a + 1, a + n);
    490     }
    491 }
    492 
    493 int aa[N], bb[N], cc[N];
    494 
    495 inline vector<int> multiply(const vector<int> a, const vector<int> b) {
    496 	int ln = 1;
    497 	while(ln < (sz(a) + sz(b)))
    498 		ln <<= 1;
    499 		
    500 	forn(i, ln)
    501 		aa[i] = (i < sz(a) ? a[i] : 0);
    502 		
    503 	forn(i, ln)
    504 		bb[i] = (i < sz(b) ? b[i] : 0);
    505 		
    506 	fft(aa, ln, false);
    507 	fft(bb, ln, false);
    508 	
    509 	forn(i, ln)
    510 		cc[i] = mul(aa[i], bb[i]);
    511 		
    512 	fft(cc, ln, true);
    513 	
    514 	vector<int> c(ln, 0);
    515 	forn(i, sz(c))
    516 		c[i] = cc[i];
    517 	
    518 	while(sz(c) > 1 && c.back() == 0)
    519 		c.pop_back();
    520 	return c;
    521 }
    522 
    523 int n, k, a[11];
    524 
    525 inline bool read() {
    526 	if(!(cin >> n >> k))
    527 		return false;
    528 	forn(i, k)
    529 		cin >> a[i];
    530 	return true;
    531 }
    532 
    533 inline void solve() {
    534 	sort(a, a + k);
    535 	
    536 	vector<int> ans(1, 1);
    537 	vector<int> f(10, 0);
    538 	forn(i, k)
    539 		f[a[i]] = 1;
    540 
    541 	precalc();
    542 		
    543 	int pw = n / 2;
    544 	while(pw > 0) {
    545 		if(pw & 1)
    546 			ans = multiply(ans, f);
    547 		f = multiply(f, f);
    548 		pw >>= 1;
    549 	}
    550 	
    551 	int res = 0;
    552 	forn(i, sz(ans))
    553 		res = norm(res + mul(ans[i], ans[i]));
    554 	cout << res << endl;
    555 }
    556 
    557 int main() {
    558 #ifdef _DEBUG
    559 	freopen("input.txt", "r", stdin);
    560 	int tt = clock();
    561 #endif
    562 	cout << fixed << setprecision(15);
    563 	
    564 	if(read()) {
    565 		solve();
    566 		
    567 #ifdef _DEBUG
    568 		cerr << "TIME = " << clock() - tt << endl;
    569 		tt = clock();
    570 #endif
    571 	}
    572 	return 0;
    573 }
    574 ```
    575 
    576 **Solution 2 (BledDest)**
    577 
    578 ```
    579 #include<bits/stdc++.h>
    580 
    581 using namespace std;
    582 
    583 const int LOGN = 21;
    584 const int N = (1 << LOGN);
    585 const int MOD = 998244353;
    586 const int g = 3;
    587 
    588 #define forn(i, n) for(int i = 0; i < int(n); i++)
    589 
    590 inline int mul(int a, int b)
    591 {
    592 	return (a * 1ll * b) % MOD;
    593 }
    594 
    595 inline int norm(int a) 
    596 {
    597 	while(a >= MOD)
    598 		a -= MOD;
    599 	while(a < 0)
    600 		a += MOD;
    601 	return a;
    602 }
    603 
    604 inline int binPow(int a, int k) 
    605 {
    606 	int ans = 1;
    607 	while(k > 0) 
    608 	{
    609 		if(k & 1)
    610 			ans = mul(ans, a);
    611 		a = mul(a, a);
    612 		k >>= 1;
    613 	}
    614 	return ans;
    615 }
    616 
    617 inline int inv(int a) 
    618 {
    619 	return binPow(a, MOD - 2);
    620 }
    621 
    622 vector<int> w[LOGN];
    623 vector<int> iw[LOGN];
    624 vector<int> rv[LOGN];
    625 
    626 void precalc() 
    627 {
    628 	int wb = binPow(g, (MOD - 1) / (1 << LOGN));
    629 	
    630 	for(int st = 0; st < LOGN; st++) 
    631 	{
    632 		w[st].assign(1 << st, 1);
    633 		iw[st].assign(1 << st, 1);
    634 		
    635 		int bw = binPow(wb, 1 << (LOGN - st - 1));
    636 		int ibw = inv(bw);
    637 		
    638 		int cw = 1;
    639 		int icw = 1;
    640 		
    641 		for(int k = 0; k < (1 << st); k++) 
    642 		{
    643 			w[st][k] = cw;
    644 			iw[st][k] = icw;
    645 			
    646 			cw = mul(cw, bw);
    647 			icw = mul(icw, ibw);
    648 		}
    649 		
    650 		rv[st].assign(1 << st, 0);
    651 		
    652 		if(st == 0) 
    653 		{
    654 			rv[st][0] = 0;
    655 			continue;
    656 		}
    657 		int h = (1 << (st - 1));
    658 		for(int k = 0; k < (1 << st); k++)
    659 			rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
    660 	}
    661 }
    662 
    663 inline void fft(int a[N], int n, int ln, bool inverse) 
    664 {	
    665 	for(int i = 0; i < n; i++) 
    666 	{
    667 		int ni = rv[ln][i];
    668 		if(i < ni)
    669 			swap(a[i], a[ni]);
    670 	}
    671 	
    672 	for(int st = 0; (1 << st) < n; st++) 
    673 	{
    674 		int len = (1 << st);
    675 		for(int k = 0; k < n; k += (len << 1)) 
    676 		{
    677 			for(int pos = k; pos < k + len; pos++) 
    678 			{
    679 				int l = a[pos];
    680 				int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k]));
    681 				
    682 				a[pos] = norm(l + r);
    683 				a[pos + len] = norm(l - r);
    684 			}
    685 		}
    686 	}
    687 	
    688 	if(inverse) 
    689 	{
    690 		int in = inv(n);
    691 		for(int i = 0; i < n; i++)
    692 			a[i] = mul(a[i], in);
    693 	}
    694 }
    695 
    696 int aa[N], bb[N], cc[N];
    697 
    698 inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc) 
    699 {
    700 	int n = 1, ln = 0;
    701 	while(n < (sza + szb))
    702 		n <<= 1, ln++;
    703 	for(int i = 0; i < n; i++)
    704 		aa[i] = (i < sza ? a[i] : 0);
    705 	for(int i = 0; i < n; i++)
    706 		bb[i] = (i < szb ? b[i] : 0);
    707 		
    708 	fft(aa, n, ln, false);
    709 	fft(bb, n, ln, false);
    710 	
    711 	for(int i = 0; i < n; i++)
    712 		cc[i] = mul(aa[i], bb[i]);
    713 		
    714 	fft(cc, n, ln, true);
    715 	
    716 	szc = n;
    717 	for(int i = 0; i < n; i++)
    718 		c[i] = cc[i];
    719 }
    720 
    721 vector<int> T[N];
    722 
    723 int a[N];
    724 int b[N];
    725 int c[N];
    726 
    727 #define sz(a) (int(a.size()))
    728 
    729 int main()
    730 {
    731 	precalc();
    732 	int n, k;
    733 	scanf("%d %d", &n, &k);
    734 	for(int i = 0; i < k; i++)
    735 	{
    736 	    int x;
    737 	    scanf("%d", &x);
    738 	    a[x] = 1;
    739 	}
    740 	int nn = 1, ln = 0;
    741 	int nw = (n * 5) + 1;
    742 	while(nn < nw)
    743 	{
    744 		nn *= 2;
    745 		ln++;
    746 	}
    747 	fft(a, nn, ln, false);
    748 	forn(i, nn)
    749 		a[i] = binPow(a[i], n / 2);
    750 	fft(a, nn, ln, true);
    751 	int ans = 0;
    752 	forn(i, nn)
    753 		ans = norm(ans + binPow(a[i], 2));
    754 	printf("%d\n", ans);
    755 	return 0;	
    756 }
    757 ```