codeforces-scrape

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

1511.md (8865B)


      1 Source: https://codeforces.com/blog/entry/89634
      2 
      3 [1511A - Review Site](/contest/1511/problem/A "Educational Codeforces Round 107 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (adedalic)**
     12 
     13 ```
     14 fun main() {
     15     repeat(readLine()!!.toInt()) {
     16         readLine()!!.toInt()
     17         println(readLine()!!.split(' ').count { it != "2" })
     18     }
     19 }
     20 ```
     21 
     22 [1511B - GCD Length](/contest/1511/problem/B "Educational Codeforces Round 107 (Rated for Div. 2)")
     23 
     24 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     25 
     26 **Tutorial**
     27 
     28 Tutorial is loading...
     29 
     30 **Solution (awoo)**
     31 
     32 ```
     33 for t in range(int(input())):
     34 	a, b, c = map(int, input().split())
     35 	print("1" + "0" * (a - 1), "1" * (b - c + 1) + "0" * (c - 1))
     36 ```
     37 
     38 [1511C - Yet Another Card Deck](/contest/1511/problem/C "Educational Codeforces Round 107 (Rated for Div. 2)")
     39 
     40 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 **Solution (Neon)**
     47 
     48 ```
     49 #include <bits/stdc++.h>
     50 
     51 using namespace std;
     52 
     53 int main() {
     54   int n, q;
     55   scanf("%d%d", &n, &q);
     56   vector<int> a(n);
     57   for (int& x : a) scanf("%d", &x);
     58   while (q--) {
     59     int x;
     60     scanf("%d", &x);
     61     int p = find(a.begin(), a.end(), x) - a.begin();
     62     printf("%d ", p + 1);
     63     rotate(a.begin(), a.begin() + p, a.begin() + p + 1);
     64   }
     65 }
     66 ```
     67 
     68 [1511D - Min Cost String](/contest/1511/problem/D "Educational Codeforces Round 107 (Rated for Div. 2)")
     69 
     70 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     71 
     72 **Tutorial**
     73 
     74 Tutorial is loading...
     75 
     76 **Solution (Neon)**
     77 
     78 ```
     79 #include <bits/stdc++.h>
     80 
     81 using namespace std;
     82 
     83 int n, k;
     84 int cur[26];
     85 vector<int> path;
     86 
     87 void dfs(int v) {
     88   while (cur[v] < k) {
     89     int u = cur[v]++;
     90     dfs(u);
     91     path.push_back(u);
     92   }
     93 }
     94 
     95 int main() {
     96   scanf("%d%d", &n, &k);
     97   dfs(0);
     98   printf("a");
     99   for (int i = 0; i < n - 1; ++i)
    100     printf("%c", path[i % path.size()] + 'a');
    101 }
    102 ```
    103 
    104 [1511E - Colorings and Dominoes](/contest/1511/problem/E "Educational Codeforces Round 107 (Rated for Div. 2)")
    105 
    106 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    107 
    108 **Tutorial**
    109 
    110 Tutorial is loading...
    111 
    112 **Solution (BledDest)**
    113 
    114 ```
    115 #include <bits/stdc++.h>
    116 
    117 using namespace std;
    118 
    119 const int N = 300043;
    120 const int MOD = 998244353;
    121 
    122 int add(int x, int y)
    123 {
    124     x += y;
    125     while(x >= MOD)
    126         x -= MOD;
    127     while(x < 0)
    128         x += MOD;
    129     return x;                         
    130 }
    131 
    132 int sub(int x, int y)
    133 {
    134     return add(x, MOD - y);
    135 }
    136 
    137 int mul(int x, int y)
    138 {
    139     return (x * 1ll * y) % MOD;
    140 }
    141 
    142 int binpow(int x, int y)
    143 {
    144     int z = 1;
    145     while(y > 0)
    146     {
    147         if(y % 2 == 1)
    148             z = mul(z, x);
    149         x = mul(x, x);
    150         y /= 2;
    151     }
    152     return z;
    153 }
    154 
    155 int inv(int x)
    156 {
    157     return binpow(x, MOD - 2);   
    158 }
    159 
    160 int divide(int x, int y)
    161 {
    162     return mul(x, inv(y));
    163 }
    164 
    165 string s[N];
    166 int p[N];
    167 int n, m;
    168 char buf[N];
    169 
    170 int main()
    171 {
    172     scanf("%d %d", &n, &m);
    173     for(int i = 0; i < n; i++)
    174     {
    175         scanf("%s", buf);
    176         s[i] = buf;
    177     }
    178     p[0] = divide(1, 2);
    179     for(int i = 1; i < N; i++)
    180         if(i % 2 == 1)
    181             p[i] = sub(p[i - 1], divide(1, binpow(2, i)));
    182         else
    183             p[i] = add(p[i - 1], divide(1, binpow(2, i)));
    184     int ans = 0;
    185     int w = 0;
    186     for(int i = 0; i < n; i++)
    187         for(int j = 0; j < m; j++)
    188             if(s[i][j] != '*')
    189                 w = add(w, 1);
    190     for(int i = 0; i < n; i++)
    191     {
    192         int c = 0;
    193         for(int j = 0; j < m; j++)
    194         {
    195             if(s[i][j] == '*')
    196                 c = 0;
    197             else
    198                 c++;
    199             if(c > 0)
    200                 ans = add(ans, p[c]);
    201         }
    202     }
    203     for(int j = 0; j < m; j++)
    204     {
    205         int c = 0;
    206         for(int i = 0; i < n; i++)
    207         {
    208             if(s[i][j] == '*')
    209                 c = 0;
    210             else
    211                 c++;
    212             if(c > 0)
    213                 ans = add(ans, p[c]);
    214         }
    215     }
    216     ans = mul(ans, binpow(2, w));
    217     cout << ans << endl;
    218 }
    219 ```
    220 
    221 [1511F - Chainword](/contest/1511/problem/F "Educational Codeforces Round 107 (Rated for Div. 2)")
    222 
    223 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    224 
    225 **Tutorial**
    226 
    227 Tutorial is loading...
    228 
    229 **Solution (awoo)**
    230 
    231 ```
    232 #include <bits/stdc++.h>
    233 
    234 #define forn(i, n) for (int i = 0; i < int(n); i++)
    235 
    236 using namespace std;
    237 
    238 const int MOD = 998244353;
    239 const int K = 161;
    240 const int AL = 26;
    241 
    242 struct node{
    243 	int nxt[AL];
    244 	bool term;
    245 	node(){
    246 		memset(nxt, -1, sizeof(nxt));
    247 		term = false;
    248 	};
    249 	int& operator [](const int x){
    250 		return nxt[x];
    251 	}
    252 };
    253 
    254 vector<node> trie;
    255 
    256 int tot;
    257 
    258 void add(const string &s){
    259 	int cur = 0;
    260 	int d = 1;
    261 	for (const char &c : s){
    262 		++d;
    263 		if (trie[cur][c - 'a'] == -1){
    264 			trie[cur][c - 'a'] = trie.size();
    265 			trie.push_back(node());
    266 			tot += d;
    267 		}
    268 		cur = trie[cur][c - 'a'];
    269 	}
    270 	trie[cur].term = true;
    271 }
    272 
    273 int add(int a, int b){
    274 	a += b;
    275 	if (a >= MOD)
    276 		a -= MOD;
    277 	return a;
    278 }
    279 
    280 int mul(int a, int b){
    281 	return a * 1ll * b % MOD;
    282 }
    283 
    284 typedef array<array<int, K>, K> mat;
    285 
    286 mat operator *(const mat &a, const mat &b){
    287 	mat c;
    288 	forn(i, K) forn(j, K) c[i][j] = 0;
    289 	forn(i, K) forn(j, K) forn(k, K)
    290 		c[i][j] = add(c[i][j], mul(a[i][k], b[k][j]));
    291 	return c;
    292 }
    293 
    294 mat binpow(mat a, long long b){
    295 	mat res;
    296 	forn(i, K) forn(j, K) res[i][j] = i == j;
    297 	while (b){
    298 		if (b & 1)
    299 			res = res * a;
    300 		a = a * a;
    301 		b >>= 1;
    302 	}
    303 	return res;
    304 }
    305 
    306 map<pair<int, int>, int> num;
    307 queue<pair<int, int>> q;
    308 
    309 int get(int v, int u){
    310 	if (v > u) swap(v, u);
    311 	if (!num.count({v, u})){
    312 		int k = num.size();
    313 		assert(k < K);
    314 		num[{v, u}] = k;
    315 		q.push({v, u});
    316 	}
    317 	return num[{v, u}];
    318 }
    319 
    320 int main() {
    321 	int n;
    322 	long long m;
    323 	cin >> n >> m;
    324 	trie = vector<node>(1, node());
    325 	tot = 1;
    326 	forn(i, n){
    327 		string s;
    328 		cin >> s;
    329 		add(s);
    330 	}
    331 	q.push({0, 0});
    332 	num[q.front()] = 0;
    333 	mat init;
    334 	forn(i, K) forn(j, K) init[i][j] = 0;
    335 	while (!q.empty()){
    336 		int v = q.front().first;
    337 		int u = q.front().second;
    338 		q.pop();
    339 		int x = get(v, u);
    340 		forn(c, AL){
    341 			int tov = trie[v][c];
    342 			int tou = trie[u][c];
    343 			if (tov == -1 || tou == -1) continue;
    344 			++init[x][get(tov, tou)];
    345 			if (trie[tov].term) ++init[x][get(0, tou)];
    346 			if (trie[tou].term) ++init[x][get(tov, 0)];
    347 			if (trie[tov].term && trie[tou].term) ++init[x][0];
    348 		}
    349 	}
    350 	init = binpow(init, m);
    351 	printf("%d\n", init[0][0]);
    352 	return 0;
    353 }
    354 ```
    355 
    356 [1511G - Chips on a Board](/contest/1511/problem/G "Educational Codeforces Round 107 (Rated for Div. 2)")
    357 
    358 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    359 
    360 **Tutorial**
    361 
    362 Tutorial is loading...
    363 
    364 **Solution (BledDest)**
    365 
    366 ```
    367 #include <bits/stdc++.h>
    368 
    369 using namespace std;
    370 
    371 const int N = 200043;
    372 const int K = 10;
    373 const int Z = 1 << K;
    374 
    375 int rem[Z];
    376 int t[N];
    377 
    378 int get(int r)
    379 {
    380     int result = 0;
    381     for (; r >= 0; r = (r & (r + 1)) - 1)
    382         result ^= t[r];
    383     return result;
    384 }
    385 
    386 void change(int i, int delta)
    387 {
    388     for (; i < N; i = (i | (i + 1)))
    389         t[i] ^= delta;
    390 }
    391 
    392 int get(int l, int r)
    393 {
    394     return get(r) - get(l - 1);
    395 }
    396 
    397 int ans[N];
    398 int c[N];
    399 int cnt[N];
    400 int n, m;
    401 int ls[N];
    402 int rs[N];
    403 vector<int> qs[N];
    404 vector<int> qs2[N];
    405 
    406 int main()
    407 {
    408     scanf("%d %d", &n, &m);
    409     for(int i = 0; i < n; i++)
    410     {
    411         scanf("%d", &c[i]);
    412         cnt[c[i]]++;
    413     }
    414     int q;
    415     scanf("%d", &q);
    416     for(int i = 0; i < q; i++)
    417     {
    418         int l, r;
    419         scanf("%d %d", &l, &r);
    420         ls[i] = l;                                                                         
    421         rs[i] = r;
    422         qs[l].push_back(i);
    423         qs2[r + 1].push_back(i);
    424     }
    425     for(int i = m; i >= 1; i--)
    426     {
    427         for(int j = 0; j < cnt[i]; j++)
    428         {
    429             rem[i % (1 << K)]++;
    430             int r = i;
    431             while(true)
    432             {
    433                 int l = r - Z + 1;
    434                 l = max(1, l);
    435                 if(l > r)
    436                     break;
    437                 int diff = i - l;
    438                 diff >>= K;
    439                 change(l, diff);
    440                 change(r + 1, diff);
    441                 r -= Z;
    442             }
    443         }
    444         for(auto x : qs[i])
    445         {
    446             int cur = (get(i)) << K;
    447             for(int k = 0; k < Z; k++)
    448             {
    449                 int dist = (k - i) % Z;
    450                 if(dist < 0)
    451                     dist += Z;
    452                 if(rem[k] & 1)
    453                     cur ^= dist;
    454             }
    455             ans[x] ^= cur;
    456         }
    457         for(auto x : qs2[i])
    458         {
    459             int cur = (get(ls[x])) << K;
    460             for(int k = 0; k < Z; k++)
    461             {
    462                 int dist = (k - ls[x]) % Z;
    463                 if(dist < 0)
    464                     dist += Z;
    465                 if(rem[k] & 1)
    466                     cur ^= dist;
    467             }
    468             ans[x] ^= cur;
    469         }
    470     }
    471     for(int i = 0; i < q; i++)
    472         if(ans[i] == 0)
    473             printf("B");
    474         else
    475             printf("A");
    476 }
    477 ```