PROBLEM LINK:SetterTrung Nguyen DIFFICULTY:HARD PREREQUISITES:Fast Walsh Hadmard Transformation (Some knowledge about concepts of FFT etc. may aid in understanding), Dynamic Programming with Bitmasking This editorial will assume you have a knowledge of the prerequisites. PROBLEM:You are to count number of "$S$ Semi Palindromic" numbers which are less than ${10}^{K}$. A nonnegative number is called $S$ Semi Palindrome if its digits can be rearranged to give a palindromic number. QUICK EXPLANATION:Let $A[i][mask]$ be the matrix of transition where $i$ represents the remainder $\%S$ and $mask$ represent a $XORSUM$ of digits as $XorSum={2}^{d_0}\oplus{2}^{d_1}.....\oplus{2}^{d_k}$. Our answer is $\sum_{i=1}^{K} {A}^{i}$ $$ but it will count leading zeroes! However, we can easily remove count of leading zeroes if we also store the state $\sum_{i=1}^{K1} {A}^{i}$. Say matrices $Ans1[][]=\sum_{i=1}^{K} {A}^{i}$ and $Ans2[][]=\sum_{i=1}^{i=K1} {A}^{i}$. Our final answer will be $(Ans=\sum_{d_i=0}^{9}Ans1[0][{2}^{d_i}]Ans2[0][({2}^{d_i})\oplus ({2}^{0})])$ EXPLANATION:First, lets make a transition matrix, which is initially initialized to hold answer for $K=1$ (i.e. single digit numbers). Hence, the initial state of our transition matrix is
The meaning of $A[i][mask]$ is All numbers, which leave a remainder i when $\%S$ and have the given mask. Note that, mask here is calculated by $Mask={2}^{d_0}\oplus{2}^{d_1}.....\oplus{2}^{d_k}$. This helps in easy semipalindrome detection, as digits can have values only from $09$ and if he do a $xor$ of $\large {2}^{d_i}$, then a semipalindrome must have mask which is either a power of $2$ , or $0$. Power of $2$ represents a single digit occurring odd number of times (middle digit) while rest occurs even number of times, and a $0$ represents that every digit occurs in multiples of $2$ which makes it possible to rearrange the number to make it a palindrome. Our $A[][]$ holds answer for $K=1$ currently. To answer the query, we need $\sum_{i=1}^{K} {A}^{i}$ where ${A}^{i}$ will store answer for numbers of length $i$. This process will also, however, count numbers with leading $0s$ which is undesirable. To compensate for that, we will need the state value of $\sum_{i=1}^{K1} {A}^{i}$. But how to find these in first place? We will be using two tricks. The first one is Fast Walsh Hadmard Transformation of our transformation matrix $A$ , so that we can compute things faster. The second one is how we will calculate the polynomials. Say we have the following values
We need to find $\sum_{i=1}^{2P} {A}^{i}$ from it. What to do? It turns out to be pretty simple! We can reformulate $({A}^{2p}+{A}^{2P1}....{A}^{P+1})+{A}^{P}.....+A$ as ${A}^{P}({A}^{P}+{A}^{P1}+....+A)+{A}^{P}+{A}^{P1}+.....+A$ Which is equivalent to, in terms of our matrices, $UT+T$. Now, remember that we need $\sum_{i=1}^{K} {A}^{i}$ AND $\sum_{i=1}^{K1} {A}^{i}$. Hence, lets find upto $\sum_{i=1}^{K1} {A}^{i}$ using the above logarithmic method. The answer for $\sum_{i=1}^{K} {A}^{i}$ can be easily obtained by multiplying with, and adding $A$ once more to $\sum_{i=1}^{K1} {A}^{i}$. Suppose matrix $B$ holds the value of ${A}^{K}$ (equivalent to matrix $U$ of my example.)
, matrix $D$ stores values of answering summation, and matrix $A$ holds the value of polynomial, (equivalent to matrix $T$ of my example).
We are almost done! We have the answer of $\sum_{i=1}^{K1} {A}^{i}$ stored in matrix $D$. Lets make another matrix $F$ to store the answer for $\sum_{i=1}^{K} {A}^{i}$. Any guesses about $F$ till now?
We are just two steps away from the final answer! Our first task is to reverse the transformation which we did for faster multiplication and computation of required answer. We have $D=\sum_{i=1}^{K1} FWT({A}^{i})$ and $F=\sum_{i=1}^{K} FWT({A}^{i})$. Our next step is to calculate the inverse of this FWT transformation. Once we calculate the inverse, our answer will be of form
Recall that $mask$ must be either $0$ or a ${2}^{i}$. Now, why We know that matrix $D$ has answer till length $K1$. One interpretation goes this way. In numbers of length $K1$ we have some unpaired number (as ${2}^{i}$) and another unpaired $0$. When we added another digit at $MSB$ to get the ans for numbers till length $K$, the $0$ got paired. So naturally, what will that number be? (Please see, this isnt intended to be an "Absolute Mathematical Reasoning" but merely a rough intuition to kind of help get the logic. People are always advised to explore the topic and get the real mathematical reasoning). The exact definition of functions SOLUTION:$Setter$ $Solution's$ $Time$ $Complexity$ $O(2^{10} * S * log(K) * (S + log(2^{10})))$ CHEF VIJJU'S CORNER:1. Add_Matrix function. 2. Multiply_Matrix Function 3. Another way of bypassing leading $0's$
This question is marked "community wiki".
asked 17 Apr '18, 03:37

Actually, The complexity is $O(2^{10} * S * log(K) * (S + log(2^{10})))$. answered 18 Apr '18, 12:33
