Painting Fence Algorithm | C ++ program for Painting Fence Algorithm ; Returns count of ways to color k posts using k colors ; There are k ways to color first post ; There are 0 ways for single post to violate ( same color ) and k ways to not violate ( different color ) ; Fill for 2 posts onwards ; Current same is same as previous diff ; We always have k - 1 choices for next post ; Total choices till i . ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; long countWays ( int n , int k ) { long total = k ; int mod = 1000000007 ; int same = 0 , diff = k ; for ( int i = 2 ; i <= n ; i ++ ) { same = diff ; diff = total * ( k - 1 ) ; diff = diff % mod ; total = ( same + diff ) % mod ; } return total ; } int main ( ) { int n = 3 , k = 2 ; cout << countWays ( n , k ) << endl ; return 0 ; }