Hello everyone!
While I am solving this problem 1967C - Fenwick Tree, I read Elegia matrix solution and finally came up with my own solution that is based on his approach, using the matrix of linear transformation. Throughout the solution is tons of "heavy-math" knowledges and assumptions that is considered to be hard to see. Motivated enough, I have my heart set on writing an entire blog here with an ambition to prove every details in my solution.
Let's first quote the problem here
Problem Statement
Let $$$\operatorname{lowbit}(x)$$$ denote the value of the lowest binary bit of $$$x$$$, e.g. $$$\operatorname{lowbit}(12)=4, \operatorname{lowbit}(8)=8.$$$
For an array $$$a$$$ of length $$$n$$$, if an array $$$s$$$ of length $$$n$$$ satisfies $$$s_k=\left(\sum\limits_{i=k-\operatorname{lowbit}(k)+1}^{k}a_i\right)\bmod 998\,244\,353$$$ for all $$$k$$$, then $$$s$$$ is called the Fenwick Tree of $$$a$$$. Let's denote it as $$$s=f(a).$$$
For a positive integer $$$k$$$ and an array $$$a$$$, $$$f_k(a)$$$ is defined as follows:
You are given an array $$$b$$$ of length $$$n$$$ and a positive integer $$$k$$$. Find an array $$$a$$$ that satisfies $$$0\leq a_i <998244353$$$ and $$$f_k(a)=b$$$. It can be proved that an answer always exists. If there are multiple possible answers, you may print any of them.
Solution
The definition of $$$s_k$$$ makes us think of the linear map $$$T: \mathbb{R_n}\rightarrow \mathbb{R_n}$$$ which map a vetor array $$$a$$$ to the Fenwick Tree of $$$a$$$, in other words $$$T(a)=f(a)$$$. Note that $$$R_n$$$ here is the set of all matrices with size $$$n\times 1$$$ and if $$$a \in \mathbb{R_n}$$$ then
From the definition of $$$s_k$$$ we can see that the matrix $$$T$$$ of the linear map is
and satisfy
Because $$$T$$$ is a lower triangular matrix, we have $$$\det T = 1$$$ for all $$$n\geq 1$$$ and the characteristicpolynomial of $$$T-I$$$ is
So all the eigenvalues of $$$T-I$$$ are $$$0$$$, $$$T-I$$$ is nilpotent and according to the Cayley-Hamilton theorem, we have
However, all of these above observations are just not enough to solve this problem, as will be seen later on. Indeed, we need to find the smallest integer $$$m$$$ such that
We claim that $$$m = \lfloor\log_2(n) \rfloor +1$$$.
Warning: the solution requires many advanced mathematical techniques and ... long, but it's the best way I can think of.
After having proven the bound for $$$m$$$, since the restriction on $$$n$$$ of the problem is $$$1\leq n \leq 2\cdot 10^5$$$, we then have
It means for all $$$1\leq n \leq 2\cdot 10^5$$$, it's ensured that
Now, from the definition of $$$T_n$$$, we know that if $$$f_k(a) = b$$$ then $$$(T_n)^k\cdot a = b$$$ or $$$a = (T_n^{-1})^k \cdot b$$$. Thus, to find $$$a$$$, we only need to compute $$$(T_n^{-1})^k \cdot b$$$ efficiently.
Achieving this requires a bit of Polynomial Modular Arithmetic skills and of course, we will use modulo $$$(x-1)^{19}$$$ here. Let's assume that for a polynomial $$$Q(x)$$$ with $$$\deg Q\leq 18$$$
If and only if
Suppose $$$Q(x) = c_{18}x^{18}+\ldots + c_1x+c_0$$$.Then it can be easily seen that
The only problem is to know the formula of $$$c_i$$$ that is dependent of $$$k$$$ as well and I got stuck while doing this. Then I came up with another fresh idea. Instead of writing $$$T_n^{-k}$$$ as a linear combination of $$$(I_n, T_n, \ldots, T_n^{18})$$$, why not writing it as a linear combination of $$$(I_n, T_n - I_n, \ldots, (T_n-I_n)^{18})$$$. We have one secret weapon that can compute the linear combination's coeffcients directly. That's the well-known Taylor Series. Using the Taylor series for function $$$x^{-k}$$$ at $$$x_0 = 1$$$, we deduce that
Thus
Please note that we can use Taylor Series for $$$x_0=1$$$ here and not $$$x_0=0$$$ because $$$x^{-k}$$$ is undefined at $$$x=0$$$. Now that we have the explicit formula of $$$c_i$$$, we will still have to compute it modulo $$$998244353$$$ because if $$$k$$$ get pretty large, the last coeffient can be up to $$$\displaystyle\frac{(10^9)^{18}}{18!}$$$. One more question arises: How can we handle the number $$$1, 2,\ldots, 18$$$ under the denominator of these coefficents? Since $$$998244353$$$ is indeed a prime number, then we can precalculate the inversion of them.
// inverse[i] is the number x that x*i equiv 1 mod 998244353
vector<ll> inverse = { 0 , 1, 499122177, 332748118, 748683265, 598946612, 166374059, 855638017, 873463809, 443664157, 299473306, 272248460, 582309206, 460728163, 926941185, 865145106, 935854081, 939524097, 720954255 };
Finally we can multiply $$$T_n-I_n$$$ with any vector $$$b$$$ in $$$O(n\log n)$$$ instead of $$$O(n^2)$$$ in a standard multiplication of a $$$n\times n$$$ matrix with a $$$n\times 1$$$ one.
