题解 | #填充数组#

class Solution {
public:
    int FillArray(vector<int>& a, int k) {
        const int mod = 1000000007;
        int n = a.size();
        vector<vector<int>> f(n + 1, vector<int>(k + 1));
        for (int j = 1; j <= k; ++j)f[1][j] = j;
        for (int i = 2; i <= n; ++i)for (int j = 1; j <= k; ++j)f[i][j] = (f[i][j-1] + f[i-1][j]) % mod;
        long long i = 0,ans = 1;
        while (i < n) {
            while (i < n && a[i] != 0)++i;
            if (i == n)break;
            int ll = i,ii = (i > 0 ? a[i-1] : 1);
            while (i < n && a[i] == 0)++i;
            int tt = i,yy = (i < n ? a[i] : k);
            ans = (ans * f[tt-ll][yy-ii+1]) % mod;
        }
        return ans;
    }
};