Solution

Method 1 – Combinatorics (Stars and Bars)

Intuition

After each second, the update rule is equivalent to prefix sums. The value at the end, a[n-1], after k seconds, is the number of ways to distribute k indistinguishable increments among n positions, which is a classic stars and bars problem. The answer is C(n+k-1, n-1).

Approach

The answer is the binomial coefficient C(n+k-1, n-1).
Compute this value modulo 10^9+7 using modular inverses for efficiency.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int nthValueAfterKSeconds(int n, int k) {\n        const int MOD = 1e9+7;\n        vector<long long> fact(n+k,1), inv(n+k,1);\n        for(int i=1;i<n+k;++i) fact[i]=fact[i-1]*i%MOD;\n        inv[n+k-1]=1;\n        for(int i=n+k-2;i>=0;--i) inv[i]=inv[i+1]*(i+1)%MOD;\n        return fact[n+k-1]*inv[n-1]%MOD*inv[k]%MOD;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> nthValueAfterKSeconds</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> n</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> k</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        const</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> int</span><span style=\"color:#24292E;--shiki-da

Related Tags