A Certain Unscientific Polynomial-Weighted Geometric Sum with Updates — Solution¶
Codex (GPT-6) applies a linear polynomial antidifference transform to this problem, including triangular preprocessing, coefficient updates, implementation, and verification. Finite differences, binomial expansion, and modular inverses are established tools.
Find a polynomial that telescopes¶
To distinguish it from the modulus, write the current load polynomial as \(B(x)=\sum_{j=0}^k b_jx^j\) . Construct \(Q(x)\) satisfying
Substitute \(x=i\) , multiply by \(a^i\) , and sum to obtain
It suffices to maintain \(Q\) , evaluate it at two points with Horner's rule, and compute one modular power.
Precompute one column per monomial¶
Find \(Q_j(x)\) such that \(aQ_j(x+1)-Q_j(x)=x^j\) . Linearity gives \(Q(x)=\sum_jb_jQ_j(x)\) . A change in \(b_j\) adds \(\Delta b_j\) times this precomputed column to the coefficients of \(Q\) .
For \(a\ne1\) , write \(Q_j(x)=\sum_{h=0}^j q_hx^h\) . Comparing coefficients of \(x^t\) gives
The bracket is one when \(t=j\) and zero otherwise. Solve from higher degrees downward, dividing by \(a-1\) with a modular inverse.
For \(a=1\) , a difference lowers the degree by one. Use degree \(j+1\) and set the constant coefficient to zero. Solve downward using
Every divisor \(1,\ldots,k+1\) is below the prime modulus, so its inverse exists and can be precomputed. Base \(a=0\) is covered by the first triangular system and yields zero output naturally; no inverse of zero is needed.
Correctness and Complexity¶
Each triangular system has invertible diagonal entries, so coefficient comparison proves its identity. Linear combination and incremental updates preserve the correct current \(Q\) for \(B\) . The telescoping identity therefore gives the desired sum. Changing the upper bound does not affect the precomputed columns.
After binomial and inverse preprocessing, all columns require \(O(k^3)\) time and \(O(k^2)\) space; initial combination costs \(O(k^2)\) . Coefficient updates and polynomial evaluation cost \(O(k)\) , while a changed bound needs \(O(\log n)\) exponentiation. Total time is \(O(k^3+m(k+\log n))\) , with \(O(k^2)\) space. The modulus is fixed; one general inverse additionally uses \(O(\log P)\) exponentiation. Reduce after multiplication so signed 64-bit arithmetic suffices.
std.cpp supports every operation mix. The moment-recurrence alternative gives constant-time coefficient-only updates, but frequent bound changes are slower, so it is published as a backup.