codeforces-scrape

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

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 ![](https://espresso.codeforces.com/e1708d7a206fd713c1d8018adf5365dfbba70a6f.png) 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 ![](https://espresso.codeforces.com/090ff3b7240ebdeb283eb84a72c8e52b60b338ca.png) 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 ![](https://espresso.codeforces.com/9608caa4b9b4c7735912ac39b7b67ff2ff5a618f.png) 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 ![](https://espresso.codeforces.com/9608caa4b9b4c7735912ac39b7b67ff2ff5a618f.png) 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 ![](https://espresso.codeforces.com/4a1608777882dfa649fe9c9577841ab382886562.png) 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 ![](https://espresso.codeforces.com/b170c1cfd207a66e5a1ffe593b6bf7307b6760f5.png).
    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 ![](https://espresso.codeforces.com/5454ebdbf124a5119d7b2b1e8ec2dd1f5ef80679.png). 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 ![](https://espresso.codeforces.com/66ca3780e3d9c21b2e19de1410fb9f38931b7457.png), separating it from the tree. We find that only the *i* with ![](https://espresso.codeforces.com/815249b90ce5808fd4390ece9ab52dd2cf6ef8b7.png) 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 ![](https://espresso.codeforces.com/5454ebdbf124a5119d7b2b1e8ec2dd1f5ef80679.png). Since all the values are positive, all the connected parts have size ![](https://espresso.codeforces.com/5454ebdbf124a5119d7b2b1e8ec2dd1f5ef80679.png). So we just need to count how many cities *i* with ![](https://espresso.codeforces.com/57bb03a21a99e52be752eef0b56b20c397c129ee.png) there are. Let the equation be ![](https://espresso.codeforces.com/60a9a9cbc80fef06128d1fd964782e959c33df3d.png), where *x* is a positive integer, so *k* should be a multiple of ![](https://espresso.codeforces.com/81d3e4674188872b2452e57edb63bc4c16f9b396.png). Now we can use a simple dp with ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png) 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 ![](https://espresso.codeforces.com/243d686763547825789da627a6b79ef1baeddc82.png) (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 ![](https://espresso.codeforces.com/0c18a224e805d960478a53ca7ac5ae33eaed6dd7.png) solution can pass this problem? Some of the testers submit solutions which enumerate the multiples of ![](https://espresso.codeforces.com/81d3e4674188872b2452e57edb63bc4c16f9b396.png) instead of keep them in an array and then use a ![](https://espresso.codeforces.com/55a740bc6da24d6368e6c9c83fa1fa3faaf56def.png) dp. I think its time complexity will be ![](https://espresso.codeforces.com/0c18a224e805d960478a53ca7ac5ae33eaed6dd7.png), 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 ![](https://espresso.codeforces.com/7290b8e091b6df2f627c989a8dd90818770eeab6.png) (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 ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png) 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 ![](https://espresso.codeforces.com/3a9351f4fab56aa417c4400a5105640107a41c95.png).
    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 ![](https://espresso.codeforces.com/937365ac4eccce570a1d59408d446093f440c9a7.png) (*j*|*k* = *i*), we can do these:
    355 
    356 1. Let ![](https://espresso.codeforces.com/3bea20ae98f7b6c4feb9f915bd5bd4f5d2956385.png) (*j*|*i* = *i*).
    357 2. Let *C**i* = *A**i*·*Bi*, it can be found that ![](https://espresso.codeforces.com/b1fd7ddbca91b62b8d2488e56900a72de902bd4e.png) (*j*|*i* = *i*).
    358 3. So ![](https://espresso.codeforces.com/c215cb152ea7cc2699080c60d76cf5f8541bbe9b.png) (*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 ![](https://espresso.codeforces.com/937365ac4eccce570a1d59408d446093f440c9a7.png) (*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 ![](https://espresso.codeforces.com/2ba110c85f9a018a14ef292e94aba84859bc8d53.png) (*j*|*i* = *i* and *BC*(*j*) = *x*).
    377 
    378 Then we calculate ![](https://espresso.codeforces.com/b82829b42f4c82a3f31e7d11c5107cc5996d8fba.png) (*y* + *z* = *x*), and ![](https://espresso.codeforces.com/84a6c88742ffb9a928f5edf5154df69cb22069b0.png) (*j*|*i* = *i* and *j* ≠ *i*).
    379 
    380 So ![](https://espresso.codeforces.com/986bd30ddd6a8614d9911cca8cc32ce139c78a40.png) (*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 ![](https://espresso.codeforces.com/b76fb85e70c9b8e20c0a1ea8122a2fdadf0ce7df.png).
    391 
    392 Then we calculate *F**i* = *A**i*·*B**i*, and ![](https://espresso.codeforces.com/18d4c16b0702adbf7a3ee33ed068d5fa35166a91.png) (*j*|*i* = *i* and *j* ≠ *i*).
    393 
    394 So ![](https://espresso.codeforces.com/63e1b2ade1041ae672b8a8080912c9946a55baeb.png) (*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 ![](https://espresso.codeforces.com/23f8de8988c3b3c7c1e7a8cf8b988bf2555725cb.png), 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 ![](https://espresso.codeforces.com/739ae3ff6c5c7b764df3637bd233bafbf885f6cc.png) 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!