ronith
11/22/2018 - 10:10 AM

Count of arrays having consecutive element with different values

Given three positive integers n, k and x. The task is to count the number of different array that can be formed of size n such that each element is between 1 to k and two consecutive element are different. Also, the first and last elements of each array should be 1 and x respectively.

Count of arrays having consecutive element with different values.cpp
content_copyfile_download
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007

long func(int n, int k, int x) {
    long dp[n];
    dp[0]= 0;
    dp[1]= 1;

    for (int i=2;i<n;i++) {
        dp[i]= ((k-1)*dp[i-2])%mod;
        dp[i]+= ((k-2)*dp[i-1])%mod;
        dp[i]%= mod;
    }
    return (x==1?((k-1)*dp[n-2])%mod:dp[n-1]);
}

int main() {
  ios_base
  int n,k,x;
  cin>>n>>k>>x;
  cout<< func(n,k,x)<<"\n";
}