Construct the Array

Construct the Array

Topic: DP

Complexity: O(n) 

Solution:

Code:

const long long mod = 1000000000+7;
long countArray(int n, int k, int x) {
    // Return the number of ways to fill in the array.
    vector<long long> a(n), b(n);
    a[0] = x == 1 ? 1 : 0;
    b[0] = x == 1 ? 0 : 1;

    for(int i = 1; i < n; i++){
        a[i] = b[i - 1] % mod;
        b[i] = (a[i- 1]*(k-1) + b[i-1] * (k-2) )%mod;
    }
    return a[n-1];
}

Share: