Editorial for Grox's Sequence VI¶
Problem setter’s solution: precompute the coefficient matrix of polynomial particular solutions and represent the recurrence using a polynomial and an exponential term. Codex (GPT-6) makes the \(\beta=1\) finite-summation branch explicit, retains handling of negative values and zeroth powers, and composes coefficients at parameter replacement so that queries evaluate one polynomial rather than all basis functions.
Polynomial particular solutions¶
All arithmetic is modulo \(P=1000000007\) . Write
For \(\beta\ne1\) , seek a polynomial \(g(n)\) of degree at most \(k\) such that
If \(g(n)=\sum_{j=0}^k c_j n^j\) , comparison of coefficients of \(n^d\) gives
This is a triangular system solved from high degrees downward, with invertible diagonal \(1-\beta\) . Precompute a coefficient vector for each basis function \(T(n)=n^i\) and denote its polynomial by \(g_i(n)\) .
For any parameters, the linear combination \(g(n)=\sum_i a_i g_i(n)\) is a particular solution. Hence
The last term satisfies the homogeneous recurrence, and the zeroth term equals \(\alpha\) , so the formula satisfies the complete initial value problem. Modular powers here use \(\beta^0=1\) , including \(\beta=0\) , to recover the initial value at index zero. For \(n>0,\beta=0\) , the exponential term vanishes.
When beta equals one¶
The diagonal \(1-\beta\) is not invertible. Instead, seek a discrete antiderivative of degree at most \(k+1\) , with \(g(0)=0\) :
Its coefficient system is
Solve from \(d=k\) downward. The coefficient of \(c_{d+1}\) in each row is \(d+1\) , which is smaller than \(P\) and invertible. Fixing \(c_0=0\) determines the polynomial uniquely. Precompute monomial basis functions in the same way. The answer is then \(f(n)=\alpha+g(n)\) , consistent with the unified formula above.
Query and replacement tradeoff¶
After precomputing basis functions, the setter’s method evaluates them separately at every query and weights them by the current \(a_i\) . Coefficient comparison and elimination correctly determine those basis functions. Each query uses \(O((k+1)^2)\) polynomial work, plus exponentiation. Replacement only stores the input parameters, costing \(O(k+1)\) .
The reference program retains that precomputation and combines the coefficients of \(g\) and the value \(\alpha-g(0)\) at initial input or replacement. Replacement takes \(O((k+1)^2)\) ; Horner evaluation makes each query \(O(k+1+\log(n+1))\) . Several queries under one parameter set avoid repeated weighting. Frequent replacements incur quadratic composition work instead of linear parameter storage, so this is not a claim of faster execution for every operation mix.
Correctness and complexity¶
The triangular systems in the two branches give basis functions satisfying their respective particular-solution equations. Linear combinations preserve those equations. Adding the homogeneous exponential term satisfies the initial value, so uniqueness of the recurrence gives the required sequence. A replacement recomposes current coefficients rather than retaining terms of the previous sequence.
Let \(Q_0\) be the number of queries, \(Q_1\) the number of replacements, and \(N_{\max}\) the largest queried index. Including exponentiation for inverses, precomputation takes \(O((k+1)^3+(k+1)^2\log P)\) time. Subsequent work takes \(O((Q_1+1)(k+1)^2+Q_0(k+1+\log(N_{\max}+1)))\) time, with \(O((k+1)^2)\) space. Normalize all negative input values into \([0,P-1]\) .
Supplementary solution¶
Finite differences and a Newton binomial basis reduce the particular-solution equation to adjacent coefficients, with \(O(k+1)\) space and \(O(k+1+\log P)\) preprocessing. Update and query bounds match the reference, with different conversion and evaluation constants; it is retained as a lower-space parallel option.