PROBLEM LINK:
Setter-Trung Nguyen
Tester- Misha Chorniy
Editorialist- Abhishek Pandey
DIFFICULTY:
HARD
PRE-REQUISITES:
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 pre-requisites.
PROBLEM:
You are to count number of "S Semi Palindromic" numbers which are less than {10}^{K}. A non-negative number is called S Semi Palindrome if its digits can be re-arranged 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 XOR-SUM 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}^{K-1} {A}^{i}. Say matrices Ans1[][]=\sum_{i=1}^{K} {A}^{i} and Ans2[][]=\sum_{i=1}^{i=K-1} {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-
for (int i=0; i<10; i++)
A[i%s][1<< i]=1;
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 semi-palindrome detection, as digits can have values only from 0-9 and if he do a xor of \large {2}^{d_i}, then a semi-palindrome 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 re-arrange 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}^{K-1} {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-
- Matrix T=\sum_{i=1}^{P} {A}^{i}
- Matrix U={A}^{P}
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}^{2P-1}....{A}^{P+1})+{A}^{P}.....+A as-
{A}^{P}({A}^{P}+{A}^{P-1}+....+A)+{A}^{P}+{A}^{P-1}+.....+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}^{K-1} {A}^{i}. Hence, lets find upto \sum_{i=1}^{K-1} {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}^{K-1} {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).
So, our code should look somewhat like this-
for(int i=0;i< s;i++)
Fast-Walsh Transform(A[i]);
int lim=k-1;
while (lim) {
if (lim&1)
{
Multiply_Matrices(D, B, s, r); //s passed to calculate %s
Add_Matrices(D, A, s);
}
for (int i=0; i<s; i++)
for (int j=0; j<N; j++)
Duplicate[i][j]=A[i][j];
Multiply_Matrices(A, B, s, r); //r is needed in multiplication process. Explained in bonus section.
Add_Matrices(A, Duplicate, s);
Multiply_Matrices(B, B, s, r);
lim>>=1;
r<<=1;
}
We are almost done!
We have the answer of \sum_{i=1}^{K-1} {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?
A=Restore_Original(A);//The transition matrix which stored answer for K=1 length.
FWT_Transform_Matrix(A);
Multiply_Matrices(D, A, F, s, r);//Multiply D and A, store in F.
Add_Matrices(F, A, s);
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}^{K-1} 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-
ans=f[0][0]-d[0][1<<0];//Separately for digit 0
for (int i=0; i<=9; i++)
ans+=F[0][1<< i]-D[0][(1<< i)^(1<<0)];//For rest of digits from '1'-'9'
Recall that mask must be either 0 or a {2}^{i}. Now, why F[0][1<< i]-D[0][(1<< i)^1] ? The exact reasoning will be clear only when you get acquainted with transition matrices- but I can try giving an intuition on why its right.
We know that matrix D has answer till length K-1. One interpretation goes this way. In numbers of length K-1 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 Multiply_Matrix, Add_Matrix and another way of dealing with number of leading zeroes is discussed in bonus section.
SOLUTION:
Setter Solution's Time Complexity- O(2^{10} * S * log(K) * (S + log(2^{10})))
Editorial Solution's Time Complexity- O({2}^{10}* {S}^{2} *LogK * log({2}^{10}) )
CHEF VIJJU’S CORNER:
1. Add_Matrix function.
Click to view
void add(int A[16][N], int B[16][N], int s) //Take matrix A, B. Store result in matrix A.
{
for (int i=0; i< s; i++)
for (int j=0; j< N; j++) //N=1024
(A[i][j]+=B[i][j])%=MOD;//Simple addition
}
2. Multiply_Matrix Function
Click to view
void mul(int A[16][N], int B[16][N], int C[16][N], int s, long long f) {
int mid=power(10, f, s);//10^r. At one step, we are directly jumping from 10^2 to 10^4 to 10^8 &etc.
for (int i=0; i< s; i++)
for (int j=0; j< N; j++) //N=1024
c[i][j]=0;//This will store the values temporarily.
for (int i=0; i< s; i++)
for (int j=0; j< s; j++)
{
int u=(i*mid+j)%s;//Remainder. Remember, expression's form is
//A^K(A^K+A^(K-1)...+A)+A^K+A^(K-1)....+A. Hence, remainder is also of form i*10^f +j.
for (int k=0; k< N; k++)
c[u][k]+=(long long )A[i][k]*B[j][k]%MOD;
}
for (int i=0; i< s; i++)
for (int j=0; j< N; j++)
C[i][j]=c[i][j]%MOD;//Store value in matrix C finally.
}
3. Another way of bypassing leading 0's
Click to view
Let, DP0[k][i][j] be equal to the count of K-length numbers which are give remainder i by modulo S and j is mask of those digits as we calculated for this question.
Then, let, DP1[k][i][j] - count of K-length numbers which are give remainder i by modulo S and j is mask of those digits, and they don’t start by 0
Let’s see the state transitions:
DP0[0][0][0] = 1
DP0[k][i][j] \implies DP0[k+1][(10^k*d+i)\%s][j \oplus {2}^{d}], d = 0…9 (transitions A)
DP1[k][i][j] \implies DP1[k+1][(10^k*d+i)\%s][j \oplus {2}^{d}], d = 1…9 (transitions B)
The result is:
SUM i = 1..K
ans += DP1[i][0][0]
SUM d = 0..9
ans += DP1[i][0][1<< d]
We can use something like the matrix multiplication for finding the answer:
If we know transitions A and we know transitions B:
Let A is matrix of transitions: A[i \% s][1<< i] = 1, i = 0..9
Let B is matrix of transitions: B[i \% s][1<< i] = 1, i = 1..9
(i, j) \implies ((10^k*d+i)\%s, j \oplus {2}^{d}) and we know {10}^{k} before hand. d=1..9(for B), d =0..9( for A)
We know that length of left side is FIXED and equal to {10}^{k}. Then, we define operation multiplying as-
(i1, j1) * (i2, j2) \implies ((i1 * 10^k + i2) \% s, (j1 \oplus j2))
We can use something like binary exponentiation next. So,
DP0[i]=A*DP0[i-1], and we know {10}^{(i-1)}
DP1[i]=B*DP0[i-1]
Let’s calculate the sum over all values RES[i][j] = \sum_{i=1}^{K}DP1[i][j]
RES = B*{A}^{(K-1)}+B*{A}^{(K-2)}+...+B(with define operations + and *, i.e we need to know K and count of k-length numbers and their XOR)
for i = 0..S-1
for j = 0..S-1
for ii = 0..(1<<10)-1
for jj = 0..(1<<10)-1
RES[(i*10^leftBlockSize+j)%s][ii ^ jj] += A[i][ii] * B[j][jj]
RES[(i*10^leftBlockSize+j)%s][ii ^ jj] %= MOD
Time Complexity=O({S}^{2}*{2}^{20})
It can be boosted with FWT to achieve a complexity of O({S}^{2}*{2}^{10}*{10})