804.md (33548B)
1 Source: https://codeforces.com/blog/entry/51846 2 3 We were waiting several weeks to setting this contest and hope the problem was good enough. 4 5 #### Events 6 7 There was a difficulty with [805E - Ice cream coloring](/contest/805/problem/E "Codeforces Round 411 (Div. 2)")/[804C - Ice cream coloring](/contest/804/problem/C "Codeforces Round 411 (Div. 1)"). A little bug in the checker fortunately yields accepting an incorrect solution of only one person during the contest. I should apologize all of you because of this. 8 9 For this sentence, `Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph.` You can find the meaning of "connected subgraph" with [connected](http://mathworld.wolfram.com/ConnectedGraph.html) and [subgraph](http://www.edmath.org/MATtours/discrete/concepts/csubgr.html), thus it can be empty as it is more logical. How ever, I should apologize all of the participants because of weak sample tests in the statement. 10 11 I will write the full editorial in the few next days, now some hints and short solutions exist here. 12 13 ## Hints 14 15 [805A - Fake NP](/contest/805/problem/A "Codeforces Round 411 (Div. 2)") 16 17 **hint1** 18 19 Almost half of numbers are divisible by two. 20 21 [805B - 3-palindrome](/contest/805/problem/B "Codeforces Round 411 (Div. 2)") 22 23 **hint1** 24 25 For the string shouldn't be any *i* ≤ *n* - 2, *s**i* = *s**i* + 2. Make some examples of little sizes. 26 27 [805C - Find Amir](/contest/805/problem/C "Codeforces Round 411 (Div. 2)") / [804A - Find Amir](/contest/804/problem/A "Codeforces Round 411 (Div. 1)") 28 29 **hint1** 30 31 Find minimum weighted edges. 32 33 **hint2** 34 35 There is some edges with weight 0, try to connect them in a carefully way. 36 37 [805D - Minimum number of steps](/contest/805/problem/D "Codeforces Round 411 (Div. 2)") / [804B - Minimum number of steps](/contest/804/problem/B "Codeforces Round 411 (Div. 1)") 38 39 **hint1** 40 41 The last situation is some '*a*' characters after some '*b*' ones. 42 43 **hint2** 44 45 The last situation is unique. 46 47 **hint3** 48 49 The number of steps is also unique. 50 51 **hint4** 52 53 Each '*b*' character makes a number of '*b*' characters in the last situation according to the number of '*a*' characters before it. 54 55 [805E - Ice cream coloring](/contest/805/problem/E "Codeforces Round 411 (Div. 2)") / [804C - Ice cream coloring](/contest/804/problem/C "Codeforces Round 411 (Div. 1)") 56 57 **hint1** 58 59 We want to color the ice creams in a way that all of ice creams in a vertex would be different with this condition that if two vertices *u* and *v* have ice cream *i*, then all of vertices in the unique path of *u* and *v* would have it. 60 61 **hint2** 62 63 Let's have a trivial lower-bound for the answer. 64 65 **answer** 66 67 The trivial lower-bound should be maximum size of vertices' sets. 68 69 **hint3** 70 71 You can prove that by induction on leaves of the tree. And code it how you proved it. 72 73 [805F - Expected diameter of a tree](/contest/805/problem/F "Codeforces Round 411 (Div. 2)") / [804D - Expected diameter of a tree](/contest/804/problem/D "Codeforces Round 411 (Div. 1)") 74 75 **hint1** 76 77 Let's solve the problem for just two tree. 78 79 **Trivail solution** 80 81 *d**t* is diameter of *t*-th tree and *f**i* is the maximum path starting from vertex *i*, for all valid *i* and *j*, assume that the edge is between them and find the diameter with *max*(*f**i* + *f**j* + 1, *max*(*d*1, *d*2)). 82 83 consider this trivial  solution and try to improve it to . 84 85 **hint2** 86 87  88 89 **Actually** 90 91 seems SQRT. 92 93 **How?** 94 95 For every new query, try to do it with the complexity of  , which *sz**i* means size of the components of *i*-th vertex. Prove its complexity is . 96 97 [804E - The same permutation](/contest/804/problem/E "Codeforces Round 411 (Div. 1)") 98 99 **hint1** 100 101 You can prove, we need even number of swaps to reach the same permutation. So  and the answer for 4·*k* + 3 and 4·*k* + 4 is -1. 102 103 **hint2** 104 105 The solution almost is constructive. 106 107 **Try to solve it for n = 4** 108 109 And then solve *n* = 8 by *n* = 4. 110 111 **hint3** 112 113 Let's partition *n* = 4·*k* numbers to classes, each class contains a 4 consecutive numbers. And when *n* = 4·*k* + 1 there is a class with 5 consecutive numbers. 114 115 [804F - Fake bullions](/contest/804/problem/F "Codeforces Round 411 (Div. 1)") 116 117 **hint1** 118 119 The problem consists two parts, the first part is to find *mn**i* and *mx**i*, the minimum and the maximum score *i*-th vertex may get after the score distribution. The second part is to finding the answer and all your need to solve this part is those two arrays. It is trivial *mn**i* is number of real bullion of golds in *i*-th vertex. 120 121 **hint2** 122 123 Let's find the scores for two vertices *u* and *v*, *u* have a directed edge to *v*. 124 125 **u -> v** 126 127  128 129 If *i*-th element from *u*-th vertex was painted and *j*-th element from *v*-th vertex was unpainted such that  then *j*-th element from *v*-th vertex will be painted quickly. For two vertex, we can do it in complexity . 130 131 **hint3** 132 133 If we have this directed walk {*w*1, *w*2, ..., *w**k*}, you should affect *v*1 on *v**k* how I said in the previous hint with . 134 135 **What about strogly connected components.** 136 137  138 139 In this components if *i*-th element from *u*-th vertex was painted then for all of *j* such that , *j*-th element from all vertices will be painted quickly. For this components, we can do it with complexity . In the main problem, we can suppose all of a strongly conected component a vertex with size *g* in this way and we can calculate *mx**i* with answer of its component's vertex multiplied by . 140 141 **hint4** 142 143 SCC of the tournament yields a Hamiltonian path of strongly connected components( if we consider each component a vertex ). The problem decreased to solve this path. we can solve the path with the complexity of sum of vertices' sizes. 144 145 **hint5** 146 147 Now, for every vertex we have minimum and maximum score it may get. For B known vertices, to check if they can be the wanted set, we can assume their score be maximum possible and the other scores be minimum possible. If they were top, then they can be a sample of the wanted set. 148 149 **hint6** 150 151 Consider a sorted sequence of combination of two array *mn* and *mx*. 152 153 For every vertex, consider the number of ways it(with its maximum score) can be the minimum score of the set of B vertices. 154 155 # Solutions 156 157 Tutorial is loading... 158 159 From: [saliii](/profile/saliii "Candidate Master saliii"), Writer: [saliii](/profile/saliii "Candidate Master saliii") 160 161 Time Complexity:  162 163 Memory complexity:  164 165 **python3** 166 167 ``` 168 l,r=list(map(int,input().split())) 169 print(2 if l<r else l) 170 ``` 171 172 **C++** 173 174 ``` 175 int main(){ 176 int l, r; 177 scanf("%d%d", &l, &r); 178 printf("%d", l == r ? l : 2); 179 } 180 ``` 181 182 Tutorial is loading... 183 184 From: [saliii](/profile/saliii "Candidate Master saliii"), Writer: [saliii](/profile/saliii "Candidate Master saliii") 185 186 Time Complexity:  187 188 Time Complexity:  189 190 Memory complexity:  191 192 **python3** 193 194 ``` 195 print(("aabb" * 50000)[:int(input())]) 196 ``` 197 198 **C++** 199 200 ``` 201 int N; 202 int main() 203 { 204 scanf("%d", &N); 205 for (int i = 0; i < N; i++) 206 putchar(i & 2 ? 'b' : 'a'); 207 puts(""); 208 } 209 ``` 210 211 Tutorial is loading... 212 213 From: [saliii](/profile/saliii "Candidate Master saliii"), Writer: [saliii](/profile/saliii "Candidate Master saliii") 214 215 Time Complexity:  216 217 Time Complexity:  218 219 Memory complexity:  220 221 **python3** 222 223 ``` 224 print((int(input())-1)//2) 225 ``` 226 227 **C++** 228 229 ``` 230 int main(){ 231 int n; 232 scanf("%d", &n); 233 printf("%d\n", (n-1)/2); 234 } 235 ``` 236 237 Tutorial is loading... 238 239 From: [MohammadJA](/profile/MohammadJA "Candidate Master MohammadJA"), Writer: [MohammadJA](/profile/MohammadJA "Candidate Master MohammadJA") 240 241 Time Complexity:  242 243 Time Complexity:  244 245 Memory complexity:  246 247 **python3** 248 249 ``` 250 s = input() 251 cnt = 0 252 m=10**9 + 7 253 t = 0 254 255 for i in range(len(s)): 256 if s[~i] == 'a': 257 cnt = (cnt+t)%m 258 t = (t*2)%m 259 else: 260 t += 1 261 print(cnt) 262 ``` 263 264 **C++** 265 266 ``` 267 int c,d,i,n,m,k,x,j=1000000007; 268 string s; 269 main(){ 270 cin>>s; 271 for(i=s.size()-1;i>=0;i--){ 272 if(s[i]=='b')c++;else{ 273 k+=c;c*=2;k%=j;c%=j; 274 } 275 } 276 cout<<k; 277 } 278 ``` 279 280 Tutorial is loading... 281 282 From: [saliii](/profile/saliii "Candidate Master saliii"), Writer: [saliii](/profile/saliii "Candidate Master saliii") 283 284 Time Complexity:  285 286 Memory complexity:  287 288 **C++** 289 290 ``` 291 // +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+ \\ 292 293 int const N = 3e5 + 10 ; 294 int n , m , ans = 1 , res[N] ; 295 vector <int> g[N] , vec[N] ; 296 297 inline bool cmp (int a , int b) { 298 return res[a] < res[b] ; 299 } 300 301 void dfs (int v , int par = -1) { 302 int col = ans , p = (int)vec[v].size() - 1 ; 303 304 sort(vec[v].begin() , vec[v].end() , cmp) ; 305 306 for (int x : vec[v]) { 307 if (res[x]) { 308 continue ; 309 } 310 311 while (p >= 0 && col == res[vec[v][p]]) { 312 col -- ; 313 p -- ; 314 } 315 316 res[x] = col ; 317 col -- ; 318 319 } 320 321 for (int u : g[v]) { 322 if (u != par) { 323 dfs(u , v) ; 324 } 325 } 326 } 327 328 int main(){ 329 ios::sync_with_stdio(false) , cin.tie(0) , cout.tie(0) ; 330 331 cin >> n >> m ; 332 333 for (int i = 0 ; i < n ; i ++) { 334 int sz ; 335 cin >> sz ; 336 337 ans = max(ans , sz) ; 338 339 while (sz --) { 340 int x ; 341 cin >> x ; 342 x -- ; 343 vec[i].push_back(x) ; 344 } 345 } 346 347 for (int i = 0 ; i < n - 1 ; i ++) { 348 int u , v ; 349 cin >> u >> v ; 350 u -- , v -- ; 351 352 g[u].push_back(v) ; 353 g[v].push_back(u) ; 354 } 355 356 dfs(0) ; 357 358 cout << ans << '\n' ; 359 360 for (int i = 0 ; i < m ; i ++) { 361 cout << max(res[i] , 1) << ' ' ; 362 } 363 cout << '\n' ; 364 } 365 ``` 366 367 Time Complexity:  368 369 Memory complexity:  370 371 **C++** 372 373 ``` 374 vector <int> Vs[300050]; 375 vector <int> conn[300050]; 376 377 int ans[300050]; 378 bool chk[500050]; 379 bool dchk[300050]; 380 vector <int> Vu; 381 void DFS(int n) { 382 dchk[n] = true; 383 384 for (auto it : Vs[n]) { 385 if (ans[it]) chk[ans[it]] = true; 386 else Vu.push_back(it); 387 } 388 389 int a = 1; 390 for (auto it : Vu) { 391 while (chk[a]) a++; 392 ans[it] = a++; 393 } 394 for (auto it : Vs[n]) chk[ans[it]] = false; 395 Vu.clear(); 396 397 for (auto it : conn[n]) { 398 if (dchk[it]) continue; 399 DFS(it); 400 } 401 } 402 int main() { 403 int N, M, i; 404 scanf("%d %d", &N, &M); 405 for (i = 1; i <= N; i++) { 406 int t1, t2; 407 scanf("%d", &t1); 408 while (t1--) { 409 scanf("%d", &t2); 410 Vs[i].push_back(t2); 411 } 412 } 413 for (i = 1; i < N; i++) { 414 int t1, t2; 415 scanf("%d %d", &t1, &t2); 416 conn[t1].push_back(t2); 417 conn[t2].push_back(t1); 418 } 419 DFS(1); 420 421 int mx = 0; 422 for (i = 1; i <= M; i++) { 423 mx = max(mx, ans[i]); 424 if (ans[i] == 0) ans[i] = 1; 425 } 426 mx = max(mx, 1); 427 printf("%d\n", mx); 428 for (i = 1; i <= M; i++) printf("%d ", ans[i]); 429 430 return !printf("\n"); 431 } 432 ``` 433 434 Tutorial is loading... 435 436 From: [MohammadJA](/profile/MohammadJA "Candidate Master MohammadJA"), Writer: [MohammadJA](/profile/MohammadJA "Candidate Master MohammadJA") 437 438 Time Complexity:  439 440 Memory complexity:  441 442 **C++** 443 444 ``` 445 using namespace std ; 446 447 #define int long long 448 449 const int MAXN = 1e5 + 100 ; 450 451 vector<int>ver[MAXN] , com[MAXN] , ps[MAXN] ; 452 int vis[MAXN] , dis[MAXN] ; 453 int mxr , mxid ; 454 void dfs(int v , int col = -1 , int h = 0 , int par = -1){ 455 vis[v] = max(vis[v] , col) ; 456 if(mxr < h)mxid = v , mxr = h ; 457 dis[v] = max(h , dis[v]) ; 458 if(col > 0)com[col] . push_back(dis[v]) ; 459 for(auto u : ver[v]){ 460 if(u == par)continue ; 461 dfs(u , col , h + 1 , v) ; 462 } 463 } 464 map<pair<int , int> , int> check ; 465 int32_t main(){ 466 ios_base::sync_with_stdio(0) ; 467 cin . tie(0) ; cout . tie(0) ; 468 int n , m , q ; cin >> n >> m >> q ; 469 for(int i = 0 ; i < m ; i ++){ 470 int x , y ; cin >> x >> y ; 471 x -- , y -- ; 472 ver[x] . push_back(y) ; 473 ver[y] . push_back(x) ; 474 } 475 int cnt = 0 ; 476 for(int i = 0 ; i < n ; i ++){ 477 if(vis[i])continue ; 478 mxr = 0 , mxid = i ; 479 dfs(i) ; 480 mxr = 0 ; 481 dfs(mxid) ; 482 dfs(mxid , ++ cnt) ; sort(com[cnt] . begin() , com[cnt] . end()) ; 483 ps[cnt] . push_back(0) ; 484 for(auto v : com[cnt])ps[cnt] . push_back(ps[cnt] . back() + v) ; 485 } 486 cout << fixed << setprecision(10) ; 487 while(q --){ 488 int x , y ; cin >> x >> y ; 489 x -- , y -- ; x = vis[x] ; y = vis[y] ; 490 if(com[x] . size() > com[y] . size())swap(x , y) ; 491 if(x == y){cout << -1 << '\n' ; continue ; } 492 if(check[{x , y}] > 0){cout << double(check[{x , y}]) / (1ll * com[x] . size() * com[y] . size()) << '\n' ; continue ; } 493 int ans = 0 , mxd = max(com[x] . back() , com[y] . back()) ; 494 for(auto v : com[x]){ 495 int num = lower_bound(com[y] . begin() , com[y] . end() , mxd - v - 1) - com[y] . begin() ; 496 ans += num * mxd + (com[y] . size() - num) * (v + 1) + ps[y] . back() - ps[y][num] ; 497 } 498 check[{x , y}] = ans ; 499 cout << double(check[{x , y}]) / (1ll * com[x] . size() * com[y] . size()) << '\n' ; 500 } 501 } 502 ``` 503 504 Tutorial is loading... 505 506 From: [saliii](/profile/saliii "Candidate Master saliii"), Writer: [saliii](/profile/saliii "Candidate Master saliii") 507 508 Time Complexity:  509 510 Memory complexity:  511 512 **C++** 513 514 ``` 515 int n; 516 517 int main() 518 { 519 scanf("%d",&n); 520 if(n%4>1)return printf("NO\n"),0; 521 printf("YES\n"); 522 for(int i=1;i<n;i+=4) 523 { 524 if(n%4)printf("%d %d\n%d %d\n%d %d\n",i+2,n,i+2,i+3,i+3,n); 525 else printf("%d %d\n",i+2,i+3); 526 printf("%d %d\n",i,i+2); 527 printf("%d %d\n",i+1,i+3); 528 printf("%d %d\n",i+1,i+2); 529 printf("%d %d\n",i,i+3); 530 if(n%4)printf("%d %d\n%d %d\n%d %d\n",i,n,i,i+1,i+1,n); 531 else printf("%d %d\n",i,i+1); 532 } 533 for(int i=1;i<n;i+=4) 534 for(int j=i+4;j<n;j+=4) 535 { 536 printf("%d %d\n",i+3,j+2); 537 printf("%d %d\n",i+2,j+2); 538 printf("%d %d\n",i+3,j+1); 539 printf("%d %d\n",i,j+1); 540 printf("%d %d\n",i+1,j+3); 541 printf("%d %d\n",i+2,j+3); 542 printf("%d %d\n",i+1,j+2); 543 printf("%d %d\n",i+1,j+1); 544 printf("%d %d\n",i+3,j); 545 printf("%d %d\n",i+3,j+3); 546 printf("%d %d\n",i,j+2); 547 printf("%d %d\n",i,j+3); 548 printf("%d %d\n",i+2,j); 549 printf("%d %d\n",i+2,j+1); 550 printf("%d %d\n",i+1,j); 551 printf("%d %d\n",i,j); 552 } 553 return 0; 554 } 555 ``` 556 557 Tutorial is loading... 558 559 From: [saliii](/profile/saliii "Candidate Master saliii"), Writer: [amsen](/profile/amsen "Candidate Master amsen") 560 561 Time Complexity:  562 563 Memory complexity:  564 565 **Java8** 566 567 ``` 568 import java.io.OutputStream; 569 import java.io.IOException; 570 import java.io.InputStream; 571 import java.io.OutputStream; 572 import java.io.PrintWriter; 573 import java.io.BufferedWriter; 574 import java.util.InputMismatchException; 575 import java.io.IOException; 576 import java.util.Stack; 577 import java.util.ArrayList; 578 import java.util.List; 579 import java.util.stream.Stream; 580 import java.util.Vector; 581 import java.io.Writer; 582 import java.io.OutputStreamWriter; 583 import java.util.BitSet; 584 import java.io.InputStream; 585 586 /** 587 * Built using CHelper plug-in 588 * Actual solution is at the top 589 */ 590 public class Main { 591 public static void main(String[] args) { 592 InputStream inputStream = System.in; 593 OutputStream outputStream = System.out; 594 InputReader in = new InputReader(inputStream); 595 OutputWriter out = new OutputWriter(outputStream); 596 TaskF solver = new TaskF(); 597 solver.solve(1, in, out); 598 out.close(); 599 } 600 601 static class TaskF { 602 public int mod = 1000000007; 603 public int n; 604 public int a; 605 public int b; 606 public char[][] adj; 607 public List<Integer>[] graph; 608 609 public void solve(int testNumber, InputReader in, OutputWriter out) { 610 n = in.nextInt(); 611 a = in.nextInt(); 612 b = in.nextInt(); 613 adj = new char[n][n]; 614 graph = Stream.generate(ArrayList::new).limit(n).toArray(List[]::new); 615 for (int i = 0; i < n; i++) adj[i] = in.next().toCharArray(); 616 for (int i = 0; i < n; i++) { 617 for (int j = 0; j < n; j++) { 618 if (adj[i][j] == '1') { 619 graph[i].add(j); 620 } 621 } 622 } 623 List<List<Integer>> comp = new SCCTarjan().scc(graph); 624 boolean[][] can = new boolean[n][]; 625 int[] low = new int[n]; 626 for (int i = 0; i < n; i++) { 627 int q = in.nextInt(); 628 char[] w = in.next().toCharArray(); 629 can[i] = new boolean[q]; 630 for (int j = 0; j < q; j++) { 631 can[i][j] = w[j] == '1'; 632 if (can[i][j]) low[i]++; 633 } 634 } 635 int[] wcomp = new int[n]; 636 int idx = 0; 637 List<BitSet> bb = new ArrayList<>(); 638 List<Integer> bs = new ArrayList<>(); 639 for (List<Integer> gg : comp) { 640 int gcd = 0; 641 for (int x : gg) { 642 gcd = Utils.gcd(gcd, can[x].length); 643 wcomp[x] = idx; 644 } 645 idx++; 646 BitSet d = new BitSet(gcd); 647 bs.add(gcd); 648 bb.add(d); 649 for (int x : gg) { 650 for (int i = 0; i < can[x].length; i++) { 651 if (can[x][i]) { 652 d.set(i % gcd, true); 653 } 654 } 655 } 656 } 657 658 for (int kk = comp.size() - 1; kk > 0; kk--) { 659 int g = Utils.gcd(bs.get(kk), bs.get(kk - 1)); 660 BitSet ww = new BitSet(g); 661 for (int i = 0; i < bs.get(kk); i += g) { 662 ww.or(bb.get(kk).get(i, i + g)); 663 } 664 for (int i = 0; i < bs.get(kk - 1); i++) { 665 if (ww.get(i % g)) { 666 bb.get(kk - 1).set(i, true); 667 } 668 } 669 } 670 int[] high = new int[n]; 671 for (int i = 0; i < n; i++) { 672 for (int j = 0; j < can[i].length; j++) { 673 if (bb.get(wcomp[i]).get(j % bs.get(wcomp[i]))) 674 high[i]++; 675 } 676 } 677 long ret = 0; 678 int[][] comb = Utils.getComb(n + 1, mod); 679 for (int lowest = 0; lowest < n; lowest++) { 680 int countabove = 0; 681 for (int other = 0; other < n; other++) { 682 if (other == lowest) continue; 683 if (low[other] > high[lowest]) { 684 countabove++; 685 } 686 } 687 if (countabove >= a) { 688 continue; 689 } 690 int canbig = 0; 691 for (int other = 0; other < n; other++) { 692 if (other == lowest) continue; 693 if (low[other] <= high[lowest] && (high[other] > high[lowest] || (high[other] == high[lowest] && other > lowest))) { 694 canbig++; 695 } 696 } 697 698 for (int take = 0; take < b && take <= canbig && take + countabove < a; take++) { 699 ret = (ret + 1L * comb[canbig][take] * comb[countabove][b - take - 1]) % mod; 700 } 701 } 702 out.println(ret); 703 } 704 705 } 706 707 static class OutputWriter { 708 private final PrintWriter writer; 709 710 public OutputWriter(OutputStream outputStream) { 711 writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream))); 712 } 713 714 public OutputWriter(Writer writer) { 715 this.writer = new PrintWriter(writer); 716 } 717 718 public void close() { 719 writer.close(); 720 } 721 722 public void println(long i) { 723 writer.println(i); 724 } 725 726 } 727 728 static class Utils { 729 public static int gcd(int a, int b) { 730 return b == 0 ? a : gcd(b, a % b); 731 } 732 733 public static int[][] getComb(int sz, int mod) { 734 int[][] comb = new int[sz][sz]; 735 for (int i = 0; i < sz; i++) { 736 comb[i][0] = 1; 737 for (int j = 1; j <= i; j++) { 738 comb[i][j] = comb[i - 1][j] + comb[i - 1][j - 1]; 739 if (comb[i][j] >= mod) comb[i][j] -= mod; 740 } 741 } 742 return comb; 743 } 744 745 } 746 747 static class InputReader { 748 private InputStream stream; 749 private byte[] buf = new byte[1024]; 750 private int curChar; 751 private int numChars; 752 753 public InputReader(InputStream stream) { 754 this.stream = stream; 755 } 756 757 public int read() { 758 if (this.numChars == -1) { 759 throw new InputMismatchException(); 760 } else { 761 if (this.curChar >= this.numChars) { 762 this.curChar = 0; 763 764 try { 765 this.numChars = this.stream.read(this.buf); 766 } catch (IOException var2) { 767 throw new InputMismatchException(); 768 } 769 770 if (this.numChars <= 0) { 771 return -1; 772 } 773 } 774 775 return this.buf[this.curChar++]; 776 } 777 } 778 779 public int nextInt() { 780 int c; 781 for (c = this.read(); isSpaceChar(c); c = this.read()) { 782 ; 783 } 784 785 byte sgn = 1; 786 if (c == 45) { 787 sgn = -1; 788 c = this.read(); 789 } 790 791 int res = 0; 792 793 while (c >= 48 && c <= 57) { 794 res *= 10; 795 res += c - 48; 796 c = this.read(); 797 if (isSpaceChar(c)) { 798 return res * sgn; 799 } 800 } 801 802 throw new InputMismatchException(); 803 } 804 805 public String next() { 806 int c; 807 while (isSpaceChar(c = this.read())) { 808 ; 809 } 810 811 StringBuilder result = new StringBuilder(); 812 result.appendCodePoint(c); 813 814 while (!isSpaceChar(c = this.read())) { 815 result.appendCodePoint(c); 816 } 817 818 return result.toString(); 819 } 820 821 public static boolean isSpaceChar(int c) { 822 return c == 32 || c == 10 || c == 13 || c == 9 || c == -1; 823 } 824 825 } 826 827 static class SCCTarjan { 828 List<Integer>[] graph; 829 boolean[] visited; 830 Stack<Integer> stack; 831 int time; 832 int[] lowlink; 833 List<List<Integer>> components; 834 835 public List<List<Integer>> scc(List<Integer>[] graph) { 836 int n = graph.length; 837 this.graph = graph; 838 visited = new boolean[n]; 839 stack = new Stack<>(); 840 time = 0; 841 lowlink = new int[n]; 842 components = new ArrayList<>(); 843 844 for (int u = 0; u < n; u++) 845 if (!visited[u]) 846 dfs(u); 847 848 return components; 849 } 850 851 void dfs(int u) { 852 lowlink[u] = time++; 853 visited[u] = true; 854 stack.add(u); 855 boolean isComponentRoot = true; 856 857 for (int v : graph[u]) { 858 if (!visited[v]) 859 dfs(v); 860 if (lowlink[u] > lowlink[v]) { 861 lowlink[u] = lowlink[v]; 862 isComponentRoot = false; 863 } 864 } 865 866 if (isComponentRoot) { 867 List<Integer> component = new ArrayList<>(); 868 while (true) { 869 int x = stack.pop(); 870 component.add(x); 871 lowlink[x] = Integer.MAX_VALUE; 872 if (x == u) 873 break; 874 } 875 components.add(component); 876 } 877 } 878 879 } 880 } 881 ``` 882 883 **C++** 884 885 ``` 886 #define pb push_back 887 #define mp make_pair 888 #define all(x) (x).begin(),(x).end() 889 #define fi first 890 #define se second 891 892 const int maxn = 5005; 893 const int maxelem = 2000006; 894 const int MOD = 1000000007; 895 896 char gr[maxn][maxn]; 897 string init[maxn]; 898 int mincnt[maxn], maxcnt[maxn]; 899 int c[maxn][maxn]; 900 int n, m, A, B; 901 bool was[maxn]; 902 vector<int> order; 903 vector<bool> can[maxn]; 904 bool nowcan[maxelem]; 905 char s[maxelem]; 906 int gcd[maxn]; 907 vector<int> comp[maxn]; 908 909 void preorder(int cur) 910 { 911 if (was[cur]) return; 912 was[cur] = true; 913 for (int i = 0; i < n; i++) if (gr[cur][i] == '1') preorder(i); 914 order.pb(cur); 915 } 916 917 void color(int cur, int cc) 918 { 919 if (was[cur]) return; 920 was[cur] = true; 921 gcd[cc] = __gcd(gcd[cc], (int)init[cur].size()); 922 comp[cc].pb(cur); 923 for (int i = 0; i < n; i++) if (gr[i][cur] == '1') color(i, cc); 924 } 925 926 int getc(int n, int k) 927 { 928 if (k < 0 || k > n) return 0; 929 return c[n][k]; 930 } 931 932 int main() 933 { 934 scanf("%d%d%d", &n, &A, &B); 935 for (int i = 0; i < n; i++) 936 { 937 scanf("%s", gr[i]); 938 } 939 for (int i = 0; i < n; i++) 940 { 941 scanf("%*d"); 942 scanf("%s", s); 943 init[i] = string(s); 944 for (int j = 0; j < (int)init[i].size(); j++) mincnt[i] += init[i][j] == '1'; 945 maxcnt[i] = mincnt[i]; 946 } 947 for (int i = 0; i < n; i++) if (!was[i]) preorder(i); 948 memset(was, 0, sizeof(was)); 949 int cc = 0; 950 reverse(all(order)); 951 for (auto t : order) if (!was[t]) 952 { 953 color(t, cc); 954 cc++; 955 } 956 for (int i = 0; i < cc; i++) 957 { 958 can[i].resize(gcd[i]); 959 for (int j = 0; j < gcd[i]; j++) can[i][j] = false; 960 for (auto t : comp[i]) 961 { 962 for (int j = 0; j < (int)init[t].size(); j++) if (init[t][j] == '1') can[i][j % gcd[i]] = true; 963 } 964 } 965 for (int i = 0; i < cc - 1; i++) 966 { 967 int g = __gcd(gcd[i], gcd[i + 1]); 968 for (int j = 0; j < g; j++) nowcan[j] = false; 969 for (int j = 0; j < gcd[i]; j++) nowcan[j % g] |= can[i][j]; 970 for (int j = 0; j < gcd[i + 1]; j++) can[i + 1][j] = (can[i + 1][j] | nowcan[j % g]); 971 } 972 for (int i = 0; i < cc; i++) 973 { 974 for (auto t : comp[i]) 975 { 976 for (int j = 0; j < (int)init[t].size(); j++) if (init[t][j] == '0' && can[i][j % gcd[i]]) maxcnt[t]++; 977 } 978 } 979 980 c[0][0] = 1; 981 for (int i = 1; i <= n; i++) 982 { 983 c[i][0] = 1; 984 for (int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % MOD; 985 } 986 int answer = 0; 987 for (int i = 0; i < n; i++) 988 { 989 int cntbigger = 0; 990 int cntupper = 0; 991 for (int j = 0; j < n; j++) if (i != j) 992 { 993 if (mincnt[j] > maxcnt[i]) cntbigger++; 994 else if (maxcnt[j] > maxcnt[i] || (maxcnt[j] == maxcnt[i] && j > i)) cntupper++; 995 } 996 if (cntbigger >= A) continue; 997 for (int j = max(0, B - 1 - cntbigger); j <= cntupper && j + cntbigger + 1 <= A && j + 1 <= B; j++) 998 { 999 answer = (answer + (ll)getc(cntupper, j) * getc(cntbigger, B - 1 - j)) % MOD; 1000 } 1001 } 1002 cout << answer << endl; 1003 return 0; 1004 } 1005 ``` 1006 1007 **C++** 1008 1009 ``` 1010 #include <bits/stdc++.h> 1011 #define xx first 1012 #define yy second 1013 #define mp make_pair 1014 #define pb push_back 1015 #define fill( x, y ) memset( x, y, sizeof x ) 1016 #define copy( x, y ) memcpy( x, y, sizeof x ) 1017 using namespace std; 1018 1019 typedef long long LL; 1020 typedef pair < int, int > pa; 1021 1022 inline int read() 1023 { 1024 int sc = 0, f = 1; char ch = getchar(); 1025 while( ch < '0' || ch > '9' ) { if( ch == '-' ) f = -1; ch = getchar(); } 1026 while( ch >= '0' && ch <= '9' ) sc = sc * 10 + ch - '0', ch = getchar(); 1027 return sc * f; 1028 } 1029 1030 const int MAXN = 5005; 1031 const int MAXM = 2000005; 1032 const int mod = 1e9 + 7; 1033 1034 int n, a, b, len[MAXN], can[MAXM], id_cnt, L[MAXN], R[MAXN], C[MAXN][MAXN]; 1035 int dfn[MAXN], scc[MAXN], low[MAXN], tim, num, st[MAXN], top, w[MAXN], ans; 1036 vector < int > G[MAXN], id[MAXN], scc_bit[MAXN], v[MAXN]; 1037 char ch[MAXM]; 1038 1039 inline void inc(int &x, int y) { x += y; if( x >= mod ) x -= mod; } 1040 1041 inline void dfs(int x) 1042 { 1043 dfn[ x ] = low[ x ] = ++tim; st[ ++top ] = x; 1044 for( auto y : G[ x ] ) 1045 if( !dfn[ y ] ) dfs( y ), low[ x ] = min( low[ x ], low[ y ] ); 1046 else if( !scc[ y ] ) low[ x ] = min( low[ x ], dfn[ y ] ); 1047 if( dfn[ x ] == low[ x ] ) 1048 { 1049 num++; int t = 0; 1050 while( t ^ x ) 1051 { 1052 scc[ t = st[ top-- ] ] = num; 1053 w[ num ] = __gcd( w[ num ], len[ t ] ); 1054 v[ num ].pb( t ); 1055 } 1056 scc_bit[ num ].resize( w[ num ] ); 1057 for( auto y : v[ num ] ) 1058 for( int d = 0 ; d < len[ y ] ; d++ ) if( can[ id[ y ][ d ] ] ) scc_bit[ num ][ d % w[ num ] ] = 1; 1059 } 1060 } 1061 1062 int main() 1063 { 1064 #ifdef wxh010910 1065 freopen( "data.in", "r", stdin ); 1066 #endif 1067 n = read(), a = read(), b = read(); 1068 for( int i = 0 ; i <= n ; i++ ) 1069 { 1070 C[ i ][ 0 ] = 1; 1071 for( int j = 1 ; j <= i ; j++ ) inc( C[ i ][ j ] = C[ i - 1 ][ j ], C[ i - 1 ][ j - 1 ] ); 1072 } 1073 for( int i = 1 ; i <= n ; i++ ) 1074 { 1075 scanf( "%s", ch + 1 ); 1076 for( int j = 1 ; j <= n ; j++ ) if( ch[ j ] == '1' ) G[ i ].pb( j ); 1077 } 1078 for( int i = 1 ; i <= n ; i++ ) 1079 { 1080 len[ i ] = read(); scanf( "%s", ch ); 1081 for( int j = 0 ; j < len[ i ] ; j++ ) id[ i ].pb( ++id_cnt ), can[ id_cnt ] = ch[ j ] == '1', L[ i ] += can[ id_cnt ]; 1082 } 1083 for( int i = 1 ; i <= n ; i++ ) if( !dfn[ i ] ) dfs( i ); 1084 for( int i = num ; i > 1 ; i-- ) 1085 { 1086 int g = __gcd( w[ i ], w[ i - 1 ] ); 1087 w[ i - 1 ] = g; 1088 for( int j = 0 ; j < w[ i ] ; j++ ) scc_bit[ i - 1 ][ j % g ] |= scc_bit[ i ][ j ]; 1089 } 1090 for( int i = 1 ; i <= n ; i++ ) 1091 { 1092 int x = scc[ i ]; 1093 for( int j = 0 ; j < len[ i ] ; j++ ) 1094 R[ i ] += scc_bit[ x ][ j % w[ x ] ]; 1095 } 1096 for( int i = 1 ; i <= n ; i++ ) 1097 { 1098 int t1 = 0, t2 = 0; 1099 for( int j = 1 ; j <= n ; j++ ) if( L[ j ] > R[ i ] ) t1++; 1100 if( t1 >= a ) continue; 1101 for( int j = 1 ; j <= n ; j++ ) if( L[ j ] <= R[ i ] && mp( R[ j ], j ) > mp( R[ i ], i ) ) t2++; 1102 for( int j = 0 ; j < b && j <= t2 && j + t1 < a ; j++ ) 1103 inc( ans, 1LL * C[ t2 ][ j ] * C[ t1 ][ b - j - 1 ] % mod ); 1104 } 1105 return printf( "%d\n", ans ), 0; 1106 } 1107 ``` 1108 1109 As my good friend, [Arpa](/profile/Arpa "Candidate Master Arpa"), did, let me share with you a perfect poem of one of our best poet you might know, Molavi: 1110 1111 .......................................................................................بند بگسل، باش آزاد ای پسر ** چند باشی بند سیم و بند زر 1112 1113 *O* *son*, *burst* *thy* *chains* *and* *be* *free*! *How* *long* *wilt* *thou* *be* *a* *bondsman* *to* *silver* *and* *gold*? 1114 1115 .......................................................................................گر بریزی بحر را در کوزهای ** چند گنجد قسمت یک روزهای 1116 1117 *If* *thou* *pour* *the* *sea* *into* *a* *pitcher*, *how* *much* *will* *it* *hold*? *One* *day*'*s* *store*. 1118 1119 ..................................................................................... کوزهی چشم حریصان پر نشد ** تا صدف قانع نشد پر در نشد 1120 1121 *The* *pitcher*, *the* *eye* *of* *the* *covetous*, *never* *becomes* *full*: *the* *oyster* - *shell* *is* *not* *filled* *with* *pearls* *until* *it* *is* *contented*. 1122 1123 .............................................................................. هر که را جامه ز عشقی چاک شد ** او ز حرص و عیب کلی پاک شد 1124 1125 *He* (*alone*) *whose* *garment* *is* *rent* *by* *a* (*mighty*) *love* *is* *purged* *entirely* *of* *covetousness* *and* *defect*.