USACO Stamp Painting (January 2018)
Notice that any integer sequence of length N where K elements are the same, this is a valid painting; Bessie can use her last stamp on the consecutive K elements and then incrementally work outwards (that is, backwards).. It's easier to use complementary counting - we wish to find the # of sequences such that there exists NO K elements that are the same. So, here's an unoptimized DP equation that is over N: dp ( n ) = ( M − 1 ) ⋅ ∑ c = 1 K − 1 dp ( n − c ) . Notice that if this recurrence equation is being called on a value of N that is less than K, dp(n) = M^N. This is very important for our optimization. However, this is effectively O(NK), which only gets 3/4 credit. Let us make another different DP equation, S, defined as: s ( n ) = ∑ n i = 1 dp ( n ) a Hence, dp(n) = s(n)-s(n-1), so s ( n ) − s ( n − 1 ) = ( M − 1 ) ( s ( n − 1 ) − s ( n − K ) ) ,or s ( n ) = M s ( n − 1 ) − ( M − 1 ) s ( n − K ). But wait! Remember that dp(n) = M^N if n is less ...