### PROBLEM LINKS

### DIFFICULTY

MEDIUM

### EXPLANATION

The most obvious approach here is to iterate over all permutations of digits of **A**, calculate **B**’ = C - A’ where A’ is a current permutation of A and check whether B’ is a permutation of **B**. Interestingly that under assumptions of the problem (that is **X * len <= 80**) this approach is fast enough for large bases 10, 9, 8 and even 7. But for small bases it is very slow, especially for 2, 3 and 4. Thus we need another algorithm here.

At first consider the worst case for the first approach - the base 2. Assume for simplicity that **A, B** and **C** all have equal length and denote it by **L**. Denote digits of **C** by **C _{1}, C_{2}, …, C_{l}** and its prefix of length

**k**by

**C(k)**, that is

**C(k) = C**(see notation in the problem statement). Also denote by

_{1}C_{2}…C_{k}**nA**and

**nB**the number of ones in binary representation of

**A**and

**B**respectively.

Let **dp[d][k][na][nb]** stands for the number of pairs of non-negative integers **A’** and **B**’ such that

**A**’ and **B**’ has exactly **k** digits in binary (possibly with leading zeros);

**A**’ has **na** ones in binary;

**B**’ has **nb** ones in binary;

**A’ + B’ + d = C(k)**.

It is easy to see that **dp[0][0][0][0] = 1, dp[ 1 ][0][0][0] = 0** and the answer to the problem is **dp[0][L][nA][nB]**.

Here for parameters **d, k, na, nb** the following inequalities hold

**0 <= d <= 1;**

**0 <= k <= L;**

**0 <= na <= min(k, nA);**

**0 <= nb <= min(k, nB).**

Now let’s consider what transitions we have between states of this dp. Let **x** and **y** be the last digits of numbers **A**’ and **B**’. Then equation **A’ + B’ + d = C(k)** is equivalent to the couple of relations

**x + y + d = 2 * d’ + Ck where 0 <= d’ <= 1;**

**A’’ + B’’ + d’ = C(k - 1),**

where **A’**’ is obtained from **A**’ by erasing its last digit and similar is for **B**’’.

If we fix **x** then **y** and **d’** determined uniquely from the first condition

**y = (Ck - d - x) mod 2;**

**d’ = (x + y + d) div 2.**

Now consider the second condition **A’’ + B’’ + d’ = C(k - 1)**. It is very similar to the 4th condition in definition of **dp[d][k][na][nb]**. Note that **A**’’ have **na**’ ones in binary where **na’ = na** if **x = 0** and **na’ = na - 1 if x = 1** and **B**’’ have **nb**’ ones in binary where **nb’ = nb** if **y = 0** and **nb’ = nb - 1** if **y = 1**. Hence we have transition from the state **(d’, k - 1, na’, nb’)** to **(d, k, na, nb)** provided that parameters **d’, k - 1, na’, nb**’ satisfy all needed inequalities. So by basic combinatorial principles **dp[d][k][na][nb]** is equal to the sum of **dp[d’][k - 1][na’][nb’]** over all valid states **(d’, k - 1, na’, nb’)** from which we have a transition to **(d, k, na, nb)**. Thus we obtain an algorithm with complexity **O(L ^{3})** for finding the answer if base is equal to 2. Indeed, we find each

**dp[d][k][na][nb]**in

**O(1)**time as a sum of at most two previous values of dp (this is because transition is uniquely determined by

**x**) and we have at most

**2 * (L + 1) * (nA + 1) * (nB + 1)**states in our dp in total. Since

**L <= 40**it is very fast.

Now consider the general case when base is arbitrary.

If **A**, **B** and **C** has different lengths then some quite careful analysis is needed. Let **La** be the length of **A, Lb** be the length of **B** and **L** be the length of **C**. Swapping if needed **A** and **B** we can always assume that **La >= Lb** .

If **L < La** then we simply can pad **C** with **La - L** leading zeros and set **L = La**.

If **L > La** then there is big chance that the answer is zero. It can be non-zero only in the case when **L = La +1** and **C** starts with **1**. In this case if base is equal to 2 we can simply delete this 1 from **C**, decrease **L** by **1** and set **dp[0][0][0][0]=0** and **dp[1][0][0][0]=1**. In the general case of base after we discuss what is dp here the same trick with initialization of dp can be done.

Thus we can assume that **L = La >= Lb**. When base is arbitrary the state in dp will be more complicated than for base 2. Namely the state is the following triple **(d, maska, maskb)** where **maska = (na[0], na1, …, na[X - 1])** and **maskb = (nb[0], nb1, …, nb[X - 1])**. Here **na[j]** is the number of digits j in representation of **A**’ and similar is for **B**’. Also we must have **La - na = Lb - nb** where **na = na[0] + na 1 + … + na[X - 1]** and similar for nb. All other assumptions on parameters are the same as for the case of base 2. The meaning of **dp[d][maska][maskb]** is similar to that for the case of base 2. The transitions between states can be obtained in similar manner. The total number of states is equal to **2 * totA * totB** where **totA = (nA[0] + 1) * (nA 1 + 1) * … * (nA[X - 1] + 1)** and similar is for **totB**. Under assumptions of the problem this number does not exceed 1296. We can code **maska** as a number of length **X** in positional numerical system where each digit has its own bounds, namely **j**th digit is from 0 to **nA[j]**. Then **dp[d][maska][maskb]** can be stored in usual three-dimensional array.

Thus we have obtained an algorithm which is fast enough now.

### SETTER’S SOLUTION

Can be found here.

Problem Setter’s alternate solution.

### TESTER’S SOLUTION

Can be found here.