794.md (33512B)
1 Source: https://codeforces.com/blog/entry/51962 2 3 **Bank Robbery** 4 5 Author : [zscoder](/profile/zscoder "Grandmaster zscoder") 6 7 This is a simple implementation problem. We iterate through all banknotes one by one and check if Oleg can take each of them. If a banknote is at position *x*, then Oleg can take it if and only if *b* < *x* < *c*. This can be checked in *O*(1) time. Thus, the total complexity is *O*(*n*). Note that the information on the starting position of Oleg is useless here. 8 9 **Code** 10 11 ``` 12 #include <bits/stdc++.h> 13 #include <ext/pb_ds/assoc_container.hpp> 14 #include <ext/pb_ds/tree_policy.hpp> 15 16 using namespace std; 17 using namespace __gnu_pbds; 18 19 #define fi first 20 #define se second 21 #define mp make_pair 22 #define pb push_back 23 #define fbo find_by_order 24 #define ook order_of_key 25 26 typedef long long ll; 27 typedef pair<ll,ll> ii; 28 typedef vector<ll> vi; 29 typedef long double ld; 30 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 31 typedef set<int>::iterator sit; 32 typedef map<int,int>::iterator mit; 33 typedef vector<int>::iterator vit; 34 35 int main() 36 { 37 ios_base::sync_with_stdio(0); cin.tie(0); 38 int a, b, c; cin>>a>>b>>c; 39 int n; cin>>n; 40 int ans=0; 41 for(int i=0;i<n;i++) 42 { 43 int x; cin>>x; 44 if(x>b&&x<c) ans++; 45 } 46 cout<<ans<<'\n'; 47 } 48 ``` 49 50 **Cutting Carrot** 51 52 Author : [zscoder](/profile/zscoder "Гроссмейстер zscoder") 53 54 Let's find the value of *x**i* explicitly. Suppose we make the *i*-th cut and distance *x**i* from the apex. Then, the ratio of similitude of the isosceles triangle with apex equal to the apex of the carrot and the base equal to the *i*-th cut and the whole carrot is . Since the area of this smaller isosceles triangle is the sum of areas of the first *i* pieces, which is  of the whole carrot. Thus, , which is equivalent to . Thus,  and we can find each *x**i* in *O*(1) time. The total complexity is *O*(*n*). 55 56 **Code** 57 58 ``` 59 #include <bits/stdc++.h> 60 #include <ext/pb_ds/assoc_container.hpp> 61 #include <ext/pb_ds/tree_policy.hpp> 62 63 using namespace std; 64 using namespace __gnu_pbds; 65 66 #define fi first 67 #define se second 68 #define mp make_pair 69 #define pb push_back 70 #define fbo find_by_order 71 #define ook order_of_key 72 73 typedef long long ll; 74 typedef pair<ll,ll> ii; 75 typedef vector<ll> vi; 76 typedef long double ld; 77 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 78 typedef set<int>::iterator sit; 79 typedef map<int,int>::iterator mit; 80 typedef vector<int>::iterator vit; 81 82 int main() 83 { 84 ios_base::sync_with_stdio(0); cin.tie(0); 85 ll n, h; cin>>n>>h; 86 for(int i=1;i<=n-1;i++) 87 { 88 cout<<fixed<<setprecision(12)<<sqrt(ld(i)/ld(n))*ld(h); 89 if(i<n-1) cout<<' '; 90 } 91 cout<<'\n'; 92 } 93 ``` 94 95 **Naming Company** 96 97 Author : [zscoder](/profile/zscoder "Гроссмейстер zscoder") 98 99 First, it is clear that Oleg will place  letters and Igor will place  letters. Next, it is clear that Oleg and Igor will both choose their smallest and biggest letters respectively to place in the final string. Thus, we now consider that Oleg places his smallest  letters and Igor places his largest  letters. 100 101 Consider the following greedy strategy. When it's Oleg's turn, he will replace the frontmost question mark with his smallest letter. When it's Igor's turn, he will replace the frontmost question mark with his largest letter. At first glance, you might think that this works. However, there's another case that we haven't considered. 102 103 Suppose Oleg has the letters {*x*, *y*, *z*} and Igor has the letters {*a*, *b*, *c*}. According to our previous strategy, Oleg will place x as the first letter. However, that's not optimal. He can place his letters at the back and force Igor to place the first letter. The reason is because the largest letter of Igor is not larger than the smallest letter of Oleg. Thus, it is beneficial for Oleg to place his letters at the back and force Igor to place his letters in front. 104 105 So, what exactly will the final string look like? We'll look at the moves one by one. If at some point Oleg's smallest letter is still strictly smaller than Igor's largest letter, then both player must put their smallest (largest if it's Igor) letter as the frontmost letter. Why? Suppose not, then on the next turn the other player will occupy that spot with their best (smallest if Oleg, largest if Igor) letter, and the resulting string will be worse for the current player. This proves that greedy is correct in this case. 106 107 Now, what if Oleg's smallest letter is not smaller than Igor's largest letter. In this case, both players will want to force the other player to place their own letter at the beginning of the string. It can be proven that in this case, each person will place their current worst (largest if Oleg, smallest if Igor) letter at the back of the string in the optimal strategy. Thus, we can calculate the final string starting from this point and after that reverse this part and combine it with the first part of the string where both players greedily place their best letters in the beginning. 108 109 Time Complexity : *O*(*n*) 110 111 Many people failed on pretest 6 initially because they didn't consider the second case. 112 113 **Code** 114 115 ``` 116 #include <bits/stdc++.h> 117 #include <ext/pb_ds/assoc_container.hpp> 118 #include <ext/pb_ds/tree_policy.hpp> 119 120 using namespace std; 121 using namespace __gnu_pbds; 122 123 #define fi first 124 #define se second 125 #define mp make_pair 126 #define pb push_back 127 #define fbo find_by_order 128 #define ook order_of_key 129 130 typedef long long ll; 131 typedef pair<ll,ll> ii; 132 typedef vector<ll> vi; 133 typedef long double ld; 134 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 135 typedef set<int>::iterator sit; 136 typedef map<int,int>::iterator mit; 137 typedef vector<int>::iterator vit; 138 139 int main() 140 { 141 ios_base::sync_with_stdio(0); cin.tie(0); 142 string ansl; 143 string ansr; 144 string s,t; 145 cin>>s>>t; 146 sort(s.begin(),s.end()); 147 sort(t.begin(),t.end()); 148 reverse(t.begin(),t.end()); 149 int n = s.length(); 150 deque<char> a,b; 151 for(int i=0;i<(n+1)/2;i++) 152 { 153 a.pb(s[i]); 154 } 155 for(int i=0;i<n/2;i++) 156 { 157 b.pb(t[i]); 158 } 159 bool mode=0; 160 for(int i=0;i<n;i++) 161 { 162 if(i&1) 163 { 164 if(!a.empty()&&a[0]>=b[0]) 165 { 166 mode=1; 167 } 168 if(mode) 169 { 170 ansr+=b.back(); 171 b.pop_back(); 172 } 173 else 174 { 175 ansl+=b[0]; 176 b.pop_front(); 177 } 178 } 179 else //P1's turn 180 { 181 if(!b.empty()&&a[0]>=b[0]) 182 { 183 mode=1; 184 } 185 if(mode) 186 { 187 ansr+=a.back(); 188 a.pop_back(); 189 } 190 else 191 { 192 ansl+=a[0]; 193 a.pop_front(); 194 } 195 } 196 } 197 reverse(ansr.begin(),ansr.end()); 198 ansl+=ansr; 199 cout<<ansl<<'\n'; 200 } 201 ``` 202 203 **Labelling Cities** 204 205 Author : [AnonymousBunny](/profile/AnonymousBunny "Кандидат в мастера AnonymousBunny") 206 207 Add each vertex to its own adjacency list. Now, we claim that if it is possible to label the cities to satisfy the problem conditions, then it is possible to do so so that for every two cities with the same adjacency list, they're labelled with the same number. 208 209 Indeed, if they have the same adjacency list, they must be neighbours. Thus, the difference between their labels is at most 1. Suppose we label the first vertex *u* with number *i* and the second vertex *v* with the number *i* + 1. Note that since their adjacency lists are equal, a vertex *x* is a neighbour of *u* iff it's a neighbour of *v*. Thus, *u* and *v* can't have neighbours with labels *i* - 1 or *i* + 2, or else it will contradict the condition. Thus, all neighbours of *u* and *v* have labels *i* or *i* + 1. Thus, we can safely change the label of the second vertex *v* to *i* and the conditions will still hold. 210 211 Thus, we can sort the set of adjacency lists of each vertex, and then group the vertices with the same adjacency list together. Suppose there are *k* such groups. For simplicity, we can create a new graph where each group represent a vertex of the new graph. Connect two groups *i* and *j* if and only if there exist some vertex in group *i* that connects to a vertex in group *j*. Note that the graph will have at most *O*(*m*) edges. Now, if a vertex has degree ≥ 3, we can't assign a number to that vertex properly, as one of its neighbours will not have a label which have a difference ≤ 1 from it. Thus, all vertices in the new graph must have degree ≤ 2. Since it's connected, it must be either a cycle or a path. However, it can be easily seen that there is no labelling if it's a cycle. Thus, it must be a path. Now, we can just assign the labels to the graph from one end of the path to the other end by the numbers 1 to *k*. Finally, the label of a vertex is simply the label of its group. 212 213 This solution can be implemented in  time. 214 215 **Code** 216 217 ``` 218 #include <bits/stdc++.h> 219 #include <ext/pb_ds/assoc_container.hpp> 220 #include <ext/pb_ds/tree_policy.hpp> 221 222 using namespace std; 223 using namespace __gnu_pbds; 224 225 #define fi first 226 #define se second 227 #define mp make_pair 228 #define pb push_back 229 #define fbo find_by_order 230 #define ook order_of_key 231 232 typedef long long ll; 233 typedef pair<int,int> ii; 234 typedef vector<ll> vi; 235 typedef long double ld; 236 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 237 typedef set<int>::iterator sit; 238 typedef map<int,int>::iterator mit; 239 typedef vector<int>::iterator vit; 240 241 const int N = 300000; 242 243 pair<vi,int> adj[N+2]; 244 int ans[N+2]; 245 int lab[N+2]; 246 int lab2[N+2]; 247 set<int> adj2[N+2]; 248 vector<ii> edges; 249 250 struct DSU 251 { 252 int S; 253 254 struct node 255 { 256 int p; ll sum; 257 }; 258 vector<node> dsu; 259 260 DSU(int n) 261 { 262 S = n; 263 for(int i = 0; i < n; i++) 264 { 265 node tmp; 266 tmp.p = i; tmp.sum = 0; 267 dsu.pb(tmp); 268 } 269 } 270 271 void reset(int n) 272 { 273 dsu.clear(); 274 S = n; 275 for(int i = 0; i < n; i++) 276 { 277 node tmp; 278 tmp.p = i; tmp.sum = 0; 279 dsu.pb(tmp); 280 } 281 } 282 283 int rt(int u) 284 { 285 if(dsu[u].p == u) return u; 286 dsu[u].p = rt(dsu[u].p); 287 return dsu[u].p; 288 } 289 290 void merge(int u, int v) 291 { 292 u = rt(u); v = rt(v); 293 if(u == v) return ; 294 if(rand()&1) swap(u, v); 295 dsu[v].p = u; 296 dsu[u].sum += dsu[v].sum; 297 } 298 299 bool sameset(int u, int v) 300 { 301 if(rt(u) == rt(v)) return true; 302 return false; 303 } 304 305 ll getstat(int u) 306 { 307 return dsu[rt(u)].sum; 308 } 309 }; 310 311 deque<int> chain; 312 313 void dfs(int u, int p, bool type) 314 { 315 if(type) chain.pb(u); 316 else chain.push_front(u); 317 int c=0; 318 for(sit it = adj2[u].begin(); it != adj2[u].end(); it++) 319 { 320 int v = (*it); 321 if(v==p) continue; 322 if(p!=-1) 323 { 324 dfs(v,u,type); 325 } 326 else 327 { 328 dfs(v,u,c); 329 c++; 330 } 331 } 332 } 333 334 int main() 335 { 336 //ios_base::sync_with_stdio(0); cin.tie(0); 337 int n, m; scanf("%d %d", &n, &m); 338 for(int i = 0; i < m; i++) 339 { 340 int u, v; scanf("%d %d", &u, &v); 341 u--; v--; 342 adj[u].fi.pb(v); 343 adj[v].fi.pb(u); 344 edges.pb(mp(u,v)); 345 } 346 for(int i = 0; i < n; i++) 347 { 348 adj[i].fi.pb(i); 349 adj[i].se = i; 350 sort(adj[i].fi.begin(),adj[i].fi.end()); 351 } 352 sort(adj,adj+n); 353 int cnt = 1; 354 for(int i = 0; i < n; i++) 355 { 356 if(i==0) 357 { 358 lab[adj[i].se] = cnt; 359 } 360 else 361 { 362 if(adj[i].fi==adj[i-1].fi) 363 { 364 lab[adj[i].se]=cnt; 365 } 366 else 367 { 368 lab[adj[i].se]=++cnt; 369 } 370 } 371 } 372 if(cnt==1) 373 { 374 printf("YES\n"); 375 for(int i = 0; i < n; i++) 376 { 377 printf("%d ",lab[i]); 378 } 379 printf("\n"); 380 return 0; 381 } 382 DSU dsu(cnt+1); 383 for(int i = 0; i < m; i++) 384 { 385 int u = edges[i].fi; int v = edges[i].se; 386 if(lab[u]!=lab[v]) 387 { 388 adj2[lab[u]].insert(lab[v]); 389 adj2[lab[v]].insert(lab[u]); 390 dsu.merge(lab[u],lab[v]); 391 } 392 } 393 bool pos = 1; 394 for(int i = 1; i <= cnt; i++) 395 { 396 if(dsu.rt(i)!=dsu.rt(1)) 397 { 398 pos=0; 399 break; 400 } 401 } 402 if(!pos) 403 { 404 printf("NO\n"); 405 return 0; 406 } 407 int d1 = 0; 408 for(int i = 1; i <= cnt; i++) 409 { 410 if(adj2[i].size()>2) 411 { 412 printf("NO\n"); 413 return 0; 414 } 415 if(adj2[i].size()==1) d1++; 416 else assert(adj2[i].size()==2); 417 } 418 if(d1==2) 419 { 420 printf("YES\n"); 421 dfs(1,-1,0); 422 for(int i = 0; i < chain.size(); i++) 423 { 424 lab2[chain[i]] = i+1; 425 } 426 for(int i = 0; i < n; i++) 427 { 428 printf("%d ",lab2[lab[i]]); 429 } 430 printf("\n"); 431 } 432 else 433 { 434 printf("NO\n"); 435 return 0; 436 } 437 } 438 ``` 439 440 **Choosing Carrot** 441 442 Author : [zscoder](/profile/zscoder "Гроссмейстер zscoder") 443 444 First, we solve the problem when no one has any extra turns. 445 446 Suppose we're binary searching the answer. Let all the numbers ≥ *x* be equal to 1 and all the numbers < *x* be equal to 0. Both players can remove one number from one end of the row. The goal of the first player is to let the remaining number be 1 and the goal of the second player is to leave 0 in the end. If the first player can win, this means that the answer is at least *x*. Thus, we first try to solve this simpler problem. 447 448 We claim that the first player wins if and only if : 449 450 1. *n* is even and one of the two middle numbers is 1. 451 2. *n* is odd, the middle digit is 1 and at least one of the digits beside the middle digit is 1 (unless *n* = 1, for which first players wins when the only carrot is labelled 1) 452 453 Indeed, once we deduce this, we can easily prove this by induction on *n*. The proof is just doing casework and considering all possible moves. 454 455 Once we have this fact, we realize we don't actually have to binary search the answer. If *n* is even, the answer is  while if *n* ≥ 3 is odd, the answer is . (If *n* = 1 then the answer is obviously *a*1.) 456 457 Now, we have to take extra moves into account. Fortunately, it's not very difficult. Having *k* extra moves just means that Player 1 can choose to start the game in any subsegment of length *n* - *k*. Thus, we just have to compute the maximum answer for all subsegments of length *n* - *k* for all 0 ≤ *k* ≤ *n* - 1. With the formula above, you can find all the answers in *O*(*n*) time or even  time if you use sparse table for range maximum query. 458 459 **Code** 460 461 ``` 462 #include <bits/stdc++.h> 463 #include <ext/pb_ds/assoc_container.hpp> 464 #include <ext/pb_ds/tree_policy.hpp> 465 466 using namespace std; 467 using namespace __gnu_pbds; 468 469 #define fi first 470 #define se second 471 #define mp make_pair 472 #define pb push_back 473 #define fbo find_by_order 474 #define ook order_of_key 475 476 typedef long long ll; 477 typedef pair<ll,ll> ii; 478 typedef vector<ll> vi; 479 typedef long double ld; 480 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 481 typedef set<int>::iterator sit; 482 typedef map<int,int>::iterator mit; 483 typedef vector<int>::iterator vit; 484 485 int a[300001]; 486 int ans[300001]; 487 int b[300001]; 488 489 int main() 490 { 491 ios_base::sync_with_stdio(0); cin.tie(0); 492 int n; cin>>n; 493 int mx=0; 494 for(int i=0;i<n;i++) 495 { 496 cin>>a[i]; 497 mx=max(mx,a[i]); 498 } 499 for(int i=0;i<n-2;i++) 500 { 501 b[i]=min(a[i+1],max(a[i],a[i+2])); 502 } 503 ans[n-1]=mx; 504 int odd=n;int even=n; 505 if(n&1) even=n-1; 506 else odd=n-1; 507 mx=0; 508 for(int i=even;i>=2;i-=2) 509 { 510 int l = (i-1)/2; int r=n-i/2; 511 assert(l<=r); 512 mx=max(mx,max(a[l],a[r])); 513 if(i==even) 514 { 515 assert(r-l<=2); 516 if(r-l==2) 517 { 518 mx=max(mx,a[l+1]); 519 } 520 } 521 ans[n-i]=mx; 522 } 523 mx=0; 524 for(int i=odd;i>=3;i-=2) 525 { 526 int l = i/2-1; int r=n-2-i/2; 527 assert(l<=r); 528 if(i==odd) assert(r-l<=1); 529 mx=max(mx,max(b[l],b[r])); 530 ans[n-i]=mx; 531 } 532 for(int i=0;i<n;i++) 533 { 534 cout<<ans[i]; 535 if(i<n-1) cout<<' '; 536 } 537 cout<<'\n'; 538 } 539 ``` 540 541 **Leha and security system** 542 543 Author : [hloya_ygrt](/profile/hloya_ygrt "Мастер hloya_ygrt") 544 545 We use a segment tree to solve this problem. For each node, it is sufficient to store two arrays : *sum*[*i*], denoting the total contribution of the digit *i* in the current segment (if a digit is in the tens digit then it contributes 10 to the sum and etc...), and also *nxt*[*i*], what all the digits *i* in the current segment are changed to. 546 547 Maintaining these arrays is quite straightforward with lazy propogation. When we push an update down a node, we need to update the nxt array of the children. First, we change *st*[*id*].*nxt*[*u*] to *v*, where the current update is to change all digits *u* to *v*. Then, we change *st*[*id* * 2].*nxt*[*i*] to *st*[*id*].*nxt*[*st*[*id* * 2].*nxt*[*i*]], where *st*[*id*] is the current node and *st*[*id* * 2] is one of the children nodes. (Do the same for the right children). You can see the code if you need more details. Finally, update the sum array of the current segment. 548 549 The total complexity of the code is , which is fast enough. 550 551 **Code** 552 553 ``` 554 #include <bits/stdc++.h> 555 #include <ext/pb_ds/assoc_container.hpp> 556 #include <ext/pb_ds/tree_policy.hpp> 557 558 using namespace std; 559 using namespace __gnu_pbds; 560 561 #define fi first 562 #define se second 563 #define mp make_pair 564 #define pb push_back 565 #define fbo find_by_order 566 #define ook order_of_key 567 568 typedef long long ll; 569 typedef pair<ll,ll> ii; 570 typedef vector<int> vi; 571 typedef long double ld; 572 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 573 typedef set<int>::iterator sit; 574 typedef map<int,int>::iterator mit; 575 typedef vector<int>::iterator vit; 576 const int N = 100000; 577 int a[N+1][10]; 578 579 struct node 580 { 581 int nxt[10]; 582 ll sum[10]; 583 }; 584 585 node st[N*4+1]; 586 587 void combine(int id) 588 { 589 for(int i = 0; i < 10; i++) 590 { 591 st[id].sum[i]=st[id*2].sum[i]+st[id*2+1].sum[i]; 592 } 593 } 594 595 void build(int id, int l, int r) 596 { 597 if(r-l<2) 598 { 599 for(int i = 0; i < 10; i++) st[id].sum[i]=a[l][i]; 600 for(int i = 0; i < 10; i++) 601 { 602 st[id].nxt[i] = i; 603 } 604 return ; 605 } 606 for(int i = 0; i < 10; i++) 607 { 608 st[id].nxt[i] = i; 609 } 610 int mid=(l+r)>>1; 611 build(id*2,l,mid); 612 build(id*2+1,mid,r); 613 combine(id); 614 } 615 616 int nxt1[10]; 617 int nxt2[10]; 618 ll sum[10]; 619 620 void push(int id, int l, int r) 621 { 622 memset(sum,0,sizeof(sum)); 623 if(r-l>=2) 624 { 625 for(int i = 0; i < 10; i++) 626 { 627 nxt1[i] = st[id].nxt[st[id*2].nxt[i]]; 628 nxt2[i] = st[id].nxt[st[id*2+1].nxt[i]]; 629 } 630 for(int i=0;i<10;i++) 631 { 632 st[id*2].nxt[i]=nxt1[i]; 633 st[id*2+1].nxt[i]=nxt2[i]; 634 } 635 } 636 for(int i=0;i<10;i++) 637 { 638 sum[st[id].nxt[i]]+=st[id].sum[i]; 639 } 640 for(int i=0;i<10;i++) 641 { 642 st[id].sum[i]=sum[i]; 643 st[id].nxt[i]=i; 644 } 645 } 646 647 void update(int id, int l, int r, int ql, int qr, int u, int v) 648 { 649 push(id,l,r); 650 if(ql>=r||l>=qr) return ; 651 if(ql<=l&&r<=qr) 652 { 653 st[id].nxt[u]=v; 654 push(id,l,r); 655 return ; 656 } 657 int mid=(l+r)>>1; 658 update(id*2,l,mid,ql,qr,u,v); 659 update(id*2+1,mid,r,ql,qr,u,v); 660 combine(id); 661 } 662 663 ll query(int id, int l, int r, int ql, int qr) 664 { 665 push(id,l,r); 666 if(ql>=r||l>=qr) return 0; 667 if(ql<=l&&r<=qr) 668 { 669 ll sum=0; 670 for(int i=1;i<10;i++) 671 { 672 sum+=ll(i)*st[id].sum[i]; 673 } 674 return sum; 675 } 676 int mid=(l+r)>>1; 677 return (query(id*2,l,mid,ql,qr)+query(id*2+1,mid,r,ql,qr)); 678 } 679 680 int main() 681 { 682 ios_base::sync_with_stdio(0); cin.tie(0); 683 int n, q; cin>>n>>q; 684 for(int i = 0; i < n; i++) 685 { 686 int x; cin>>x; 687 int cur=1; 688 for(int j = 0; j < 9; j++) 689 { 690 a[i][x%10] += cur; 691 x/=10; 692 cur*=10; 693 if(x==0) break; 694 } 695 } 696 build(1,0,n); 697 for(int i = 0; i < q; i++) 698 { 699 int type; 700 cin>>type; 701 if(type==1) 702 { 703 int l,r,u,v; 704 cin>>l>>r>>u>>v; 705 l--; r--; 706 update(1,0,n,l,r+1,u,v); 707 } 708 else 709 { 710 int l,r; cin>>l>>r; 711 l--; r--; 712 ll sum = query(1,0,n,l,r+1); 713 cout<<sum<<'\n'; 714 } 715 } 716 } 717 ``` 718 719 **Replace All** 720 721 Author : [zscoder](/profile/zscoder "Гроссмейстер zscoder") 722 723 First, we solve the problem when there're no question marks, i.e. we find a way to calculate the number of good pairs of strings fast for a constant pair of strings *A* and *B*. 724 725 Call a pair of strings (*S*, *T*) where |*S*| ≤ |*T*| coprime if *S* = *T* or *S* is a prefix of *T*, and if *T* = *S* + *X*, then (*X*, *S*) is also coprime. (*S*, *T*) where |*S*| > |*T*| is coprime iff (*T*, *S*) is coprime. 726 727 If *A* = *B*, then all possible strings work. Thus, we assume *A* ≠ *B* from now on. We remove the longest common prefix of *A* and *B*. Thus, we can assume *A*[0] ≠ *B*[0]. Thus, either *S* is a prefix of *T* or *T* is a prefix of *S*. WLOG, *S* is a prefix of *T*. Let *T* = *S* + *X*. Now, *A* and *B* consists of only *S* and *X*. Using this, we can prove by induction on |*S*| + |*T*| that *S* and *T* must be coprime. 728 729 One important property of coprime strings is that *S* + *T* = *T* + *S* holds. (again induction works here) 730 731 Now, since the strings *S* and *T* needs to be coprime, we have *S* + *T* = *T* + *S*. This allows us to swap any neighbouring Ss and Ts (or 'A's and 'B's) in *A* and *B*, as the resulting strings will still be equal. Thus, swapping repeatedly allows us to sort the strings A and B. (the 'A's appear in front and 'B's appear at the back) Let *x**A*, *x**B*, *y**A*, *y**B* denote the number of As and Bs in the first string and second string respectively. If (*x**A*, *x**B*) > (*y**A*, *y**B*), then the answer is 0. We'll handle the case (*x**A*, *x**B*) = (*y**A*, *y**B*) later. Now, assume *x**A* > *y**A*, *x**B* < *y**B*. Thus, we have to solve the equation (*x**A* - *y**A*) copies of *S* = (*y**B* - *x**B*) copies of *T*. 732 733 Now, let *x* = *x**A* - *y**A*, *y* = *y**B* - *x**B*. If *x* = *y*, then the solution is *S* = *T*. Otherwise, assume *x* > *y*. Then, |*S*| < |*T*|. So, by comparing, we again have *T* = *S* + *X*, for some nonempty binary string *X*. Note that *S* and *X* must be coprime too, so we can sort the second string as well. We cancel off the Ss on both sides to get (*x* - *y*)*S* = *yX*. Thus, this means that if (*S*, *T*) is a solution for (*x*, *y*), then (*S*, *X*) is a solution for (*x* - *y*, *y*). Note that repeating this process will eventually lead us to (1, 1). (this process is similar to Euclidean Algorithm) 734 735 The answer for (1, 1) is the number of solutions to *S* = *T*. Let's denote the solution here as *X*. Doing some backtracking, we realize that the answer for (*x*, *y*) is equal to (X....X (*y* times), X...X (*x* times)). Note that we still have the condition |*S*|, |*T*| ≤ *N*, so we can translate this to an appropriate condition on the length of *X* and the answer is simply the number of binary strings of length not exceeding the maximum possible length of *X*. 736 737 The only case that remains is that (*x**A*, *x**B*) = (*y**A*, *y**B*). In this case, any pair of coprime strings *S* and *T* will work. Thus, our task reduces to calculating the number of coprime pair of strings with length not exceeding *N*. 738 739 We claim that the number of coprime pair of strings (*S*, *T*) with |*S*| = *p*, |*T*| = *q* is . 740 741 If *p* = *q* the claim is obviously true. Otherwise, we can induct on *p* + *q* agin. If *q* > *p*, we can write *T* = *S* + *X* and then the number of coprime pairs of (*S*, *T*) is equal to the number of coprime pairs of (*S*, *X*), which by induction is equal to . This proves the claim. 742 743 Thus, we just need to compute the sum of  for all 1 ≤ *p*, *q* ≤ *N*. 744 745 Indeed, since *N* ≤ 3·105, it is enough to count the number of pairs (*p*, *q*) with *gcd* = *g* for all *g*. 746 747 However, this is quite easy. Let *cnt*[*i*] denote the number of pairs (*p*, *q*) such that *p* and *q* are both divisible by *i*. Let *ans*[*i*] denote the number of pairs (*p*, *q*) with *gcd* = *i*. Then, . Thus, this can be computed in . 748 749 Now, we need to find out how to calculate the sum of all these values on two strings *X* and *Y* with question marks. Handle the case when the two strings become equal separately. 750 751 Let's first make a summary of the number of good pairs of strings for constant strings *A* and *B*. In fact, note that the formulaes above only depends on (*d**A*, *d**B*), the difference between the number of As in *A* and *B*, and the difference between the number of Bs in *A* and *B* (note that *d**A*, *d**B* can be negative) 752 753 If *d**A* = *d**B* = 0, then the answer is the sum of  for all 1 ≤ *p*, *q* ≤ *N*, which as we have just saw can be precomputed in time. 754 755 Otherwise, if *d**A*, *d**B* ≥ 0 or *d**A*, *d**B* ≤ 0, then there are no good pair of strings. 756 757 Finally, in other cases, let *p* = |*d**A*|, *q* = |*d**B*|. Then, the answer is . 758 759 This also means that we can compute the answer if we know *d**A* and *d**B* very fast. (worst case is ) 760 761 Now, suppose in the strings *X* and *Y*, we have *a* and *b* question marks respectively. Additionally, suppose the current difference between the number of As and Bs of these strings is (*p*, *q*). 762 763 If we choose *x* and *y* of the question marks from *X* and *Y* to be replaced with As, then the difference between As and Bs in the strings become (*p* + *x* - *y*, *q* + (*a* - *b*) - (*x* - *y*)). Let's denote *q* as *q* + *a* - *b* for simplicity. Thus, the difference is now written as (*p* + (*x* - *y*), *q* - (*x* - *y*)). The values of *x* and *y* can be any integer in the range [0, *a*] and [0, *b*] respectively. Suppose for all - *b* ≤ *d* ≤ *a*, we know how many ways to assign the question marks have *x* - *y* = *d*. Then, we can iterate through all the *d*s one by one and compute the answer fast for each *d*. 764 765 Thus, the final hurdle is to calculate the number of ways to obtain *x* - *y* = *d* for all possible *d* so that 0 ≤ *x* ≤ *a*, 0 ≤ *y* ≤ *b*. This is just the sum of  for all 0 ≤ *x* ≤ *a*. However, this is equal to , as the number of ways to choose *b* + *d* objects from *a* + *b* objects is the same as the sum of the product of the number of ways to choose *x* objects from the first *a* objects and the number of ways to choose *b* + *d* - *x* objects from the first *b* objects for all 0 ≤ *a* ≤ *x*. Thus, this value can be computed in *O*(1) with precomputed factorials and inverse factorials (or you can maintain this value when we iterate through all *d*). 766 767 Finally, don't forget to take care of the cases where it is possible for both strings to be equal. 768 769 The time complexity of the solution is . 770 771 **Code** 772 773 ``` 774 #include <bits/stdc++.h> 775 #include <ext/pb_ds/assoc_container.hpp> 776 #include <ext/pb_ds/tree_policy.hpp> 777 778 using namespace std; 779 using namespace __gnu_pbds; 780 781 #define fi first 782 #define se second 783 #define mp make_pair 784 #define pb push_back 785 #define fbo find_by_order 786 #define ook order_of_key 787 788 typedef long long ll; 789 typedef pair<ll,ll> ii; 790 typedef vector<ll> vi; 791 typedef long double ld; 792 typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; 793 typedef set<int>::iterator sit; 794 typedef map<int,int>::iterator mit; 795 typedef vector<int>::iterator vit; 796 797 const int MOD = 1e9 + 7; 798 799 struct NumberTheory 800 { 801 vector<ll> primes; 802 vector<bool> prime; 803 vector<ll> totient; 804 vector<ll> sumdiv; 805 vector<ll> bigdiv; 806 void Sieve(ll n) 807 { 808 prime.assign(n+1, 1); 809 prime[1] = false; 810 for(ll i = 2; i <= n; i++) 811 { 812 if(prime[i]) 813 { 814 primes.pb(i); 815 for(ll j = i*2; j <= n; j += i) 816 { 817 prime[j] = false; 818 } 819 } 820 } 821 } 822 823 ll phi(ll x) 824 { 825 map<ll,ll> pf; 826 ll num = 1; ll num2 = x; 827 for(ll i = 0; primes[i]*primes[i] <= x; i++) 828 { 829 if(x%primes[i]==0) 830 { 831 num2/=primes[i]; 832 num*=(primes[i]-1); 833 } 834 while(x%primes[i]==0) 835 { 836 x/=primes[i]; 837 pf[primes[i]]++; 838 } 839 } 840 if(x>1) 841 { 842 pf[x]++; num2/=x; num*=(x-1); 843 } 844 x = 1; 845 num*=num2; 846 return num; 847 } 848 849 bool isprime(ll x) 850 { 851 if(x==1) return false; 852 for(ll i = 0; primes[i]*primes[i] <= x; i++) 853 { 854 if(x%primes[i]==0) return false; 855 } 856 return true; 857 } 858 859 void SievePhi(ll n) 860 { 861 totient.resize(n+1); 862 for (int i = 1; i <= n; ++i) totient[i] = i; 863 for (int i = 2; i <= n; ++i) 864 { 865 if (totient[i] == i) 866 { 867 for (int j = i; j <= n; j += i) 868 { 869 totient[j] -= totient[j] / i; 870 } 871 } 872 } 873 } 874 875 void SieveSumDiv(ll n) 876 { 877 sumdiv.resize(n+1); 878 for(int i = 1; i <= n; ++i) 879 { 880 for(int j = i; j <= n; j += i) 881 { 882 sumdiv[j] += i; 883 } 884 } 885 } 886 887 ll getPhi(ll n) 888 { 889 return totient[n]; 890 } 891 892 ll getSumDiv(ll n) 893 { 894 return sumdiv[n]; 895 } 896 897 ll modpow(ll a, ll b, ll mod) 898 { 899 ll r = 1; 900 if(b < 0) b += mod*100000LL; 901 while(b) 902 { 903 if(b&1) r = (r*a)%mod; 904 a = (a*a)%mod; 905 b>>=1; 906 } 907 return r; 908 } 909 910 ll inv(ll a, ll mod) 911 { 912 return modpow(a, mod - 2, mod); 913 } 914 915 ll invgeneral(ll a, ll mod) 916 { 917 ll ph = phi(mod); 918 ph--; 919 return modpow(a, ph, mod); 920 } 921 922 void getpf(vector<ii>& pf, ll n) 923 { 924 for(ll i = 0; primes[i]*primes[i] <= n; i++) 925 { 926 int cnt = 0; 927 while(n%primes[i]==0) 928 { 929 n/=primes[i]; cnt++; 930 } 931 if(cnt>0) pf.pb(ii(primes[i], cnt)); 932 } 933 if(n>1) 934 { 935 pf.pb(ii(n, 1)); 936 } 937 } 938 939 //ll op; 940 void getDiv(vector<ll>& div, vector<ii>& pf, ll n, int i) 941 { 942 //op++; 943 ll x, k; 944 if(i >= pf.size()) return ; 945 x = n; 946 for(k = 0; k <= pf[i].se; k++) 947 { 948 if(i==int(pf.size())-1) div.pb(x); 949 getDiv(div, pf, x, i + 1); 950 x *= pf[i].fi; 951 } 952 } 953 }; 954 955 NumberTheory nt; 956 957 ll modpow(ll a, ll b) 958 { 959 ll r = 1; 960 while(b) 961 { 962 if(b&1) r=(r*a)%MOD; 963 a=(a*a)%MOD; 964 b>>=1; 965 } 966 return r; 967 } 968 969 ll inv(ll a) 970 { 971 return modpow(a,MOD-2); 972 } 973 974 ll n; 975 ll cnt[300001]; 976 ll mob[300001]; 977 978 ll mobius(ll x) 979 { 980 int cc = 0; 981 for(int i=0;nt.primes[i]*nt.primes[i]<=x;i++) 982 { 983 int z=0; 984 while(x%nt.primes[i]==0) 985 { 986 z++; 987 x/=nt.primes[i]; 988 } 989 if(z>=2) return 0; 990 if(z>0) cc++; 991 } 992 if(x>1) cc++; 993 if(cc&1) return -1; 994 else return 1; 995 } 996 997 ll solve(ll x, ll y) 998 { 999 if(x==0&&y==0) 1000 { 1001 for(int i=1;i<=n;i++) 1002 { 1003 cnt[i]=ll(n/i)*ll(n/i); 1004 } 1005 for(int i=1;i<=n;i++) 1006 { 1007 for(int j=2*i;j<=n;j+=i) 1008 { 1009 cnt[i]+=mob[j/i]*cnt[j]; 1010 } 1011 } 1012 ll ans = 0; 1013 ll cur = 2; 1014 for(int i=1;i<=n;i++) 1015 { 1016 cnt[i]%=MOD; 1017 if(cnt[i]<0) cnt[i]+=MOD; 1018 //cerr<<i<<' '<<cnt[i]<<'\n'; 1019 ans=(ans+(cur*cnt[i])%MOD)%MOD; 1020 if(ans<0) ans+=MOD; 1021 cur=(cur*2)%MOD; 1022 if(cur<0) cur+=MOD; 1023 } 1024 return ans; 1025 } 1026 else if(x>=0&&y>=0) 1027 { 1028 return 0; 1029 } 1030 else if(x<=0&&y<=0) 1031 { 1032 return 0; 1033 } 1034 else 1035 { 1036 x=abs(x); y=abs(y); 1037 ll g = __gcd(x,y); 1038 x/=g; y/=g; 1039 ll k = n/max(x,y); 1040 ll ans = modpow(2,k+1)+MOD-2; 1041 while(ans>=MOD) ans-=MOD; 1042 return ans; 1043 } 1044 } 1045 1046 ll fact[600001]; 1047 ll ifact[600001]; 1048 ll inverse[600001]; 1049 1050 ll choose(ll n, ll r) 1051 { 1052 if(r==0) return 1; 1053 ll ans = fact[n]; 1054 ans=(ans*ifact[r])%MOD; 1055 ans=(ans*ifact[n-r])%MOD; 1056 if(ans<0) ans+=MOD; 1057 return ans; 1058 } 1059 1060 int main() 1061 { 1062 ios_base::sync_with_stdio(0); cin.tie(0); 1063 string s, t; 1064 cin>>s>>t; 1065 cin>>n; 1066 fact[0]=1; ifact[0]=1; 1067 for(int i=1;i<=600000;i++) 1068 { 1069 fact[i]=(fact[i-1]*i)%MOD; 1070 if(fact[i]<0) fact[i]+=MOD; 1071 ifact[i]=inv(fact[i]); 1072 inverse[i]=inv(i); 1073 } 1074 nt.Sieve(300001); 1075 for(int i=2;i<=n;i++) 1076 { 1077 mob[i]=mobius(i); 1078 } 1079 ll sa, sb, sc; //sa = # of As in s, sb = # of Bs in s, sc = # of ?s in s 1080 ll ta, tb, tc; 1081 sa=sb=sc=ta=tb=tc=0; 1082 ll same = 1; //number of ways to fill in ?s such that |S| = |T| 1083 if(s.length()!=t.length()) same=0; 1084 else 1085 { 1086 for(int i=0;i<s.length();i++) 1087 { 1088 if(s[i]=='?'&&t[i]=='?') same=(same*2)%MOD; 1089 else if(s[i]=='?'||t[i]=='?') 1090 { 1091 1092 } 1093 else if(s[i]==t[i]) 1094 { 1095 1096 } 1097 else 1098 { 1099 same=0; 1100 } 1101 } 1102 } 1103 for(int i=0;i<s.length();i++) 1104 { 1105 if(s[i]=='A') sa++; 1106 else if(s[i]=='B') sb++; 1107 else sc++; 1108 } 1109 for(int i=0;i<t.length();i++) 1110 { 1111 if(t[i]=='A') ta++; 1112 else if(t[i]=='B') tb++; 1113 else tc++; 1114 } 1115 ll ans = 0; 1116 ll c = 1; 1117 int cntt=0; 1118 for(ll i = sa - ta - tc; i <= sa - ta + sc; i++) 1119 { 1120 if(i==0) 1121 { 1122 ll cc = (c-same)%MOD; 1123 if(cc<0) cc+=MOD; 1124 ans=(ans+(cc*solve(i,sa+sb+sc-ta-tb-tc-i))%MOD)%MOD; 1125 ll tmp = modpow(2,n+1)+MOD-2; 1126 while(tmp>=MOD) tmp-=MOD; 1127 tmp=(tmp*tmp)%MOD; 1128 ans=(ans+(same*tmp)%MOD)%MOD; 1129 } 1130 else 1131 { 1132 ans=(ans+(c*solve(i,sa+sb+sc-ta-tb-tc-i))%MOD)%MOD; 1133 } 1134 if(ans<0) ans+=MOD; 1135 c=(c*inverse[cntt+1])%MOD; 1136 c=(c*(sc+tc-cntt))%MOD; 1137 if(c<0) c+=MOD; 1138 cntt++; 1139 } 1140 cout<<ans<<'\n'; 1141 } 1142 ```