1081.md (37189B)
1 Source: https://codeforces.com/blog/entry/63888 2 3 [1081A - Definite Game](/contest/1081/problem/A "Avito Cool Challenge 2018") 4 5 Idea: [sunset](/profile/sunset "Legendary Grandmaster sunset") Developer: [sunset](/profile/sunset "Legendary Grandmaster sunset") 6 7 **Hint** 8 9 1 sounds like the minimum value we can get. Why? Is it always true? 10 11 **Solution** 12 13 When *n* ≤ 2, we can do nothing. 14 15 When *n* ≥ 3, since , *n* - 1 isn't a divisor of *n*, so we can choose it and get 1 as the result. 16 17 **Code (yjq_naiive)** 18 19 ``` 20 #include <bits/stdc++.h> 21 using namespace std; 22 int main() { 23 int n; 24 scanf("%d", &n); 25 if (n == 2) { 26 puts("2"); 27 } else { 28 puts("1"); 29 } 30 return 0; 31 } 32 ``` 33 34 [1081B - Farewell Party](/contest/1081/problem/B "Avito Cool Challenge 2018") 35 36 Idea: [yanQval](/profile/yanQval "International Grandmaster yanQval") Developer: [yanQval](/profile/yanQval "International Grandmaster yanQval") 37 38 **Hint** 39 40 Consider the number of people wearing hats of the same color. 41 42 **Solution** 43 44 let *b**i* = *n* - *a**i* represent the number of people wearing the same type of hat of *i*-th person. 45 46 Notice that the person wearing the same type of hat must have the same *b*s. Suppose the number of people having the same *b**i* be *t*, there would be exactly  kinds of hats with *b**i* wearers. Therefore, *t* must be a multiple of *b**i*. Also this is also sufficient, just give *b**i* people a new hat color, one bunch at a time. 47 48 **Code (yanQval)** 49 50 ``` 51 #include <bits/stdc++.h> 52 using namespace std; 53 const int maxn = 100010; 54 int n; 55 pair<int,int> a[maxn]; 56 int Ans[maxn],cnt; 57 int main(){ 58 ios::sync_with_stdio(false); 59 cin>>n; 60 for(int i=1;i<=n;i++){ 61 cin>>a[i].first; 62 a[i].first=n-a[i].first; 63 a[i].second=i; 64 } 65 sort(a+1,a+n+1); 66 for(int l=1,r=0;l<=n;l=r+1){ 67 for(r=l;r<n&&a[r+1].first==a[r].first;++r); 68 if((r-l+1)%a[l].first){ 69 cout<<"Impossible"<<endl; 70 return 0; 71 } 72 for(int i=l;i<=r;i+=a[l].first){ 73 cnt++; 74 for(int j=i;j<i+a[l].first;++j)Ans[a[j].second]=cnt; 75 } 76 } 77 cout<<"Possible"<<endl; 78 for(int i=1;i<=n;i++)cout<<Ans[i]<<' '; 79 return 0; 80 } 81 ``` 82 83 [1081C - Colorful Bricks](/contest/1081/problem/C "Avito Cool Challenge 2018") 84 85 Idea: [TLE](/profile/TLE "Legendary Grandmaster TLE") Developer: [TLE](/profile/TLE "Legendary Grandmaster TLE") 86 87 **Hint** 88 89 No hint here :) 90 91 **Solution** 92 93 Let *f*[*i*][*j*] be the ways that there're *j* bricks of a different color from its left-adjacent brick among bricks numbered 1 to *i*. Considering whether the *i*-th brick is of the same color of *i* - 1-th, we have *f*[*i*][*j*] = *f*[*i* - 1][*j*] + *f*[*i* - 1][*j* - 1](*m* - 1). *f*[1][0] = *m* and the answer is *f*[*n*][*k*]. 94 95 Also, there is a possibly easier solution. We can first choose the bricks of a different color from its left and then choose a different color to color them, so the answer can be found to be simply . 96 97 **Code1 (fjzzq2002)** 98 99 ``` 100 //quadratic 101 #include <bits/stdc++.h> 102 using namespace std; 103 const int MOD=998244353; 104 int n,m,k; 105 long long f[2005][2005]; 106 int main() 107 { 108 scanf("%d%d%d",&n,&m,&k); 109 f[1][0]=m; 110 for(int i=1;i<n;++i) 111 for(int j=0;j<=k;++j) 112 (f[i+1][j]+=f[i][j])%=MOD, 113 (f[i+1][j+1]+=f[i][j]*(m-1))%=MOD; 114 printf("%d\n",int(f[n][k])); 115 } 116 ``` 117 118 **Code2 (fjzzq2002)** 119 120 ``` 121 //linear 122 #include <bits/stdc++.h> 123 using namespace std; 124 const int MOD=998244353; 125 typedef long long ll; 126 ll fac[2333],rfac[2333]; 127 ll qp(ll a,ll b) 128 { 129 ll x=1; a%=MOD; 130 while(b) 131 { 132 if(b&1) x=x*a%MOD; 133 a=a*a%MOD; b>>=1; 134 } 135 return x; 136 } 137 int n,m,k; 138 int main() 139 { 140 scanf("%d%d%d",&n,&m,&k); 141 fac[0]=1; 142 for(int i=1;i<=n;++i) 143 fac[i]=fac[i-1]*i%MOD; 144 rfac[n]=qp(fac[n],MOD-2); 145 for(int i=n;i;--i) 146 rfac[i-1]=rfac[i]*i%MOD; 147 printf("%lld\n",m*qp(m-1,k)%MOD*fac[n-1]%MOD 148 *rfac[k]%MOD*rfac[n-1-k]%MOD); 149 } 150 ``` 151 152 [1081D - Maximum Distance](/contest/1081/problem/D "Avito Cool Challenge 2018") 153 154 Idea: [fateice](/profile/fateice "Legendary Grandmaster fateice") Developer: [fateice](/profile/fateice "Legendary Grandmaster fateice") 155 156 Sorry for the weak pretest. 157 158 **Hint** 159 160 Consider the MST of the graph. 161 162 **Solution** 163 164 Consider the minimum spanning tree formed from the *n* vertexes, we can find that the distance between two vertexes is the maximum weight of edges in the path between them in the minimum spanning tree (it's clear because of the correctness of Kruskal algorithm). 165 166 Take any minimum spanning tree and consider some edge in this spanning tree. If this edge has all special vertexes on its one side, it cannot be the answer. Otherwise, it can always contribute to the answer, since for every special vertex, we can take another special vertex on the other side of this edge. Therefore, answers for all special vertexes are the maximum weight of the edges that have special vertexes on both sides. 167 168 Besides implementing this directly, one can also run the Kruskal algorithm and maintain the number of special vertexes of each connected component in the union-find-set. Stop adding new edges when all special vertexes are connected together and the last edge added should be the answer. 169 170 **Code (fateice)** 171 172 ``` 173 #include<bits/stdc++.h> 174 #define L long long 175 #define vi vector<int> 176 #define pb push_back 177 using namespace std; 178 int n,m,t,f[100010],p; 179 bool a[100010]; 180 inline int fa(int i) 181 { 182 return f[i]==i?i:f[i]=fa(f[i]); 183 } 184 struct edge 185 { 186 int u,v,w; 187 inline void unit() 188 { 189 u=fa(u); 190 v=fa(v); 191 if(u!=v) 192 { 193 if(a[u]) 194 f[v]=u; 195 else 196 f[u]=v; 197 if(a[u] && a[v]) 198 p--; 199 if(p==1) 200 { 201 for(int i=1;i<=t;i++) 202 printf("%d ",w); 203 printf("\n"); 204 exit(0); 205 } 206 } 207 } 208 }x[100010]; 209 inline bool cmp(edge a,edge b) 210 { 211 return a.w<b.w; 212 } 213 int main() 214 { 215 int i,j; 216 scanf("%d%d%d",&n,&m,&t); 217 p=t; 218 for(i=1;i<=t;i++) 219 { 220 scanf("%d",&j); 221 a[j]=1; 222 } 223 for(i=1;i<=m;i++) 224 scanf("%d%d%d",&x[i].u,&x[i].v,&x[i].w); 225 sort(x+1,x+m+1,cmp); 226 for(i=1;i<=n;i++) 227 f[i]=i; 228 for(i=1;i<=m;i++) 229 x[i].unit(); 230 return 0; 231 } 232 ``` 233 234 [1081E - Missing Numbers](/contest/1081/problem/E "Avito Cool Challenge 2018") 235 236 Idea: [TLE](/profile/TLE "Legendary Grandmaster TLE") Developer: [TLE](/profile/TLE "Legendary Grandmaster TLE") 237 238 **Hint** 239 240 How to solve *n* = 2? 241 242 **Solution** 243 244 Let , *x**max* = 2 × 105. 245 246 Since *x*2*i* = *s*2*i* - *s*2*i* - 1 = *t*2*i*2 - *t*2*i* - 12 ≥ (*t*2*i* - 1 + 1)2 - *t*2*i* - 12 = 2*t*2*i* - 1 + 1, so 2*t*2*i* - 1 + 1 ≤ *x**max*, *t*2*i* - 1 < *x**max*. 247 248 For every , we can precalculate all possible (*a*, *b*)s so that *x* = *b*2 - *a*2: enumerate all possible *a* , then for every *a* enumerate *b* from small to large starting from *a* + 1 and stop when *b*2 - *a*2 > *x**max*, record this (*a*, *b*) for *x* = *b*2 - *a*2. Since , then , its complexity is . 249 250 Now, we can try to find a possible *s* from left to right. Since *x*2*i* - 1 is positive, we need to ensure *t*2*i* - 2 < *t*2*i* - 1. Becuase *x*2*i* = *t*2*i*2 - *t*2*i* - 12, we can try all precalculated (*a*, *b*)s such that *x*2*i* = *b*2 - *a*2. If we have several choices, we should choose the one that *a* is minimum possible, because if the current sum is bigger, it will be harder for the remaining number to keep positive. 251 252 **Bonus:** Solve *n* ≤ 103, *x*2*i* ≤ 109. 253 254 **Bonus Hint** 255 256 *t*2*i*2 - *t*2*i* - 12 = (*t*2*i* - *t*2*i* - 1)(*t*2*i* + *t*2*i* + 1). Factor *x*2*i*. 257 258 **Code1 (fjzzq2002)** 259 260 ``` 261 #include <bits/stdc++.h> 262 using namespace std; 263 typedef long long ll; 264 typedef pair<int,int> pii; 265 int n; 266 ll sq[100099]; 267 #define S 200000 268 vector<pii> v[S+55]; 269 int main() 270 { 271 for(int i=1;i<=S;++i) 272 { 273 if(i*2+1>S) break; 274 for(int j=i+1;j*(ll)j-i*(ll)i<=S;++j) 275 v[j*(ll)j-i*(ll)i].push_back(pii(i,j)); 276 } 277 scanf("%d",&n); 278 for(int i=2;i<=n;i+=2) 279 { 280 int x; scanf("%d",&x); 281 for(auto t:v[x]) 282 if(sq[i-2]<t.first) 283 { 284 sq[i-1]=t.first,sq[i]=t.second; 285 break; 286 } 287 if(!sq[i-1]) 288 {puts("No"); return 0;} 289 } 290 puts("Yes"); 291 for(int i=1;i<=n;++i) 292 printf("%lld%c",sq[i]*(ll)sq[i]-sq[i-1] 293 *(ll)sq[i-1]," \n"[i==n]); 294 } 295 ``` 296 297 **Code2 (fjzzq2002)** 298 299 ``` 300 #include <bits/stdc++.h> 301 using namespace std; 302 typedef long long ll; 303 int n; 304 vector<int> d[200099]; 305 ll su[100099],x[100099]; 306 int main() 307 { 308 for(int i=1;i<=200000;++i) 309 for(int j=i;j<=200000;j+=i) 310 d[j].push_back(i); 311 scanf("%d",&n); 312 for(int i=2;i<=n;i+=2) 313 scanf("%lld",x+i); 314 for(int i=2;i<=n;i+=2) 315 { 316 for(auto j:d[x[i]]) 317 { 318 int a=j,b=x[i]/j; 319 if(((a+b)&1)||a>=b) continue; 320 int s1=(b-a)/2; 321 if(su[i-2]<(ll)s1*s1) 322 x[i-1]=(ll)s1*s1-su[i-2]; 323 } 324 if(x[i-1]==0) 325 { 326 puts("No"); 327 return 0; 328 } 329 su[i-1]=su[i-2]+x[i-1]; 330 su[i]=su[i-1]+x[i]; 331 } 332 puts("Yes"); 333 for(int i=1;i<=n;i++) 334 printf("%lld%c",x[i]," \n"[i==n]); 335 } 336 ``` 337 338 [1081F - Tricky Interactor](/contest/1081/problem/F "Avito Cool Challenge 2018") 339 340 Idea: [TLE](/profile/TLE "Legendary Grandmaster TLE") Developer: [fateice](/profile/fateice "Legendary Grandmaster fateice"), [TLE](/profile/TLE "Legendary Grandmaster TLE") 341 342 Yet another binary search? 343 344 **Hint** 345 346 What about parity? 347 348 **Solution** 349 350 Assuming the number of 1s changed from *a* to *b* after flipping a range of length *s*. 351 352 Let the number of 1s in the range before this flip be be *t*, then *b* - *a* = (*l* - *t*) - *t* = *s* - 2*t*, so . 353 354 So if we made a query *l*, *r*, the parities of the lengths of [1, *r*] and [*l*, *n*] are different, we can find out which one is actually flipped by parity of delta. Also if we only want [1, *r*] or [*l*, *n*] to be flipped and nothing else, we can keep querying *l*, *r* and record all the flips happened until it's the actual case (since flipping a range twice is equivalent to no flipping at all). The expected number of queries needed is 3. 355 356 **Proof for expectation** 357 358 Let *s**a*, *b* be, currently *a* ≡ the number of times [1, *r*] is flipped , *b* ≡ the number of times [*r*, *n*] is flipped , the expectation of remaining number of queries needed to complete our goal. Then *s*1, 0 = 0 (goal), we're going to find out *s*0, 0. 359 360 *s*0, 0 = (*s*0, 1 + *s*1, 0) / 2 + 1, *s*0, 1 = (*s*0, 0 + *s*1, 1) / 2 + 1, *s*1, 1 = (*s*1, 0 + *s*0, 1) / 2 + 1. 361 362 Solve this equation you'll get *s*0, 0 = 3, *s*0, 1 = 4, *s*1, 1 = 3. 363 364 Since , it's easy to arrive at such arrangements. 365 366 When , try to query (1, 1), (1, 1), (2, 2), (2, 2), (3, 3), (3, 3)...(*n*, *n*), (*n*, *n*) and use the method described above to flip [1, 1], [1, 1], [1, 2], [1, 2], [1, 3], [1, 3]...[1, *n*], [1, *n*]. Thus we'll know *s*1, *s*1 + *s*2, *s*1 + *s*2 + *s*3...*s*1 + *s*2 + ... + *s**n* and *s* becomes obvious. 367 368 When , try to query (2, *n*), (2, *n*), (1, 2), (1, 2), (2, 3), (2, 3)...(*n* - 1, *n*), (*n* - 1, *n*) and use the method described above to flip [2, *n*], [2, *n*], [1, 2], [1, 2][1, 3], [1, 3]...[1, *n*], [1, *n*]. Thus we'll know *s*2 + *s*3 + ... + *s**n*, *s*1 + *s*2, *s*1 + *s*2 + *s*3...*s*1 + *s*2 + ... + *s**n* and *s* also becomes obvious. 369 370 Also, we can flip every range only once instead of twice by recording whether every element is currently flipped or not, although it will be a bit harder to write. 371 372 **Code (fjzzq2002)** 373 374 ``` 375 #include <bits/stdc++.h> 376 using namespace std; 377 int n,ss[10005],sn=0,q[333]; 378 bool tf(int l,int r) 379 { 380 cout<<"? "<<l<<" "<<r<<endl<<flush; 381 cin>>ss[++sn]; 382 return (ss[sn]-ss[sn-1])&1; 383 } 384 int main() 385 { 386 cin>>n>>ss[0]; q[n]=ss[0]; 387 for(int i=1;i<n;++i) 388 { 389 int j=i-n%2; 390 if(j==0) 391 { 392 int t[2]={0,0},u=ss[sn]; 393 while(t[0]!=1||t[1]!=0) 394 t[tf(2,n)]^=1; 395 int v=ss[sn]; 396 q[i]=q[n]-(n-1-v+u)/2; 397 while(t[0]||t[1]) 398 t[tf(2,n)]^=1; 399 } 400 else 401 { 402 int t[2]={0,0},u=ss[sn]; 403 while(t[0]!=1||t[1]!=0) 404 t[(tf(j,i)^i)&1]^=1; 405 int v=ss[sn]; 406 q[i]=(i-v+u)/2; 407 while(t[0]||t[1]) 408 t[(tf(j,i)^i)&1]^=1; 409 } 410 } 411 cout<<"! "; 412 for(int i=1;i<=n;++i) 413 printf("%d",q[i]-q[i-1]); 414 cout<<endl<<flush; 415 } 416 ``` 417 418 [1081G - Mergesort Strikes Back](/contest/1081/problem/G "Avito Cool Challenge 2018") 419 420 Idea: [quailty](/profile/quailty "Grandmaster quailty") Developer: [fateice](/profile/fateice "Legendary Grandmaster fateice"), [TLE](/profile/TLE "Legendary Grandmaster TLE"), [sunset](/profile/sunset "Legendary Grandmaster sunset") 421 422 **Hint** 423 424 How does "merge" work? What is this "mergesort" actually doing? 425 426 **Solution** 427 428 First, consider how "merge" will work when dealing with two arbitrary arrays. Partition every array into several blocks: find all elements that are larger than all elements before them and use these elements as the start of the blocks. Then, by 'merging' we're just sorting these blocks by their starting elements. (This is because that when we decided to put the start element of a block into the result array, the remaining elements in the block will be sequentially added too since they're smaller than the start element) 429 430 Now back to the merge sort. What this "mergesort" doing is basically dividing the array into several segments (i.e. the ranges reaching the depth threshold). In every segment, the relative order stays the same when merging, so the expected number of inversions they contribute is just  (for a segment of length *l*). Again suppose every segment is divided into blocks aforementioned, we're just sorting those blocks altogether by the beginning elements. 431 432 Let's consider inversions formed from two blocks in two different segments. Say the elements forming the inversion are initially the *i*-th and *j*-th of those two segments (from left to right), then the blocks they belong start from the maximum of the first *i*-th and the first *j*-th of those two segments. Consider the maximum among these *i* + *j* numbers, if it is one of these two elements, the inversion can't be formed. The probability that the maximum is neither *i* nor *j* is , and if the maximum is chosen, there are 50% percent of odds that the order of *i* and *j* is different from that of two maximums, because these two elements' order can be changed by swapping these two elements while leaving the maximums' order unchanged. So their probability of forming an inversion is just . 433 434 Enumerate two blocks and *i* and precalculate the partial sum of reciprocals, we can calculate the expectation of inversions formed from these two blocks in *O*(*n*) time. However, there might be *O*(*n*) blocks. But there is one more property for this problem: those segments are of at most two different lengths. By considering same length pairs only once, we can get a *O*(*n*) or  solution. 435 436 **proof of two lengths** 437 438 Do an induction on *k*. 439 440 Suppose for *k* - 1 we have only segments of length *a* and *a* + 1. 441 442 If 2|*a*, let *a* = 2*t*, from 2*t* and 2*t* + 1 only segments of length *t* and *t* + 1 will be formed. 443 444 Otherwise, let *a* = 2*t* + 1, from 2*t* + 1 and 2*t* + 2 still only segments of length *t* and *t* + 1 will be formed. 445 446 **Bonus:** solve this problem when the segments' length can be arbitary and *n* ≤ 105. 447 448 **Code (fjzzq2002)** 449 450 ``` 451 #include <bits/stdc++.h> 452 using namespace std; 453 typedef long long ll; 454 #define fi first 455 #define se second 456 #define SZ 123456 457 int n,k,MOD,ts[SZ],tn=0; 458 ll inv[SZ],invs[SZ]; 459 ll qp(ll a,ll b) 460 { 461 ll x=1; a%=MOD; 462 while(b) 463 { 464 if(b&1) x=x*a%MOD; 465 a=a*a%MOD; b>>=1; 466 } 467 return x; 468 } 469 void go(int l,int r,int h) 470 { 471 if(h<=1||l==r) ts[++tn]=r-l+1; 472 else 473 { 474 int m=(l+r)>>1; 475 go(l,m,h-1); go(m+1,r,h-1); 476 } 477 } 478 map<ll,int> cnt; 479 ll calc(int a,int b) 480 { 481 ll ans=a*(ll)b%MOD; 482 for(int i=1;i<=a;++i) 483 ans-=(invs[i+b]-invs[i])*2LL,ans%=MOD; 484 return ans; 485 } 486 int main() 487 { 488 scanf("%d%d%d",&n,&k,&MOD); 489 for(int i=1;i<=max(n,2);++i) 490 inv[i]=qp(i,MOD-2), 491 invs[i]=(invs[i-1]+inv[i])%MOD; 492 go(1,n,k); ll ans=0; 493 for(int i=1;i<=tn;++i) 494 ++cnt[ts[i]],ans+=ts[i]*(ll)(ts[i]-1)/2,ans%=MOD; 495 for(auto t:cnt) 496 if(t.se>=2) 497 ans+=calc(t.fi,t.fi)*((ll)t.se*(t.se-1)/2%MOD),ans%=MOD; 498 for(auto a:cnt) 499 for(auto b:cnt) 500 if(a.fi<b.fi) 501 ans+=calc(a.fi,b.fi)*((ll)a.se*b.se%MOD),ans%=MOD; 502 ans=ans%MOD*inv[2]%MOD; 503 ans=(ans%MOD+MOD)%MOD; 504 printf("%d\n",int(ans)); 505 } 506 ``` 507 508 [1081H - Palindromic Magic](/contest/1081/problem/H "Avito Cool Challenge 2018") 509 510 Idea: [TLE](/profile/TLE "Legendary Grandmaster TLE") Developer: [TLE](/profile/TLE "Legendary Grandmaster TLE"), [sunset](/profile/sunset "Legendary Grandmaster sunset") 511 512 This problem is quite educational and we didn't expect anyone to pass. :P 513 514 **Hint** 515 516 What will be counted twice? 517 518 **Solution** 519 520 Warning: This editorial is probably new and arcane for ones who are not familiar with this field. If you just want to get a quick idea about the solution, you can skip all the proofs (they're wrapped in spoiler tags). 521 522 Some symbols: All indices of strings start from zero. *x**R* stands for the reverse of string *x*. (e.g. '*abc*'*R* = '*cba*'), *xy* stands for concatenation of *x* and *y*. (e.g. *x* = '*a*', *y* = '*b*', *xy* = '*ab*'), *x**a* stands for concatenation of *a* copies of *x* (e.g. *x* = '*ab*', *x*2 = '*abab*'). *x*[*a*, *b*] stands for the substring of *x* starting and ending from the *a*-th and *b*-th character. (e.g. '*abc*'[1, 2] = '*bc*') 523 524 Border of *x*: strings with are common prefix & suffix of *x*. Formally, *x* has a border of length *t* (*x*[0, *t* - 1]) iff *x**i* = *x*|*x*| - *t* + *i* (). 525 526 Period of *x*: *x* has a period of length *t* iff *x**i* = *x**i* + *t* (0 ≤ *i* < |*x*| - *t*). When *t*||*x*| we also call *t* a full period. From the formulas it's easy to see *x* has a period of length *t* iff *x* has a border of length |*x*| - *t*. () 527 528 Power: *x* is a power iff the minimum full period of *x* isn't |*x*|. e.g. abab is a power. 529 530 Lemma 1 (weak periodicity lemma): if *p* and *q* are periods of *s*, *p* + *q* ≤ |*s*|, *gcd*(*p*, *q*) is also a period of *s*. 531 532 **Proof** 533 534 Suppose *p* < *q*, *d* = *q* - *p*. 535 536 If |*s*| - *q* ≤ *i* < |*s*| - *d*, *s**i* = *s**i* - *p* = *s**i* + *d*. 537 538 If 0 ≤ *i* < |*s*| - *q*, *s**i* = *s**i* + *q* = *s**i* + *q* - *p* = *s**i* + *d*. 539 540 So *q* - *p* is also a period. Using Euclid algorithm we can get *gcd*(*p*, *q*) is a period. 541 542 Lemma 2: Let *S* be the set of period lengths ≤ |*s*| / 2 of *s*, if *S* is non-empty, . 543 544 **Proof** 545 546 Let *min* *S* = *v*, since *v* + *u* ≤ |*s*|, *gcd*(*v*, *u*) is also a valid period, so *gcd*(*v*, *u*) ≥ *v*, *v*|*u*. 547 548 Let *border*(*x*) be the longest (not-self) border of *x*. e.g. *border*('*aba*') = '*a*', *border*('*ab*') = ". 549 550 If *x* is a palindrome, its palindromic prefix and suffix must be its border. Therefore, its (not-self) longest palindromic prefix (suffix) is *border*(*x*). 551 552 **Proof** 553 554 Let |*x*| = *a*, *x* has a border of length *b* iff *x**i* = *x**a* - *b* + *i* (), *x* has a palindromic prefix of length *b* iff *x**i* = *x**b* - 1 - *i* (). Since *x**i* = *x**a* - 1 - *i*, they are just the same. 555 556 If *S* = *pq*, *p* and *q* are palindromic and non-empty, we call (*p*, *q*) a palindromic decomposition of *S*. If *S* = *pq*, *p* and *q* are palindromic, *q* is non-empty (*p* can be empty) we call (*p*, *q*) a non-strict palindromic decomposition of *S*. 557 558 Lemma 3: if *S* = *x*1 *x*2 = *y*1 *y*2 = *z*1 *z*2, |*x*1| < |*y*1| < |*z*1|, *x*2, *y*1, *y*2, *z*1 are palindromic and non-empty, then *x*1 and *z*2 are also palindromic. 559 560 **Proof** 561 562 Let *z*1 = *y*1 *v*. 563 564 *v**R* is a suffix of *y*2, also a suffix of *x*2. So *v* is a prefix of *x*2, then *x*1*v* is a prefix of *z*1. 565 566 Since *y*1 is a palindromic prefix of *z*1, *z*1 = *y*1 *v*, |*v*| is a period of *z*1. Since *x*1*v* is a prefix, so |*v*| is also a period of *x*1 *v*. 567 568 Suppose *t* be some arbitary large number (you can think of it as ∞), then *x*1 is a suffix of *v**t*. 569 570 Since *v**R* is prefix of *z*1, *x*1 is a prefix of (*v**R*)*t*. So *x*1*R* is a suffix of *v**t*, then *x*1 = *x*1*R*, so *x*1 is palindromic. *z*2 is palindromic similarly. 571 572 Lemma 4: Suppose *S* has some palindromic decomposition. Let the longest palindromic prefix of *S* be *a*, *S* = *ax*, longest palindromic suffix of *S* be *b*, *S* = *yb*. At least one of *x* and *y* is palindromic. 573 574 **Proof** 575 576 If none of them are palindromic, let *S* = *pq* be a valid palindromic decomposition of *S*, then *S* = *yb* = *pq* = *ax*, by Lemma 3, contradiction. 577 578 Lemma 5: *S* = *p*1 *q*1 = *p*2 *q*2 (|*p*1| < |*p*2|, *p*1, *q*1, *p*2, *q*2 are palindromic, *q*1 and *q*2 are non-empty), then *S* is a power. 579 580 **Proof** 581 582 We prove this by proving *gcd*(|*p*2| - |*p*1|, |*S*|) is a period. 583 584 Let |*S*| = *n*, |*p*2| - |*p*1| = *t*. 585 586 Because *p*1 is a palindromic prefix of *p*2, *t* is a period of *p*2. Similarly *t* is a period of *q*1. Since they have a common part of length *t* (namely *S*[*p*1, *p*2 - 1]), *t* is a period of *S*. So *t* is a period of *S*. 587 588 For , *s**x* = *s*|*p*2| - 1 - *x* = *s**n* - 1 + |*p*1| - (|*p*2| - 1 - *x*) = *s**n* - *t* + *x* (first two equations are because *p*2 and *q*1 and palindromic). So *n* - *t* is also a period of *S*. 589 590 Since *t* + *n* - *t* = *n*, *gcd*(*t*, *n* - *t*) = *gcd*(*t*, *n*) is also a period of *S*. (weak periodicity lemma) 591 592 Lemma 6: Let *S* = *p*1 *q*1 = *p*2 *q*2 = ... = *p**t* *q**t* be all non-strict palindromic decompositions of *S*, *h* be the minimum full period of *S*. When *t* ≠ 0, *t* = |*S*| / *h*. 593 594 **Proof** 595 596 From Lemma 5, it's clear that *h* = |*S*| iff *t* = 1. In the following *t* ≥ 2 is assumed. 597 598 Let α = *S*[0, *h* - 1], because α is not a power (otherwise *s* will have smaller full period), α has at most one non-strict palindromic decomposition (from Lemma 5). 599 600 Let *S* = *pq* be any non-strict palindromic decomposition, then *max*(|*p*|, |*q*|) ≥ *h*. When |*p*| ≥ *h*, α = *p*[0, *h* - 1], so , then  is palindromic. Similarly  is also palindromic. When |*q*| ≥ *h* similar arguments can be applied. Therefore,  and  is a non-strict palindromic decomposition of α. 601 602 Therefore, α has a non-strict palindromic decomposition. Let its only non-strict palindromic decomposition be α[0, *g* - 1] and α[*g*, *h* - 1]. Therefore, every *p**i* must satisfy , so *t* ≤ |*s*| / *h*. Also, these all |*s*| / *h* decompositions can be obtained. 603 604 Lemma 7: Let *S* = *p*1 *q*1 = *p*2 *q*2 = ... = *p**t* *q**t* be all non-strict palindromic decompositions of *S*. (|*p**i*| < |*p**i* + 1|) For every , at least one of *p**i* = *border*(*p**i* + 1) and *q**i* + 1 = *border*(*q**i*) is true. 605 606 **Proof** 607 608 Instead of proving directly, we first introduce a way to compute all decompositions. 609 610 Let the longest palindromic prefix of *S* be *a* (*a* ≠ *S*), *S* = *ax*, longest palindromic suffix of *S* be *b* (it may be *S*), *S* = *yb*. 611 612 If *x* = *b* obviously *S* = *ab* is the only way to decompose. 613 614 If *S* = *pq* and *p* ≠ *a*, *q* ≠ *b*, *p* and *q* are palindromic, by Lemma 3 we have *x*, *y* are also palindromic. 615 616 So if neither *x* or *y* is palindromic, then *S* can't be composed to two palindromes. 617 618 If exactly one of *x* and *y* is palindromic, it's the only way to decompose *S*. 619 620 If both of them are palindromic, we can then find the second-longest non-self palindromic prefix of *S*: *c*. Let *S* = *cz*, if *z* is not palindromic or *c* = *y*, then *S* = *ax* = *yb* are the only non-strict palindromic decompositions. Otherwise, we can find all palindromic suffix of |*S*| whose lengths between |*z*| and |*b*|, their prefixes must also be palindromic (using Lemma 3 for *ax* and *cz*), then *S* = *ax* = *cz* = ... = *yb* (other palindromic suffixes and their corresponding prefixes are omitted) 621 622 Back to the proof of Lemma 7, the only case we need to prove now is *S* = *ax* = *yb*. Suppose the claim is incorrect, let *p* = *border*(*a*), *s* = *border*(*y*), *S* = *ax* = *pq* = *rs* = *yb*, (|*a*| > |*p*| > |*y*|, |*a*| > |*r*| > |*y*|, *p* and *s* are palindromic) 623 624 Continuing with the proof of Lemma 6, since *t* = 2, *S* = α2. If |*p*| ≥ |α|, , so *q* would also be palindromic, contradiction. Therefore, |*p*| < |α| and similarly |*s*| < |α|. Let α = *pq*' = *r*'*s* and the non-strict palindromic decomposition of α be α = βθ. Since α = *pq*' = βθ = *r*'*s*, by Lemma 3 *q*' and *r*' should also be palindromic, contradiction. 625 626 Lemmas are ready, let's start focusing on this problem. A naive idea is to count the number of palindromes in *A* and in *B*, and multiply them. This will obviously count a string many times. By Lemma 7, suppose *S* = *xy*, to reduce counting, we can check if using *border*(*x*) or *border*(*y*) to replace *x* or *y* can also achieve *S*. If any of them do, reduce the answer by 1, then we're done. 627 628 So for a palindromic string *x* in *A*, we want to count strings that are attainable from both *x* and *border*(*x*) and subtract from the answer. Finding *x* and *border*(*x*) themselves can be simply done by the palindromic tree. 629 630 Let *x* = *border*(*x*)*w*, we want to count *T*s in *B* that *T* = *wS* and both *T* and *S* are palindromic. Since |*w*| is the shortest period of *x*, *w* can't be a power. 631 632 If |*w*| > |*S*|, *w* = *S* + *U*. *S* are *U* are both palindromes. Since *w* is not a power, it can be decomposed to be two palindromes in at most one way (Lemma 5). We can find that only way (by checking maximal palindromic suffix & prefix) and use hashing to check if it exists in *B*. 633 634 If |*w*| ≤ |*S*|, if *S* is not maximum palindromic suffix of *T*, *w* must be a power (Lemma 2), so we only need to check maximum palindromic suffixes (i.e. *S* = *border*(*T*)). 635 636 We need to do the similar thing to *y*s in *B*, then adding back both attainable from *border*(*x*) and *border*(*y*). Adding back can be done in a similar manner, or directly use hashing to find all matching *w* s. 637 638 Finding maximal palindromic suffix and prefix of substrings can be done by binary-lifting on two palindromic trees (one and one reversed). Let *up**i*, *j* be the resulting node after jumping through fail links for 2*j* steps from node *i*. While querying maximal palindromic suffix for *s*[*l*, *r*], find the node corresponding to the maximal palindromic suffix of *s*[1, *r*] (this can be stored while building palindromic tree). If it fits into *s*[*l*, *r*] we're done. Otherwise, enumerate *j* from large to small and jump 2*j* steps (with the help of *up*) if the result node is still unable to fit into *s*[*l*, *r*], then jump one more step to get the result. 639 640 **Code (yjq_naiive)** 641 642 ``` 643 #include <bits/stdc++.h> 644 645 using namespace std; 646 647 const int N = 234567; 648 const int LOG = 18; 649 const int ALPHA = 26; 650 const int base = 2333; 651 const int md0 = 1e9 + 7; 652 const int md1 = 1e9 + 9; 653 654 struct hash_t { 655 int hash0, hash1; 656 657 hash_t(int hash0 = 0, int hash1 = 0):hash0(hash0), hash1(hash1) { 658 } 659 660 hash_t operator + (const int &x) const { 661 return hash_t((hash0 + x) % md0, (hash1 + x) % md1); 662 }; 663 664 hash_t operator * (const int &x) const { 665 return hash_t((long long)hash0 * x % md0, (long long)hash1 * x % md1); 666 } 667 668 hash_t operator + (const hash_t &x) const { 669 return hash_t((hash0 + x.hash0) % md0, (hash1 + x.hash1) % md1); 670 }; 671 672 hash_t operator - (const hash_t &x) const { 673 return hash_t((hash0 + md0 - x.hash0) % md0, (hash1 + md1 - x.hash1) % md1); 674 }; 675 676 hash_t operator * (const hash_t &x) const { 677 return hash_t((long long)hash0 * x.hash0 % md0, (long long)hash1 * x.hash1 % md1); 678 } 679 680 long long get() { 681 return (long long)hash0 * md1 + hash1; 682 } 683 } ha[N], hb[N], power[N]; 684 685 struct palindrome_tree_t { 686 int n, total, p[N], pos[N], value[N], parent[N], go[N][ALPHA], ancestor[LOG][N]; 687 char s[N]; 688 689 palindrome_tree_t() { 690 parent[0] = 1; 691 value[1] = -1; 692 total = 1; 693 p[0] = 1; 694 } 695 696 int extend(int p, int w, int n) { 697 while (s[n] != s[n - value[p] - 1]) { 698 p = parent[p]; 699 } 700 if (!go[p][w]) { 701 int q = ++total, k = parent[p]; 702 while (s[n] != s[n - value[k] - 1]) { 703 k = parent[k]; 704 } 705 value[q] = value[p] + 2; 706 parent[q] = go[k][w]; 707 go[p][w] = q; 708 pos[q] = n; 709 } 710 return go[p][w]; 711 } 712 713 void init() { 714 for (int i = 1; i <= n; ++i) { 715 p[i] = extend(p[i - 1], s[i] - 'a', i); 716 } 717 for (int i = 0; i <= total; ++i) { 718 ancestor[0][i] = parent[i]; 719 } 720 for (int i = 1; i < LOG; ++i) { 721 for (int j = 0; j <= total; ++j) { 722 ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]]; 723 } 724 } 725 } 726 727 int query(int r, int length) { 728 r = p[r]; 729 if (value[r] <= length) { 730 return value[r]; 731 } 732 for (int i = LOG - 1; ~i; --i) { 733 if (value[ancestor[i][r]] > length) { 734 r = ancestor[i][r]; 735 } 736 } 737 return value[parent[r]]; 738 } 739 740 bool check(int r, int length) { 741 r = p[r]; 742 for (int i = LOG - 1; ~i; --i) { 743 if (value[ancestor[i][r]] >= length) { 744 r = ancestor[i][r]; 745 } 746 } 747 return value[r] == length; 748 } 749 } A, B, RA, RB; 750 751 map<long long, int> fa, fb, ga, gb; 752 long long answer; 753 char a[N], b[N]; 754 int n, m; 755 756 hash_t get_hash(hash_t *h, int l, int r) { 757 return h[r] - h[l - 1] * power[r - l + 1]; 758 } 759 760 int main() { 761 #ifdef wxh010910 762 freopen("input.txt", "r", stdin); 763 #endif 764 scanf("%s %s", a + 1, b + 1); 765 n = strlen(a + 1); 766 m = strlen(b + 1); 767 A.n = RA.n = n; 768 B.n = RB.n = m; 769 for (int i = 1; i <= n; ++i) { 770 A.s[i] = RA.s[n - i + 1] = a[i]; 771 ha[i] = ha[i - 1] * base + a[i]; 772 } 773 for (int i = 1; i <= m; ++i) { 774 B.s[i] = RB.s[m - i + 1] = b[i]; 775 hb[i] = hb[i - 1] * base + b[i]; 776 } 777 power[0] = hash_t(1, 1); 778 for (int i = 1; i <= max(n, m); ++i) { 779 power[i] = power[i - 1] * base; 780 } 781 A.init(); 782 B.init(); 783 RA.init(); 784 RB.init(); 785 answer = (long long)(A.total - 1) * (B.total - 1); 786 for (int i = 2; i <= A.total; ++i) { 787 ++fa[get_hash(ha, A.pos[i] - A.value[i] + 1, A.pos[i]).get()]; 788 int p = A.parent[i]; 789 if (p < 2) { 790 continue; 791 } 792 int l = A.pos[i] - (A.value[i] - A.value[p]) + 1, r = A.pos[i]; 793 if (A.value[i] <= A.value[p] << 1) { 794 ++ga[get_hash(ha, l, r).get()]; 795 } 796 } 797 for (int i = 2; i <= B.total; ++i) { 798 ++fb[get_hash(hb, B.pos[i] - B.value[i] + 1, B.pos[i]).get()]; 799 int p = B.parent[i]; 800 if (p < 2) { 801 continue; 802 } 803 int l = B.pos[i] - B.value[i] + 1, r = B.pos[i] - B.value[p]; 804 if (B.value[i] <= B.value[p] << 1) { 805 ++gb[get_hash(hb, l, r).get()]; 806 } 807 } 808 for (int i = 2; i <= A.total; ++i) { 809 int p = A.parent[i]; 810 if (p < 2) { 811 continue; 812 } 813 int l = A.pos[i] - (A.value[i] - A.value[p]) + 1, r = A.pos[i]; 814 long long value = get_hash(ha, l, r).get(); 815 if (gb.count(value)) { 816 answer -= gb[value]; 817 } 818 int longest_palindrome_suffix = A.query(r, r - l + 1); 819 if (longest_palindrome_suffix == r - l + 1) { 820 continue; 821 } 822 if (RA.check(n - l + 1, r - l + 1 - longest_palindrome_suffix)) { 823 int length = r - l + 1 - longest_palindrome_suffix; 824 if (fb.count(get_hash(ha, l, l + length - 1).get()) && fb.count((get_hash(ha, l, r) * power[length] + get_hash(ha, l, l + length - 1)).get())) { 825 --answer; 826 } 827 continue; 828 } 829 int longest_palindrome_prefix = RA.query(n - l + 1, r - l + 1); 830 if (A.check(r, r - l + 1 - longest_palindrome_prefix)) { 831 int length = longest_palindrome_prefix; 832 if (fb.count(get_hash(ha, l, l + length - 1).get()) && fb.count((get_hash(ha, l, r) * power[length] + get_hash(ha, l, l + length - 1)).get())) { 833 --answer; 834 } 835 continue; 836 } 837 } 838 for (int i = 2; i <= B.total; ++i) { 839 int p = B.parent[i]; 840 if (p < 2) { 841 continue; 842 } 843 int l = B.pos[i] - B.value[i] + 1, r = B.pos[i] - B.value[p]; 844 long long value = get_hash(hb, l, r).get(); 845 if (ga.count(value)) { 846 answer -= ga[value]; 847 } 848 int longest_palindrome_suffix = B.query(r, r - l + 1); 849 if (longest_palindrome_suffix == r - l + 1) { 850 continue; 851 } 852 if (RB.check(m - l + 1, r - l + 1 - longest_palindrome_suffix)) { 853 int length = longest_palindrome_suffix; 854 if (fa.count(get_hash(hb, r - length + 1, r).get()) && fa.count((get_hash(hb, r - length + 1, r) * power[r - l + 1] + get_hash(hb, l, r)).get())) { 855 --answer; 856 } 857 continue; 858 } 859 int longest_palindrome_prefix = RB.query(m - l + 1, r - l + 1); 860 if (B.check(r, r - l + 1 - longest_palindrome_prefix)) { 861 int length = r - l + 1 - longest_palindrome_prefix; 862 if (fa.count(get_hash(hb, r - length + 1, r).get()) && fa.count((get_hash(hb, r - length + 1, r) * power[r - l + 1] + get_hash(hb, l, r)).get())) { 863 --answer; 864 } 865 continue; 866 } 867 } 868 for (int i = 2; i <= A.total; ++i) { 869 int p = A.parent[i]; 870 if (p < 2) { 871 continue; 872 } 873 int l = A.pos[i] - (A.value[i] - A.value[p]) + 1, r = A.pos[i]; 874 if (A.value[i] > A.value[p] << 1) { 875 ++ga[get_hash(ha, l, r).get()]; 876 } 877 } 878 for (int i = 2; i <= B.total; ++i) { 879 int p = B.parent[i]; 880 if (p < 2) { 881 continue; 882 } 883 int l = B.pos[i] - B.value[i] + 1, r = B.pos[i] - B.value[p]; 884 if (B.value[i] > B.value[p] << 1) { 885 ++gb[get_hash(hb, l, r).get()]; 886 } 887 } 888 for (auto p : ga) { 889 answer += (long long)p.second * gb[p.first]; 890 } 891 printf("%lld\n", answer); 892 return 0; 893 } 894 ``` 895 896 Hope you enjoyed the round! See you next time!