Grox's Sequence V B — Editorial¶
Problem setter's solution: obtain a row of Stirling numbers of the second kind by convolution, then evaluate a binomial moment. Codex (GPT-6) organizes NTT, inverse factorials, zero powers and normalized residues, and truncates the convolution to the prefix contributing to the answer. The fixed modulus \(P=1005060097\) differs from those of IV and VII.
Binomial moments¶
For \(k=0\) , the answer is \(2^n-1\) . For \(k>0\) , use the falling-factorial expansion:
Here \(S(k,j)\) is a Stirling number of the second kind and \((n)_j=n(n-1)\cdots(n-j+1)\) . The proof follows Sequence V A: expand \(i^k\) by the number of distinct images, then use \(\binom ni(i)_j=(n)_j\binom{n-j}{i-j}\) and the binomial theorem.
One convolution for the needed prefix¶
Inclusion-exclusion over missing target values gives
Put \(m=\min(n,k)\) and construct only
Coefficient \(j\) of their ordinary convolution is \(S(k,j)\) . For \(j\le m\) , both contributing indices are at most \(j\) , so truncation loses no needed term. The setter's complete row through \(k\) is also correct; when \(n<k\) , later columns do not enter the final sum and can be omitted. Convolution is used only for \(k>0\) , so the power at \(t=0\) is zero. Return zero directly for \(n=0\) .
\(P=1917\times2^{19}+1\) is prime and \(5\) is a primitive root. Factorial indices are at most \(m<P\) , so inverses exist. Choose the smallest power-of-two NTT length strictly greater than \(2m\) ; its maximum is \(2^{18}\) , dividing \(P-1\) . Invert \(m!\) once, then compute all inverse factorials downward.
Update \((n)_j\) successively. Starting from \(2^n\) , multiply by the inverse of \(2\) per step to obtain \(2^{n-j}\) , considering only \(1\le j\le m\) . Normalize all results to \([0,P-1]\) .
Correctness and complexity¶
Inclusion-exclusion counts surjections to \(j\) targets; division by target permutations gives the Stirling number. NTT computes ordinary convolution, and truncation preserves every coefficient used by the answer. Substitution into the binomial-moment identity proves the result.
Constructing powers takes \(O(m\log(k+1))\) time, convolution takes \(O(m\log(m+1))\) , and computing \(2^n\) takes \(O(\log(n+1))\) . Total time is
Space is \(O(m+1)\) . Worst-case bounds match the setter's full row: \(O(k\log(k+1)+\log(n+1))\) time and \(O(k+1)\) space. Small \(n\) needs a much shorter convolution. Row-by-row Stirling recurrence is also correct but takes \(O(k^2)\) time, appropriate for smaller \(k\) .
Supplementary solution¶
An exponential generating function extracts binomial moments through formal-series log/exp, giving a different algorithm with the same worst-case asymptotic bounds. It uses more polynomial operations; the supplied implementation exceeds the 0.5-second limit and is explicitly a backup, not a full-data reference.