2062.md (18451B)
1 Source: https://codeforces.com/blog/entry/138866 2 3 [2062A - String](/contest/2062/problem/A) 4 5 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Preparation: [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"), [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). 6 7 **Rate this problem** 8 9 Good problem 10 11 Average problem 12 13 Bad problem 14 15 Did not solve 16 17 **Solution** 18 19 Tutorial is loading... 20 21 **Code (C++)** 22 23 ``` 24 #include<bits/stdc++.h> 25 using namespace std; 26 string s; 27 int main(){ 28 ios::sync_with_stdio(false),cin.tie(0); 29 int T,n,i,ans; 30 for(cin>>T;T>0;T--) 31 { 32 cin>>s;n=s.size(); 33 ans=0; 34 for(i=0;i<n;i++)ans+=s[i]-'0'; 35 cout<<ans<<'\n'; 36 } 37 return 0; 38 } 39 ``` 40 41 **Code (Python)** 42 43 ``` 44 for _ in range(int(input())): 45 print(input().count('1')) 46 ``` 47 48 [2062B - Clockwork](/contest/2062/problem/B) 49 50 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Preparation: [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"), [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). 51 52 **Rate this problem** 53 54 Good problem 55 56 Average problem 57 58 Bad problem 59 60 Did not solve 61 62 **Solution** 63 64 Tutorial is loading... 65 66 **Code (C++)** 67 68 ``` 69 #include<bits/stdc++.h> 70 using namespace std; 71 int main(){ 72 ios::sync_with_stdio(false),cin.tie(0); 73 int T,n,i,t,flag; 74 for(cin>>T;T>0;T--) 75 { 76 cin>>n; 77 flag=0; 78 for(i=0;i<n;i++) 79 { 80 cin>>t; 81 if(t<=i*2||t<=(n-i-1)*2)flag=1; 82 } 83 if(flag)cout<<"NO\n"; 84 else cout<<"YES\n"; 85 } 86 return 0; 87 } 88 ``` 89 90 **Code (Python)** 91 92 ``` 93 for _ in range(int(input())): 94 n=int(input()) 95 a=list(map(int,input().split())) 96 for i in range(n): 97 if a[i]<=max(i,n-i-1)*2: 98 print('NO') 99 break 100 else: 101 print('YES') 102 ``` 103 104 [2062C - Cirno and Operations](/contest/2062/problem/C) 105 106 Idea: [Yakumo_Ran](/profile/Yakumo_Ran "Master Yakumo_Ran"). Solution: [Yakumo_Ran](/profile/Yakumo_Ran "Master Yakumo_Ran"). Preparation: [Yakumo_Ran](/profile/Yakumo_Ran "Master Yakumo_Ran"), [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"), [mejiamejia](/profile/mejiamejia "Expert mejiamejia"). 107 108 **Rate this problem** 109 110 Good problem 111 112 Average problem 113 114 Bad problem 115 116 Did not solve 117 118 **Solution** 119 120 Tutorial is loading... 121 122 **Code (C++)** 123 124 ``` 125 #include <bits/stdc++.h> 126 using namespace std; 127 128 long long a[1010]; 129 130 int main(){ 131 int t; 132 cin >> t; 133 while (t--){ 134 int n; 135 cin >> n; 136 for (int i = 1; i <= n; i++) cin >> a[i]; 137 int now = n; 138 long long ans = -1e18; 139 for (int i = 1; i <= n; i++){ 140 long long sum = 0; 141 for (int i = 1; i <= now; i++) sum = (sum + a[i]) ; 142 if (i == 1) ans = max(ans, sum); 143 else ans = max(ans, max(sum, ( - sum) )); 144 for (int i = 1; i < now; i++) a[i] = (a[i + 1] - a[i]) ; 145 now--; 146 } 147 cout << ans << endl; 148 } 149 return 0; 150 } 151 ``` 152 153 **Code (Python)** 154 155 ``` 156 from math import * 157 for _ in range(int(input())): 158 n=int(input()) 159 a=list(map(int,input().split())) 160 ans=sum(a) 161 while n>1: 162 n-=1 163 a=[a[i+1]-a[i] for i in range(n)] 164 ans=max(ans,abs(sum(a))) 165 print(ans) 166 ``` 167 168 [2062D - Balanced Tree](/contest/2062/problem/D) 169 170 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"), [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"), [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"). Preparation: [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"). 171 172 **Rate this problem** 173 174 Good problem 175 176 Average problem 177 178 Bad problem 179 180 Did not solve 181 182 **Solution** 183 184 Tutorial is loading... 185 186 **Code (C++)** 187 188 ``` 189 #include "bits/stdc++.h" 190 using namespace std; 191 #define all(x) (x).begin(),(x).end() 192 int main() 193 { 194 ios::sync_with_stdio(0); cin.tie(0); 195 int T; cin >> T; 196 while (T--) 197 { 198 int n, i; 199 cin >> n; 200 vector<int> l(n), r(n), a(n); 201 for (i = 0; i < n; i++) cin >> l[i] >> r[i]; 202 vector e(n, vector<int>(0)); 203 for (i = 1; i < n; i++) 204 { 205 int u, v; 206 cin >> u >> v; 207 --u, --v; 208 e[u].push_back(v); 209 e[v].push_back(u); 210 } 211 long long ans = 0; 212 function<void(int)> dfs = [&](int u) { 213 int mx = l[u]; 214 for (int v : e[u]) 215 { 216 erase(e[v], u); 217 dfs(v); 218 mx = max(mx, a[v]); 219 } 220 a[u] = min(mx, r[u]); 221 for (int v : e[u]) ans += max(0, a[v] - a[u]); 222 }; 223 dfs(0); 224 cout << ans + a[0] << "\n"; 225 } 226 } 227 ``` 228 229 **Code (Python)** 230 231 ``` 232 for _ in range(int(input())): 233 n = int(input()) 234 l,r=[],[] 235 for i in range(n): 236 L,R=map(int,input().split()) 237 l.append(L) 238 r.append(R) 239 e=[[] for i in range(n)] 240 for i in range(n-1): 241 u,v=map(int,input().split()) 242 e[u-1].append(v-1) 243 e[v-1].append(u-1) 244 stk=[0] 245 f=[-1]*n 246 nfd=[] 247 while stk: 248 u=stk.pop() 249 nfd.append(u) 250 for v in e[u]: 251 if v!=f[u]: 252 f[v]=u 253 stk.append(v) 254 nfd.reverse() 255 ans=0 256 for u in nfd: 257 for v in e[u]: 258 if f[v]==u: 259 l[u]=max(l[u],l[v]) 260 l[u]=min(l[u],r[u]) 261 for v in e[u]: 262 if f[v]==u: 263 ans+=max(0,l[v]-l[u]) 264 print(ans+l[0]) 265 ``` 266 267 [2062E1 - The Game (Easy Version)](/contest/2062/problem/E1) 268 269 Idea: [Yakumo_Ran](/profile/Yakumo_Ran "Master Yakumo_Ran"). Solution: [Yakumo_Ran](/profile/Yakumo_Ran "Master Yakumo_Ran"). Preparation: [Yakumo_Ran](/profile/Yakumo_Ran "Master Yakumo_Ran"),[mejiamejia](/profile/mejiamejia "Expert mejiamejia"),[SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"). 270 271 **Rate this problem** 272 273 Good problem 274 275 Average problem 276 277 Bad problem 278 279 Did not solve 280 281 **Solution** 282 283 Tutorial is loading... 284 285 **Code (C++)** 286 287 ``` 288 #include "bits/stdc++.h" 289 using namespace std; 290 const int N=1e6+5; 291 vector<int> e[N]; 292 int w[N],dfn[N],nfd[N],pre[N],suf[N],low[N]; 293 bool ed[N]; 294 int id; 295 void dfs(int u) 296 { 297 if (ed[u]) return; 298 ed[u]=1; 299 dfn[u]=++id; 300 nfd[id]=u; 301 for (int v:e[u]) dfs(v); 302 ed[u]=0; 303 low[u]=id; 304 } 305 int main() 306 { 307 ios::sync_with_stdio(0); cin.tie(0); 308 cout<<fixed<<setprecision(15); 309 int T; cin>>T; 310 while (T--) 311 { 312 int n,m,i,j; 313 cin>>n; 314 for (i=1; i<=n; i++) 315 { 316 e[i].clear(); 317 id=0; 318 } 319 for (i=1; i<=n; i++) cin>>w[i]; 320 for (i=1; i<n; i++) 321 { 322 int u,v; 323 cin>>u>>v; 324 e[u].push_back(v); 325 e[v].push_back(u); 326 } 327 dfs(1); 328 for (i=1; i<=n; i++) pre[i]=max(pre[i-1],w[nfd[i]]); 329 suf[n+1]=0; 330 for (i=n; i; i--) suf[i]=max(suf[i+1],w[nfd[i]]); 331 int mx=0; 332 for (i=1; i<=n; i++) if (max(pre[dfn[i]-1],suf[low[i]+1])>w[i]&&w[i]>w[mx]) mx=i; 333 cout<<mx<<'\n'; 334 } 335 } 336 ``` 337 338 **Code (Python)** 339 340 ``` 341 for _ in range(int(input())): 342 n = int(input()) 343 w=[int(x) for x in input().split()] 344 wb=[[] for i in range(n)] 345 for i in range(n): 346 w[i]-=1 347 wb[w[i]].append(i) 348 e=[[] for i in range(n)] 349 for i in range(n-1): 350 u,v=map(int,input().split()) 351 e[u-1].append(v-1) 352 e[v-1].append(u-1) 353 stk=[0] 354 f,dfn=[-1]*n,[0]*n 355 nfd=[] 356 while stk: 357 u=stk.pop() 358 dfn[u]=len(nfd) 359 nfd.append(u) 360 for v in e[u]: 361 if v!=f[u]: 362 f[v]=u 363 stk.append(v) 364 sz=[1]*n 365 nfd.reverse() 366 for u in nfd: 367 if u==0: 368 continue 369 sz[f[u]]+=sz[u] 370 wb.reverse() 371 mx=-1;mn=n+1 372 for v in wb: 373 for u in v: 374 if mn<dfn[u] or mx>dfn[u]+sz[u]-1: 375 print(u+1) 376 break 377 else: 378 for u in v: 379 mn=min(mn,dfn[u]) 380 mx=max(mx,dfn[u]) 381 continue 382 break 383 else: 384 print(0) 385 ``` 386 387 [2062E2 - The Game (Hard Version)](/contest/2062/problem/E2) 388 389 Idea: [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"),[SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"),[PaperCloud](/profile/PaperCloud "Master PaperCloud"),[fallleaves01](/profile/fallleaves01 "International Grandmaster fallleaves01"). Preparation: [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"),[mejiamejia](/profile/mejiamejia "Expert mejiamejia"). 390 391 **Rate this problem** 392 393 Good problem 394 395 Average problem 396 397 Bad problem 398 399 Did not solve 400 401 **Solution** 402 403 Tutorial is loading... 404 405 **Code (C++)** 406 407 ``` 408 #include "bits/stdc++.h" 409 using namespace std; 410 #define all(x) (x).begin(),(x).end() 411 const int N = 5e5 + 2; 412 vector<int> e[N]; 413 int dfn[N], nfd[N], low[N]; 414 int id, n; 415 void dfs(int u) 416 { 417 nfd[dfn[u] = ++id] = u; 418 for (int v : e[u]) erase(e[v], u), dfs(v); 419 low[u] = id; 420 } 421 int main() 422 { 423 ios::sync_with_stdio(0); cin.tie(0); 424 cout << fixed << setprecision(15); 425 int T; cin >> T; 426 while (T--) 427 { 428 int n, m, i, j; 429 cin >> n; 430 vector w(n, vector<int>()); 431 vector<int> c(n + 1), ans; 432 for (i = 1; i <= n; i++) 433 { 434 e[i].clear(); id = 0; 435 cin >> j; 436 w[j - 1].push_back(i); 437 } 438 for (i = 1; i < n; i++) 439 { 440 int u, v; 441 cin >> u >> v; 442 e[u].push_back(v); 443 e[v].push_back(u); 444 } 445 dfs(1); 446 int l = n + 1, r = 0; 447 set<int> s; 448 for (i = n - 1; i >= 0; i--) 449 { 450 if (s.size()) 451 { 452 for (int u : w[i]) 453 { 454 int mx = 0; 455 for (j = dfn[u] - 1; j; j -= j & -j) mx = max(mx, c[j]); 456 if ((*s.begin() < dfn[u] || *s.rbegin() > low[u]) && mx <= low[u] && dfn[u] <= l && low[u] >= r) 457 ans.push_back(u); 458 } 459 for (int u : w[i]) 460 { 461 int mn = *s.begin(), mx = *s.rbegin(); 462 int L = dfn[u], R = low[u]; 463 if (mn >= L && mx <= R) continue; 464 if (mn >= L && mn <= R) mn = *s.upper_bound(R); 465 if (mx >= L && mx <= R) mx = *prev(s.lower_bound(L)); 466 auto fun = [&](int x, int y) { 467 if (x > y) swap(x, y); 468 l = min(l, y), r = max(r, x); 469 for (j = x; j <= n; j += j & -j) c[j] = max(c[j], y); 470 }; 471 fun(mn, dfn[u]); 472 fun(mx, dfn[u]); 473 } 474 } 475 for (int u : w[i]) s.insert(dfn[u]); 476 } 477 sort(all(ans)); 478 cout << ans.size(); 479 for (int x : ans) cout << ' ' << x; 480 cout << '\n'; 481 } 482 } 483 ``` 484 485 [2062F - Traveling Salescat](/contest/2062/problem/F) 486 487 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Preparation: [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"), [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). 488 489 **Rate this problem** 490 491 Good problem 492 493 Average problem 494 495 Bad problem 496 497 Did not solve 498 499 **Solution** 500 501 Tutorial is loading... 502 503 **Code (C++)** 504 505 ``` 506 #include<bits/stdc++.h> 507 using namespace std; 508 struct apos{ 509 long long a; 510 long long b; 511 friend bool operator<(apos a,apos b){ 512 return a.b-a.a<b.b-b.a; 513 } 514 }ap[3000]; 515 long long dp[3001][3],tdp[3001][3],ans[3001],inf=1000000000000000000LL; 516 int main(){ 517 ios::sync_with_stdio(false),cin.tie(0); 518 int T,n,i,j,t; 519 for(cin>>T;T>0;T--) 520 { 521 cin>>n; 522 for(i=0;i<n;i++)cin>>ap[i].a>>ap[i].b; 523 sort(ap,ap+n); 524 for(i=0;i<=n;i++) 525 { 526 for(j=0;j<3;j++) 527 { 528 dp[i][j]=inf; 529 tdp[i][j]=inf; 530 } 531 ans[i]=inf; 532 } 533 for(i=0;i<n;i++) 534 { 535 tdp[1][0]=min(tdp[1][0],ap[i].a*2); 536 tdp[1][1]=min(tdp[1][1],ap[i].a); 537 for(j=1;j<n;j++) 538 { 539 for(t=0;t<3;t++)tdp[j+1][t]=min(tdp[j+1][t],dp[j][t]+ap[i].a+ap[i].b); 540 tdp[j+1][1]=min(tdp[j+1][1],dp[j][0]+ap[i].b); 541 tdp[j+1][2]=min(tdp[j+1][2],dp[j][1]+ap[i].a); 542 ans[j+1]=min(ans[j+1],dp[j][1]+ap[i].b); 543 ans[j+1]=min(ans[j+1],dp[j][2]+ap[i].b*2); 544 } 545 for(j=1;j<=n;j++) 546 { 547 for(t=0;t<3;t++) 548 { 549 dp[j][t]=min(dp[j][t],tdp[j][t]); 550 tdp[j][t]=inf; 551 } 552 } 553 } 554 for(i=2;i<=n;i++)cout<<ans[i]<<' '; 555 cout<<'\n'; 556 } 557 return 0; 558 } 559 ``` 560 561 **Code (Python)** 562 563 ``` 564 class Q: 565 def __init__(this,x,y): 566 this.x,this.y=x+y,x-y 567 def __lt__(this,rhs): 568 return this.y<rhs.y 569 for _ in range(int(input())): 570 n=int(input()) 571 a=[0]*n 572 for i in range(n): 573 x,y=map(int,input().split()) 574 a[i]=Q(x,y) 575 a.sort() 576 l=[10**18]*(n+1) 577 sl=l.copy();slt=l.copy();slrt=l.copy() 578 s=10**18 579 for m,t in enumerate(a): 580 x,y=t.x,t.y 581 for i in range(m,0,-1): 582 slrt[i+1]=min(slrt[i+1],sl[i]+x+y,slt[i]+x*2+y*2) 583 slt[i+1]=min(slt[i+1],slt[i]+x*2,sl[i]+x-y) 584 sl[i+1]=min(sl[i+1],sl[i]+x*2,l[i]+x+y) 585 l[i+1]=min(l[i+1],l[i]+x*2) 586 sl[1]=min(sl[1],x-y) 587 l[1]=min(l[1],x*2-y*2) 588 print(*[x//2 for x in slrt[2:]]) 589 ``` 590 591 [2062G - Permutation Factory](/contest/2062/problem/G) 592 593 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Preparation: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"), [SSerxhs](/profile/SSerxhs "Legendary Grandmaster SSerxhs"). 594 595 **Rate this problem** 596 597 Good problem 598 599 Average problem 600 601 Bad problem 602 603 Did not solve 604 605 **Solution** 606 607 Tutorial is loading... 608 609 **Code (C++)** 610 611 ``` 612 #include<bits/stdc++.h> 613 using namespace std; 614 struct linex{ 615 int v; 616 int w; 617 int nxt; 618 int c; 619 }; 620 int head[210],cnt,cpos[210],vis[210],qvis[210],totc,dis[210],inf=1000000000; 621 linex l[21000]; 622 queue<int>que; 623 void add(int u,int v,int w,int c){ 624 l[cnt].nxt=head[u]; 625 head[u]=cnt; 626 l[cnt].v=v; 627 l[cnt].w=w; 628 l[cnt].c=c; 629 cnt++; 630 l[cnt].nxt=head[v]; 631 head[v]=cnt; 632 l[cnt].v=u; 633 l[cnt].w=0; 634 l[cnt].c=-c; 635 cnt++; 636 } 637 int spfa(int st,int en,int n){ 638 int i,j,t; 639 for(i=0;i<n;i++) 640 { 641 vis[i]=0; 642 dis[i]=inf; 643 cpos[i]=head[i]; 644 } 645 que.push(st); 646 dis[st]=0; 647 vis[st]=1; 648 qvis[st]=1; 649 while(!que.empty()) 650 { 651 t=que.front(); 652 que.pop(); 653 qvis[t]=0; 654 for(j=head[t];j!=-1;j=l[j].nxt) 655 { 656 if(l[j].w>0&&dis[l[j].v]>dis[t]+l[j].c) 657 { 658 dis[l[j].v]=dis[t]+l[j].c; 659 vis[l[j].v]=1; 660 if(!qvis[l[j].v]) 661 { 662 que.push(l[j].v); 663 qvis[l[j].v]=1; 664 } 665 } 666 } 667 } 668 return vis[en]; 669 } 670 long long dfs(int p,int en,int curr){ 671 int x,j,flow=0; 672 if(p==en)return curr; 673 for(j=cpos[p];j!=-1&&flow<curr;j=l[j].nxt) 674 { 675 cpos[p]=j; 676 qvis[p]=1; 677 if(l[j].w>0&&dis[l[j].v]==dis[p]+l[j].c&&!qvis[l[j].v]) 678 { 679 x=dfs(l[j].v,en,min(curr-flow,l[j].w)); 680 flow+=x; 681 l[j].w-=x; 682 l[j^1].w+=x; 683 totc+=l[j].c*x; 684 } 685 qvis[p]=0; 686 } 687 return flow; 688 } 689 int p[100],q[100],id[100][100]; 690 int cabs(int x){ 691 if(x<0)x=-x; 692 return x; 693 } 694 struct point{ 695 int x; 696 int y; 697 int tx; 698 int ty; 699 }pc[100]; 700 vector<int>ansv[2]; 701 int main(){ 702 ios::sync_with_stdio(false),cin.tie(0); 703 srand(time(0)); 704 int T,n,i,j,flow,flag; 705 for(cin>>T;T>0;T--) 706 { 707 cin>>n; 708 for(i=0;i<n;i++) 709 { 710 cin>>p[i]; 711 p[i]--; 712 } 713 for(i=0;i<n;i++) 714 { 715 cin>>q[i]; 716 q[i]--; 717 } 718 for(i=0;i<n*2+2;i++)head[i]=-1; 719 cnt=0; 720 totc=0; 721 flow=0; 722 for(i=0;i<n;i++) 723 { 724 add(n*2,i,1,0); 725 add(i+n,n*2+1,1,0); 726 for(j=0;j<n;j++) 727 { 728 id[i][j]=cnt; 729 add(i,j+n,1,cabs(i-j)+cabs(p[i]-q[j])); 730 } 731 } 732 while(spfa(n*2,n*2+1,n*2+2))flow+=dfs(n*2,n*2+1,inf); 733 for(i=0;i<n;i++) 734 { 735 pc[i].x=i; 736 pc[i].y=p[i]; 737 for(j=0;j<n;j++) 738 { 739 if(l[id[i][j]].w==0) 740 { 741 pc[i].tx=j; 742 pc[i].ty=q[j]; 743 } 744 } 745 } 746 while(1) 747 { 748 flag=0; 749 for(i=0;i<n;i++) 750 { 751 for(j=0;j<n;j++) 752 { 753 if(pc[j].tx<=pc[i].x&&pc[i].x<pc[j].x&&pc[j].x<=pc[i].tx) 754 { 755 ansv[0].push_back(pc[i].x); 756 ansv[1].push_back(pc[j].x); 757 swap(pc[i].x,pc[j].x); 758 flag=1; 759 } 760 } 761 } 762 if(!flag)break; 763 } 764 while(1) 765 { 766 flag=0; 767 for(i=0;i<n;i++) 768 { 769 for(j=0;j<n;j++) 770 { 771 if(pc[j].ty<=pc[i].y&&pc[i].y<pc[j].y&&pc[j].y<=pc[i].ty) 772 { 773 ansv[0].push_back(pc[i].x); 774 ansv[1].push_back(pc[j].x); 775 swap(pc[i].y,pc[j].y); 776 flag=1; 777 } 778 } 779 } 780 if(!flag)break; 781 } 782 cout<<ansv[0].size()<<'\n'; 783 for(i=0;i<ansv[0].size();i++)cout<<ansv[0][i]+1<<' '<<ansv[1][i]+1<<'\n'; 784 ansv[0].clear(); 785 ansv[1].clear(); 786 } 787 return 0; 788 } 789 ``` 790 791 [2062H - Galaxy Generator](/contest/2062/problem/H) 792 793 Idea: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Solution: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). Preparation: [StarSilk](/profile/StarSilk "Legendary Grandmaster StarSilk"). 794 795 **Rate this problem** 796 797 Good problem 798 799 Average problem 800 801 Bad problem 802 803 Did not solve 804 805 **Solution** 806 807 Tutorial is loading... 808 809 **Code (C++)** 810 811 ``` 812 #include<bits/stdc++.h> 813 using namespace std; 814 const long long mod=1000000007; 815 string s; 816 long long dp[15][15][1<<14],vl[200],sgvl[15][15][15][15]; 817 long long dp2[15][1<<14],dpvl2[15][1<<14]; 818 int psum[15][15]; 819 long long getvl(long long l,long long r,long long x,long long y){ 820 if(l>=r||x>=y)return 0; 821 return vl[psum[r][y]-psum[l][y]-psum[r][x]+psum[l][x]]; 822 } 823 long long f(long long l,long long r,long long x,long long y){ 824 long long ans=0,i,c,tl,tr,tx,ty; 825 for(i=0;i<16;i++) 826 { 827 c=0; 828 tl=l; 829 tr=r; 830 tx=x; 831 ty=y; 832 if(i&1) 833 { 834 c^=1; 835 tl++; 836 } 837 if(i&2) 838 { 839 c^=1; 840 tr--; 841 } 842 if(i&4) 843 { 844 c^=1; 845 tx++; 846 } 847 if(i&8) 848 { 849 c^=1; 850 ty--; 851 } 852 if(c)ans=(ans+mod-getvl(tl,tr,tx,ty))%mod; 853 else ans=(ans+getvl(tl,tr,tx,ty))%mod; 854 } 855 return ans; 856 } 857 int main(){ 858 ios::sync_with_stdio(false),cin.tie(0); 859 int T,n,i,j,t,p,l,r,len,cmsk; 860 long long ans; 861 for(cin>>T;T>0;T--) 862 { 863 cin>>n; 864 vl[0]=0; 865 for(i=1;i<=n*n;i++)vl[i]=(vl[i-1]*2+1)%mod; 866 for(i=0;i<=n;i++) 867 { 868 for(j=0;j<=n;j++)psum[i][j]=0; 869 } 870 for(i=0;i<n;i++) 871 { 872 cin>>s; 873 for(j=0;j<n;j++)psum[i+1][j+1]=s[j]-'0'; 874 } 875 for(i=0;i<n;i++) 876 { 877 for(j=0;j<=n;j++)psum[i+1][j]+=psum[i][j]; 878 } 879 for(i=0;i<=n;i++) 880 { 881 for(j=0;j<n;j++)psum[i][j+1]+=psum[i][j]; 882 } 883 for(l=0;l<=n;l++) 884 { 885 for(r=l+1;r<=n;r++) 886 { 887 for(i=0;i<=n;i++) 888 { 889 for(j=i+1;j<=n;j++)sgvl[l][r][i][j]=f(l,r,i,j); 890 } 891 } 892 } 893 for(i=0;i<=n;i++) 894 { 895 for(j=0;j<=n;j++) 896 { 897 for(t=0;t<(1<<n);t++)dp[i][j][t]=0; 898 } 899 } 900 for(i=0;i<=n;i++)dp[i][i][0]=1; 901 for(len=1;len<=n;len++) 902 { 903 for(l=0;l+len<=n;l++) 904 { 905 r=l+len; 906 for(i=l+1;i<r;i++) 907 { 908 for(j=1;j<(1<<n);j++) 909 { 910 for(t=0;t<n;t++) 911 { 912 cmsk=j; 913 for(p=t;p<n&&(j>>p&1^1);p++) 914 { 915 cmsk|=(1<<p); 916 dp[l][r][cmsk]=(dp[l][r][cmsk]+dp[l][i][j]*sgvl[i][r][t][p+1])%mod; 917 } 918 } 919 } 920 } 921 for(j=1;j<(1<<n);j++) 922 { 923 for(i=0;(j>>i&1^1);i++); 924 for(t=n-1;(j>>t&1^1);t--); 925 sgvl[l][r][i][t+1]=(sgvl[l][r][i][t+1]+mod-dp[l][r][j])%mod; 926 } 927 for(i=0;i<n;i++) 928 { 929 cmsk=0; 930 for(t=i;t<n;t++) 931 { 932 cmsk|=(1<<t); 933 dp[l][r][cmsk]=(dp[l][r][cmsk]+sgvl[l][r][i][t+1])%mod; 934 } 935 } 936 if(len==1)continue; 937 for(j=0;j<(1<<n);j++)dp[l][r][j]=(dp[l][r-1][j]+dp[l][r][j])%mod; 938 } 939 } 940 for(i=0;i<=n;i++) 941 { 942 for(j=0;j<(1<<n);j++) 943 { 944 dp2[i][j]=0; 945 dpvl2[i][j]=0; 946 } 947 } 948 dp2[0][0]=1; 949 for(l=0;l<n;l++) 950 { 951 for(j=0;j<(1<<n);j++) 952 { 953 dp2[l+1][j]=(dp2[l+1][j]+dp2[l][j])%mod; 954 dpvl2[l+1][j]=(dpvl2[l+1][j]+dpvl2[l][j])%mod; 955 } 956 for(r=l+1;r<=n;r++) 957 { 958 for(j=0;j<(1<<n);j++) 959 { 960 for(i=0;i<n;i++) 961 { 962 cmsk=j; 963 for(t=i;t<n&&(j>>t&1^1);t++) 964 { 965 cmsk|=(1<<t); 966 dp2[r][cmsk]=(dp2[r][cmsk]+dp2[l][j]*sgvl[l][r][i][t+1])%mod; 967 dpvl2[r][cmsk]=(dpvl2[r][cmsk]+(dp2[l][j]+dpvl2[l][j])*sgvl[l][r][i][t+1])%mod; 968 } 969 } 970 } 971 } 972 } 973 ans=0; 974 for(j=1;j<(1<<n);j++)ans=(ans+dpvl2[n][j])%mod; 975 cout<<ans<<'\n'; 976 } 977 return 0; 978 } 979 ```