link this question recently appear on codechef and it look similar to counting problem .

But, it become difficult for me to understand how this question can be transform into matrix expo…(as many student solve it)

what i understand from this question" No of ways to arrange k number on n-1 place such that No two adjacent number are same and start,end with 1 "

finally I am not able to solve this problem .If you can explain please .help

Thanks

Editorial for this problem will be up by tonight.

1 Like

Well if you would look closely then you might notice that since 1 is fixed at the end , so if at n-2th position if you have 1 , then you have k-1 values for n-1th position but, if you have any other value at n-2th position then you can have k-2 values at n-1th position , So basically answer of current state depends upon answer of previous state . You could have used dp here to calculate answer , but N and K value are so big , so you cant just do O(N) DP , and now to make calculation faster U are using Matrix Exponentiation.

1 Like