Problem Description
Given two integers n and k, you start with an array a of n integers where every element is initialized to 1. At each second, every element a[i] is updated simultaneously to be the sum of all elements from index 0 to i (inclusive). After k seconds, return the value of a[n - 1] modulo 10^9 + 7.
Key Insights
- The update rule is equivalent to computing prefix sums.
- After each second, the transformation results in values that correspond to binomial coefficients.
- In fact, a[n - 1] after k seconds equals the combination C(n - 1 + k, k).
- The constraint n, k ≤ 1000 allows us to compute the combination iteratively modulo 10^9+7 using the multiplicative inverse (thanks to Fermat’s Little Theorem).
Space and Time Complexity
Time Complexity: O(k) – It takes k iterations to compute the final result. Space Complexity: O(1) – Only a few auxiliary variables are used.
Solution
We derive the answer by observing that after k seconds the value at position n - 1 is given by the binomial coefficient C(n - 1 + k, k) which can be computed iteratively. In each iteration, we multiply the current result by (n - 1 + current iteration index) and then multiply it by the modular inverse of the iteration index to perform the division modulo 10^9+7. This uses Fermat’s Little Theorem for calculating the modular inverse when the modulus is prime.