• + 1 comment

    An O(n) Python3 solution:

    def countArray(n, k, x):
        # Note:
        # The key point to achieve linear time complexity is to realize that all x where x!=1 are symmetrical.
        # So instead of iterate over a table of size n*k, we only need to iterate over a table of size n*2
        
        table = []
    
        table.append([0,0]) # The first list in table is arbitrary. It won't be used
        table.append([0,1]) 
        for i in range(2, n):
            table.append([-1,-1])
    
        for i in range(2, n):
            # If the i-th element is 1, then all k-1 possibilities for (i-1)-th element are symmetrical. 
            table[i][0] = (k-1)*table[i-1][1] % int(1e9+7)
            
            # If the i-th element is not 1, then we have k-2 symmetrical possibilities for (i-1)-th element, plus the case where (i-1)-th element is 1.
            table[i][1] = (table[i-1][0] + (k-2)*table[i-1][1]) % int(1e9+7)
             
        if x == 1:
            return table[n-1][0] % int(1e9+7)
        else:
            return table[n-1][1] % int(1e9+7)