1047.md (26584B)
1 Source: https://codeforces.com/blog/entry/61993 2 3 Hi, here is the editorial. Sorry for a long waiting. 4 5 Have you enjoyed this round? I hope so. I know there are many things not so good and making some people unhappy :( I'm very sorry about that. Since this is my first round, I have many things not taken into consideration or done badly. I will try to improve them if I have my next round (I hope). 6 7 Let's talk about the problems. The problems are mainly prepared by me, [ditoly](/profile/ditoly "Grandmaster ditoly"), which can be seen in D1D as "Little D". Also, my friends [ACMLCZH](/profile/ACMLCZH "Candidate Master ACMLCZH") ("Little C") and [FallDream](/profile/FallDream "Grandmaster FallDream") ("Mr. F", I don't know whether this name can explain Chinese word "F大爷" well, maybe "Master F" is better?) provided great helps. The statements are mainly written by me (with the help of [300iq](/profile/300iq "International Grandmaster 300iq") and [cyand1317](/profile/cyand1317 "Grandmaster cyand1317") and some others, thanks!). My English is not so good, so it's frequent that I just understand the problem but other people get AC :( So I try to explain the problems in short statements. Are you not the same with me in this round :p? By the way, why Little C loves "3" so much? He said, it's because C is the 3rd letter in alphabet :D 8 9 [Div. 2 A — Little C loves 3 I](//codeforces.com/contest/1047/problem/A) 10 11 Problem Author: [ditoly](/profile/ditoly "Grandmaster ditoly") 12 13 This problem is set by Little C at first, and it's a problem about "Tic-Tac-Toe" for D2B. But after discussion with the coordinator, we thought it's just a implement problem and not so interesting. So I came up with a new problem as you saw. 14 15 **Solution** 16 17 If *n* - 2 is not a multiple of 3, *a* = 1, *b* = 1, *c* = *n* - 2 is OK. 18 19 Otherwise, *a* = 1, *b* = 2, *c* = *n* - 3 is OK. 20 21 **My Code** 22 23 ``` 24 #include<bits/stdc++.h> 25 using namespace std; 26 int main() 27 { 28 int n; 29 scanf("%d",&n); 30 if((n-2)%3)printf("1 1 %d",n-2); 31 else printf("1 2 %d",n-3); 32 } 33 ``` 34 35 [Div. 2 B — Cover Points](//codeforces.com/contest/1047/problem/B) 36 37 Problem Author: [ditoly](/profile/ditoly "Grandmaster ditoly") and [ACMLCZH](/profile/ACMLCZH "Candidate Master ACMLCZH") 38 39 This is the former D2A :) After discussion with the coordinator, we thought this problem is too difficult for beginners so it became D2B. What do you think of it? 40 41 **Solution** 42 43 To cover a point (*x**i*, *y**i*), the length of the shorter side of the triangle should be at least *x**i* + *y**i*. 44 45 So the answer is *max*(*x**i* + *y**i*). 46 47 **My Code** 48 49 ``` 50 #include<bits/stdc++.h> 51 using namespace std; 52 int main() 53 { 54 int n,x,y,ans=0; 55 scanf("%d",&n); 56 while(n--)scanf("%d%d",&x,&y),ans=max(ans,x+y); 57 printf("%d",ans); 58 } 59 ``` 60 61 [Div. 1 A — Enlarge GCD](https://codeforces.com/contest/1034/problem/A) 62 63 Problem Author: [FallDream](/profile/FallDream "Grandmaster FallDream") 64 65 In the initial version, it's satisfied that the GCD of all the given integers is 1. So maybe it will be easier to find the standard solution? 66 67 **Solution** 68 69 First we divide all numbers by GCD of them. Then we should find a subset with maximum number of integers GCD of which is bigger than 1. 70 71 We can enumerate a prime *p* that GCD of the remaining integers can be divided by. And the number of integers can be divided by *p* is the maximum size of the subset. 72 73 We can use Sieve of Euler to factor all integers in  time. Then we find the prime that can divide most integers. The answer is *n* minus the number of integers can be divided by this prime. If all integers are 1 (after dividing their GCD), there is no solution. 74 75 **My Code** 76 77 ``` 78 #include<bits/stdc++.h> 79 using namespace std; 80 #define MN 300000 81 #define MX 15000000 82 int a[MN+5],u[MX+5],p[MX+5],pn,s[MX+5]; 83 int gcd(int x,int y){return y?gcd(y,x%y):x;} 84 int main() 85 { 86 int n,i,j,g,x,ans=0; 87 for(i=2;i<=MX;++i) 88 { 89 if(!u[i])u[i]=p[++pn]=i; 90 for(j=1;i*p[j]<=MX;++j){u[i*p[j]]=p[j];if(i%p[j]==0)break;} 91 } 92 scanf("%d",&n); 93 for(g=0,i=1;i<=n;++i)scanf("%d",&a[i]),g=gcd(g,a[i]); 94 for(i=1;i<=n;++i)for(j=a[i]/g;j>1;)for(++s[x=u[j]];u[j]==x;)j/=u[j]; 95 for(i=1;i<=MX;++i)ans=max(ans,s[i]); 96 printf("%d",ans?n-ans:-1); 97 } 98 ``` 99 100 **About the Constraints** 101 102 It seems that many people is unsatisfied with the constraints of this problem :( I'm sorry very very much! 103 104 Now I'll explain the reason of the constraints. 105 106 First, about the main idea of this problem, both [FallDream](/profile/FallDream "Grandmaster FallDream") and me thought it's only the prime factors must be considered (Certainly, when the GCD of all the integers is 1). 107 108 So I think solutions which consider each prime should be able to pass but which consider all the factors should not. 109 110 In the beginning, the maximum of *n* is 5·105 and of *a**i* is 107, and the time limit is also 1s. My solution will run for less than 0.4s. 111 112 Then the tester [cyand1317](/profile/cyand1317 "Grandmaster cyand1317") submit a solution with  time (Let *A* denote the maximum of *a**i*) which count the number of multiples for each number. His solution got TLE but just ran for about 1s. I think this solution do not use the main idea, so should be not able to pass. Then I increased the limit of *a**i* a little to 1.5·107 so that his solution should run for about 1.5s. Since the solution with  time should use the main idea and I think it should be able to pass, I do not increase it too much. And according to [cyand1317](/profile/cyand1317 "Grandmaster cyand1317")'s suggestion, the time limit is unfriendly to some languages, I reduced *n* to 3·105 so that there will be less constant requirement for standard solutions. Then my solution will run for about 0.3s and  solutions will run for about 0.6s (and it seems that running on codeforces is a little bit faster than running on polygon). I thought this result is acceptable so it became the final constraints. 113 114 If the constraints make you feel unfriendly, I'm sorry very very much once again! There are so many conditions I should consider that I worried about it for a long time and do not receive a good result finally :( And I did not notice that the brute force can care only primes not bigger than  so many of them got AC :( 115 116 Also sorry for too weak pretests. 117 118 Hope you can forgive me for my mistakes. 119 120 [Div. 1 B — Little C Loves 3 II](https://codeforces.com/contest/1034/problem/B) 121 122 Problem Author: [ACMLCZH](/profile/ACMLCZH "Candidate Master ACMLCZH") 123 124 When [ACMLCZH](/profile/ACMLCZH "Candidate Master ACMLCZH") first told me this problem and the solution, I hacked him because of his mistake :p 125 126 **Solution** 127 128 Following the rules in the problem, the 1 × 6, 2 × 4, 2 × 5 and 3 × 4 grids full of chessmen can be easily constructed. 129 130 **How to construct?** 131 132 Let the number denote the time when the chessman placed. 133 134 Grids of 1 × 6 : 135 136 1 2 3 1 2 3 137 138 Grids of 2 × 4 : 139 140 1 2 3 4 141 142 3 4 1 2 143 144 Grids of 2 × 5 : 145 146 1 3 2 1 5 147 148 2 4 5 3 4 149 150 Grids of 3 × 4 : 151 152 1 3 4 2 153 154 5 2 1 5 155 156 6 4 3 6 157 158 Assume that *n* ≤ *m*. Consider the following cases: 159 160 If *n* = 1, obviously the answer is . 161 162 If *n* = 2, only the 2 × 2, 2 × 3 and 2 × 7 grids cannot be completely constructed. The others can be constructed by using the 2 × 4, 2 × 5 and 2 × 6(constructed by two 1 × 6 grids) girds. 163 164 **How to prove that they cannot be constructed?** 165 166 You can write a brute force or enumerate all the possibilities by yourself. If you consider each grid from left to right and choose the grid it matched with, there are only several possible conditions. So I think it can be proved in several minutes :) 167 168 If *n* > 2, the following things we can consider: 169 170 We know that using the 2 × 4 and 3 × 4 grids we can construct the 4 × *x*(*x* > 2) grid, and using several 1 × 6 grids we can construct the 6 × *x*(*x* > 2) grid, so using the 4 × *x* and 6 × *x* grids we can construct the *x* × *y* grid while *x*, *y* > 2 and *y* is an even number. 171 172 Therefore we only need to consider the *n* × *m* grid that *n* and *m* are both odd numbers. 173 174 Since *n* × *m* is an odd integer, we can place *nm* - 1 chessmen at most, so we try to reach the maximum. 175 176 Then we can easily construct the 3 × 3, 3 × 5 and 5 × 5 grids that have only one empty grid. According to the above-mentioned conclusions, any *n* × *m* grids can be reduce to one of the three grids by using some *x* × *y*(*x* or *y* is even) grids. The maximum is reached. 177 178 **How to construct?** 179 180 Grids of 3 × 3 : 181 182 1 2 3 183 184 3 0 4 185 186 4 1 2 187 188 Grids of 3 × 5 : 189 190 1 3 4 6 7 191 192 2 5 1 0 5 193 194 3 4 2 7 6 195 196 Grids of 5 × 5 : 197 198 1 2 3 1 2 199 200 3 4 5 6 4 201 202 5 6 7 8 9 203 204 10 8 9 12 7 205 206 11 12 10 11 0 207 208 It seems that the chessboard is a little bit big but you can match them arbitrarily and get correct solution with a big possibility :) 209 210 **My Code** 211 212 ``` 213 #include<bits/stdc++.h> 214 using namespace std; 215 int main() 216 { 217 int n,m; 218 scanf("%d%d",&n,&m); 219 if(n>m)swap(n,m); 220 if(n==1)printf("%d",m/6*3+max(m%6-3,0)<<1); 221 else if(n==2)printf("%d",m==2?0:m==3?4:m==7?12:m<<1); 222 else printf("%lld",1LL*n*m/2*2); 223 } 224 ``` 225 226 **How to solve this problem quickly and safely without complex proof?** 227 228 This problem is a matching problem. And we found that two grids can be matched only if they have different parities of the sum of two coordinates. So it's actually a biparite graph matching problem :) So we can calculate the answer for all small *n* and *m*. When *n* = 1 or *m* = 1, the answer is easy to get. Otherwise, we found that if *n* or *m* is big enough, the answer will be the maximum. So just keep the answers for small *n* and *m*, you will get AC easily :) 229 230 [Div. 1 C — Region Separation](https://codeforces.com/contest/1034/problem/C) 231 232 Problem Author: [ditoly](/profile/ditoly "Grandmaster ditoly") 233 234 This problem seems to be a little difficult for its position. In fact, D1C is an easier problem with dp on a tree. For some reasons, it was replaced by this problem. But I think the new problem is very interesting, isn't it? 235 236 **Solution** 237 238 First, we try to find whether it's possible to separate the kingdom into *k* regions of level-2 with the same sum of values. We calculate *S*, the sum of all the values, so each region should have sum . Let *s**i* be the sum of values in the subtree of root *i*. We consider all the cities from the leaves to the root, when a subtree *i* has sum , separating it from the tree. We find that only the *i* with  will be considered. So there should be at least *k* cities satisfying this condition. And if there exist such *k* cities, we cut the edge to their father (if it is not the root), so the size of each connected part will be multiple of . Since all the values are positive, all the connected parts have size . So we just need to count how many cities *i* with  there are. Let the equation be , where *x* is a positive integer, so *k* should be a multiple of . Now we can use a simple dp with  time to find whether it's possible to separate the kingdom into *k* regions of level-2 for all the *k*. 239 240 And it's not difficult to find that there can be *k**i* regions of level-*i* if and only if there can be *k**i* regions of level-2 and *k**i* - 1 is a factor of *k**i*. Let *f**i* be the number of plans with *i* regions of the last level, and we enumerate the factors of *i* to transform. So the total time of this solution is  (including the time to calculate the gcd). 241 242 **My Code** 243 244 ``` 245 #include<bits/stdc++.h> 246 using namespace std; 247 typedef long long ll; 248 #define MN 1000000 249 #define MOD 1000000007 250 ll s[MN+5];int f[MN+5],p[MN+5],F[MN+5]; 251 inline void rw(int&x,int y){if((x+=y)>=MOD)x-=MOD;} 252 int main() 253 { 254 int n,i,j,ans=0; 255 scanf("%d",&n); 256 for(i=1;i<=n;++i)scanf("%lld",&s[i]); 257 for(i=2;i<=n;++i)scanf("%d",&p[i]); 258 for(i=n;i>1;--i)s[p[i]]+=s[i]; 259 for(i=n;i;--i)if((s[i]=s[1]/__gcd(s[1],s[i]))<=n)++f[s[i]]; 260 for(i=n;i;--i)for(j=i;(j+=i)<=n;)f[j]+=f[i]; 261 for(F[1]=i=1;i<=n;++i)if(f[i]==i)for(rw(ans,F[j=i]);(j+=i)<=n;)rw(F[j],F[i]); 262 printf("%d",ans); 263 } 264 ``` 265 266 **Something else about this problem** 267 268 It seems that  solution can pass this problem? Some of the testers submit solutions which enumerate the multiples of  instead of keep them in an array and then use a  dp. I think its time complexity will be , but I can not prove it's a tight upper bound. I try to construct tests but get 1.5·108 times of calculation at most which their solutions should run for about 1.5s and my solution should run for about 1s. 269 270 And I could not construct tests whose answer is bigger than 109 + 7. So you may get AC even though you mistake the modulo number or do not modulo :D I guess the answer will be about  (just guess). Can someone tell me about it, please? 271 272 Lastly, about the generator, I spent a whole afternoon to write it and its length is about 4kb which seems to be longer than the total length of my code for all problems! (As you can see, my code is always a little shoter than most of people) I hope the tests are strong enough :) 273 274 [Div. 1 D — Intervals of Intervals](https://codeforces.com/contest/1034/problem/D) 275 276 Problem Author: [ditoly](/profile/ditoly "Grandmaster ditoly") and [FallDream](/profile/FallDream "Grandmaster FallDream") 277 278 A data structure problem! With a very interesting (I think) solution! But in the beginning, this problem is just asking you for the values of several intervals of intervals :( I try to improve it and come up with this new problem :) This problem seems to be a little difficult so that only [scott_wu](/profile/scott_wu "Legendary Grandmaster scott_wu") solved it, congratulations! In fact, I would like to set the scoring contribution to 2250 (so [scott_wu](/profile/scott_wu "Legendary Grandmaster scott_wu") may take the 1st place?) before the contest. But for some reasons I finally did not :( 279 280 Great thanks to [cyand1317](/profile/cyand1317 "Grandmaster cyand1317") for the revision of the tutorial. 281 282 **Solution** 283 284 First we consider how to calculate the value of an interval of intervals [*l*, *r*]. We can consider intervals in order from 1 to *n* and, for each position on the axis, maintain a timestamp denoting the last time it was covered. When the *r*-th interval is taken into consideration, the timestamps for positions [*a**r*, *b**r*] should all be updated to *r*. Right after that, the desired answer of a query [*l*, *r*] is the number of positions whose timestamp is not smaller than *l*. 285 286 We would like to, for each *r*, keep the desired answer for every *l*. To achieve this, when we change the timestamps of *k* positions from *r*' to *r*, the answers for *l* in [*r*' + 1, *r*] should each be increased by *k*. 287 288 To do it fast, we can merge consecutive positions with the same timestamp into a segment, and use a balanced tree (e.g. std::set) to maintain the segments. *O*(1) new segments appear when adding an interval, and when a segment is completely covered by later intervals, it will be deleted. By amortized analysis, the total number of balanced tree operations and the number of range modifications of answers (see above) are both *O*(*n*). We spend  time in this part. 289 290 Now we consider how to get the answer. It's obvious that we will select the *k* largest values. We can use binary search to find the minimum we finally select, i.e. we should, for several integers *x*, count how many values of [*l*, *r*] are not smaller than *x* and count the sum of these values by the way to get the answer. 291 292 For each *i*, we will select all [*l*, *i*]'s such that their interval of intervals values is not smaller than *x*. As the value of [*l*, *r*] is not smaller than [*l* + 1, *r*] or [*l*, *r* - 1], it's obvious that all *l*'s smaller than an integer *L**i* will be taken and *L**i* + 1 will be not smaller than *L**i*. Now we can iterate *i* from 1 to *n*, maintaining the sum of values of [*l*, *i*] (1 ≤ *l* < *L**i*) and the value of [*L**i*, *i*] by maintaining the difference between the answers for *l* and *l* + 1 (in this way we carry out a range increment in *O*(1) time). Similar to the sliding-window method, we try to increase *L**i* when *i* changes to *i* + 1. Therefore, we spend *O*(*n*) time for each *x* we check with. 293 294 Summing everything up, the total time complexity of this problem is . 295 296 **My Code** 297 298 ``` 299 #include<bits/stdc++.h> 300 using namespace std; 301 #define MN 300000 302 #define p make_pair 303 #define pb push_back 304 #define A first 305 #define B second 306 set< pair<int,int> > st; 307 set< pair<int,int> >::iterator it,tt; 308 vector< pair<int,int> > v[MN+5]; 309 int f[MN+5]; 310 int main() 311 { 312 int n,m,i,j,k,l,r,x,X,t2;long long s1,s2,S1,S2,t1; 313 scanf("%d%d",&n,&m); 314 st.insert(p(1,0));st.insert(p(1e9,0)); 315 for(i=1;i<=n;++i) 316 { 317 scanf("%d%d",&l,&r); 318 tt=(it=st.upper_bound(p(l,n)))--; 319 v[i].pb(p(x=it->B,it->A-tt->A)); 320 if(it->A<l)v[i].pb(p(x,l-it->A)); 321 else st.erase(it); 322 v[i].pb(p(i,r-l));st.insert(p(l,i)); 323 while(tt->A<r)it=tt++,v[i].pb(p(x=it->B,it->A-tt->A)),st.erase(it); 324 if(tt->A>r)v[i].pb(p(x,tt->A-r)),st.insert(p(r,x)); 325 } 326 for(l=1,r=1e9;l<=r;) 327 { 328 x=l+r>>1; 329 memset(f,0,sizeof(f)); 330 for(i=j=1,s1=s2=t1=t2=0;i<=n;++i) 331 { 332 for(k=0;k<v[i].size();++k) 333 if(v[i][k].A<j)t1+=1LL*v[i][k].A*v[i][k].B; 334 else t1+=1LL*(j-1)*v[i][k].B,t2+=v[i][k].B,f[v[i][k].A]+=v[i][k].B; 335 while(j<=i&&t2>=x)t1+=t2,t2-=f[j++]; 336 s1+=t1;s2+=j-1; 337 } 338 if(s2>=m)X=x,S1=s1,S2=s2,l=x+1;else r=x-1; 339 } 340 printf("%lld",S1-(S2-m)*X); 341 } 342 ``` 343 344 [Div. 1 E — Little C Loves 3 III](https://codeforces.com/contest/1034/problem/E) 345 346 Problem Author: [ditoly](/profile/ditoly "Grandmaster ditoly") 347 348 A common, artful, interesting solution for subset convolutions! Even though it can solve with modulo *p* which *p* is a small integer now, I can solve with modulo 109 + 7 using 1024-bit computers! :p 349 350 There seems to be many solutions with hard optimizations can pass this problem. I worried about whether I should allow these solutions before the contest and finally get the answer yes. Congratulations to people who solved this problem, [nikanqilaizhenhaoxiao](/profile/nikanqilaizhenhaoxiao "International Master nikanqilaizhenhaoxiao") and [consecutivelimit](/profile/consecutivelimit "Legendary Grandmaster consecutivelimit") whose solutions are very close to the standard solution, and [whzzt](/profile/whzzt "International Grandmaster whzzt") whose solution has an interesting optimization. 351 352 **Solution** 353 354 If we only need to calculate  (*j*|*k* = *i*), we can do these: 355 356 1. Let  (*j*|*i* = *i*). 357 2. Let *C**i* = *A**i*·*Bi*, it can be found that  (*j*|*i* = *i*). 358 3. So  (*j*|*i* = *i* and *j* ≠ *i*). 359 360 To calculate *A**i* fast (*B**i* is the same), let *f*(*x*, *i*) be the sum of *a**j* which *j*|*i* = *i* and the lower *x* binary bits of *j* is equal to *i*'s. 361 362 So *f*(*n*, *i*) = *a**i*, *f*(*x* - 1, *i*) = *f*(*x*, *i*) if *i*&2x = 0 , *f*(*x* - 1, *i*) = *f*(*x*, *i*) + *f*(*x*, *i* - 2*x*) if *i*&2x = 2*x*, and *A**i* = *f*(0, *i*). 363 364 We can calculate all *A**i* and *B**i* in *O*(*n*·2*n*) time. 365 366 Getting *c**i* from *C**i* is the inversion of getting *A**i* from *a**i*. So we can use *f*(*x*, *i*) once again. *f*(*x*, *i*) = *f*(*x* - 1, *i*) if *i*&2x = 0, *f*(*x*, *i*) = *f*(*x* - 1, *i*) - *f*(*x* - 1, *i* - 2*x*) if *i*&2x = 2*x*. So we can get all *c**i* in *O*(*n*·2*n*) total time. 367 368 But in this problem we need to calculate  (*j*|*k* = *i* and *j*&*k* = 0). 369 370 In fact, there is a well-known algorithm for this problem. 371 372 The main idea of this algorithm is consider the number of "1" binary bits. 373 374 First, let *BC*(*x*) be the number of "1" binary bits in *x*. 375 376 Let  (*j*|*i* = *i* and *BC*(*j*) = *x*). 377 378 Then we calculate  (*y* + *z* = *x*), and  (*j*|*i* = *i* and *j* ≠ *i*). 379 380 So  (*j*|*k* = *i* and *BC*(*j*) + *BC*(*k*) = *x*). 381 382 Finally *c**i* we need to calculate is equal to *c*(*BC*(*i*), *i*), because if *j*|*k* = *i* and *BC*(*j*) + *BC*(*k*) = *BC*(*i*), *j*&*k* must be 0. 383 384 This algorithm cost *O*(*n*2·2*n*) time. Unfortunately, it may be too slow in this problem. 385 386 In this problem, we only need to calculate *c**i*&3, equal to *c**i* modulo 4. 387 388 In fact, when the answer is modulo *p*, an arbitrary integer, my solution works. 389 390 Let . 391 392 Then we calculate *F**i* = *A**i*·*B**i*, and  (*j*|*i* = *i* and *j* ≠ *i*). 393 394 So  (*j*|*k* = *i*). 395 396 If *j*|*k* = *i*, *BC*(*j*) + *BC*(*k*) ≥ *BC*(*i*). If *j*|*k* = *i* and *j*&*k* = 0, *BC*(*j*) + *BC*(*k*) = *BC*(*i*). 397 398 We find that , because if *BC*(*j*) + *BC*(*k*) > *BC*(*i*), *a**j*·*b**k*·*p**BC*(*j*) + *BC*(*k*) - *BC*(*i*) can be divided by *p*. 399 400 So the total time is *O*(*n*·2*n*). 401 402 A remainder problem is it can not be modulo *p* when calculating in this algorithm, so the number may be very large. 403 404 Fortunately, in this problem, *p* is only 4. We can use 128-bit integers or merge two 64-bit integers into one number when calculating. 405 406 But in fact, we only care  modulo *p*, so we can let all number be modulo *p**n* + 1. Single 64-bit integer is enough. 407 408 **How to come up with it?** 409 410 In fact, I did not come up with this solution directly. 411 412 When I learnt about Fast Walsh–Hadamard transform, I could not understand it well but came up with it: 413 414 Let's define a transform *F*(*x*0, *x*1) about a pair of integers (*x*0, *x*1) to be (*ax*0 + *bx*1, *cx*0 + *dx*1), and define (*x*0, *x*1)·(*y*0, *y*1) to be (*x*0*y*0, *x*1*y*1). 415 416 According to FWT, there is such a transform satisfies *F*(*x*0, *x*1)·*F*(*y*0, *y*1) = *F*(*z*0, *z*1), which *z*0 = *x*0*y*0 + *x*1*y*1, *z*1 = *x*0*y*1 + *x*1*y*0. 417 418 Then we can solve an equation to get *a*, *b*, *c*, *d*! After calculating, I get *a* = *c* = 1, *b* = ± 1 and *d* = ± 1, which is close to FWT! 419 420 Then I find that if *b* = *d*, there is no the inversion of this transform, so we can not get (*z*0, *z*1) from *F*(*z*0, *z*1). 421 422 If we do this transform for all the bits, it's actually FWT! 423 424 So we can use this method to solve bitwise xor convolution, and bitwise or convolution is similar, what about subset convolution? 425 426 After calculating, I get *a* = 0 or *a* = 1, *c* = 0 or *c* = 1, *b* = *d* = 0, which made me disappointed because it's difficult to find the inversion. 427 428 But at this time, I came up with a special idea — if we calculate in modulo *p*, *p* = 0 satisfied. 429 430 Let *a* = 1, *b* = 0, *c* = 1, *d* = *p*. We finally get a transform, which is actually my solution above! 431 432 And I'm really interested about how the others (such as [nikanqilaizhenhaoxiao](/profile/nikanqilaizhenhaoxiao "International Master nikanqilaizhenhaoxiao") and [consecutivelimit](/profile/consecutivelimit "Legendary Grandmaster consecutivelimit")) came up with it? 433 434 **My Code** 435 436 ``` 437 #include<cstdio> 438 typedef long long ll; 439 #define MN (1<<21) 440 char A[MN+5],B[MN+5]; 441 int s[MN+5];ll a[MN+5],b[MN+5]; 442 int main() 443 { 444 int n,i,j; 445 scanf("%d%s%s",&n,A,B); 446 for(i=0;i<1<<n;++i)s[i]=s[i>>1]+((i&1)<<1),a[i]=(ll)(A[i]-'0')<<s[i],b[i]=(ll)(B[i]-'0')<<s[i]; 447 for(i=0;i<n;++i)for(j=0;j<1<<n;++j)if(j&(1<<i))a[j]+=a[j^(1<<i)],b[j]+=b[j^(1<<i)]; 448 for(i=0;i<1<<n;++i)a[i]*=b[i]; 449 for(i=0;i<n;++i)for(j=0;j<1<<n;++j)if(j&(1<<i))a[j]-=a[j^(1<<i)]; 450 for(i=0;i<1<<n;++i)putchar(((a[i]>>s[i])&3)+'0'); 451 } 452 ``` 453 454 Hope it be useful to you!