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.
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.