codeforces-scrape

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

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 ![](https://espresso.codeforces.com/3d5314c1a4331427610c77504be9ab70bbdae24a.png), *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 ![](https://espresso.codeforces.com/ea56a677f48f7e7ab9727bc15d043206d71b62ed.png) 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 ![](https://espresso.codeforces.com/712e4de69a7d96cee37b3627da168e5b507664fa.png).
     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 ![](https://espresso.codeforces.com/2a8da75b8741fc27a224f99622f117cfd8b4ed89.png), *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 ![](https://espresso.codeforces.com/412083ad375a58908af24bcf9b69334a8c779257.png), we can precalculate all possible (*a*, *b*)s so that *x* = *b*2 - *a*2: enumerate all possible *a* ![](https://espresso.codeforces.com/5e693d8ef436ba860832cb6bce422a82f9218ae6.png), 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 ![](https://espresso.codeforces.com/9d45d0c9c8de41d389b95effbb790946eb3ec342.png), then ![](https://espresso.codeforces.com/19c9c5c692744be201f294faf803311f2aff587c.png), its complexity is ![](https://espresso.codeforces.com/9e312081b49f4588c11ba41443c6cc4bc68c72fb.png).
    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 ![](https://espresso.codeforces.com/9eebab71564fea798e52c3f476ee8159b2a6263f.png).
    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 ![](https://espresso.codeforces.com/a135055b720bab043a1c88ce564dcee6e8695362.png), *b* ≡  the number of times [*r*, *n*] is flipped ![](https://espresso.codeforces.com/a135055b720bab043a1c88ce564dcee6e8695362.png), 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 ![](https://espresso.codeforces.com/dce8b480e25313552f2025d9a6c8305b014be064.png), it's easy to arrive at such arrangements.
    365 
    366 When ![](https://espresso.codeforces.com/bdbeb9933fd5a53eae7de0226bfc38942dee1b69.png), 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 ![](https://espresso.codeforces.com/4e08aae15ecf5b990ad265bd3c27e271f63cf3dc.png), 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 ![](https://espresso.codeforces.com/a21c72bd7fc3e5e5f58be330a0f9d439e7df1ac4.png) (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 ![](https://espresso.codeforces.com/b8b8b5954e8bb5d204e8c994c0cd8af70108ff5c.png), 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 ![](https://espresso.codeforces.com/6bc436be8b02b7edb0c07cb626e2b3afc7e19eb7.png).
    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 ![](https://espresso.codeforces.com/49d24101dcdd81f4a7959288cb2ee875414fdc6a.png) 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* (![](https://espresso.codeforces.com/60c4300471a97d01c8acc26c1c219e42d0a7d18a.png)).
    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*. (![](https://espresso.codeforces.com/83125b04df60d7e97ff6f22d81548ed289c1bfac.png))
    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, ![](https://espresso.codeforces.com/ba9e954f7c6a07746a4a2762f160bc2d5b038da3.png).
    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* (![](https://espresso.codeforces.com/f6662567fc2bbb7e2d5b697adfff4be20324dab2.png)), *x* has a palindromic prefix of length *b* iff *x**i* = *x**b* - 1 - *i* (![](https://espresso.codeforces.com/f6662567fc2bbb7e2d5b697adfff4be20324dab2.png)). 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 ![](https://espresso.codeforces.com/efb161bbe2ff1bc9611814f49964b7f2b9368901.png), *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 ![](https://espresso.codeforces.com/bdb125e46621aa09038fd7f7b33fa201dc906b01.png), then ![](https://espresso.codeforces.com/e6b1b70b33dde24d2fdddd9db54544cd217394d0.png) is palindromic. Similarly ![](https://espresso.codeforces.com/905b40ceab151f665bafaebc60253224ae8b61b6.png) is also palindromic. When |*q*| ≥ *h* similar arguments can be applied. Therefore, ![](https://espresso.codeforces.com/e6b1b70b33dde24d2fdddd9db54544cd217394d0.png) and ![](https://espresso.codeforces.com/905b40ceab151f665bafaebc60253224ae8b61b6.png) 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 ![](https://espresso.codeforces.com/4591639e6301843b2ac41c4366cd2b27fae55f3c.png), 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 ![](https://espresso.codeforces.com/970d98273dae3d763a47e45a890f7dfb238baf82.png), 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*| ≥ |α|, ![](https://espresso.codeforces.com/e526f8a09f4315689ebe1ff34c2a0cf798189b87.png), 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!