mike_wasabi's blog

How this problem is solved?
By mike_wasabi, history, 6 years ago, In English

I need help with a problem like this: Count the number of arrays of n elements in which each element of the array has the value of paragraph [1, M] so that there are the same K consecutive values. with n, M, K <= 1000000 For example: n = 3, M = 2, k = 2 The result will be 6 satisfying fields that are (1,1,1); (1,1,2); (1,2,2); (2,1,1); (2,2,1); (2,2,2)

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Clarify your ques

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Go through this blog, and then try to ask your question again. https://codeforces.net/blog/entry/64993

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Dp[i] — the number of ways to choose the first i elements such that they necessarily contain k consecutive same numbers. For i smaller than k the value of the dp is obviously 0. Otherwise we have two opportunities: either the last k elements are equal and the first i-k elements don't matter, or the first i-k numbers are valid(contain k consecutive same numbers). This leads us to the following transition: dp[i] = m * m ^ (i — k) + (m ^ k — m) * dp[i — k] = m ^ (i — k + 1) + (m ^ k — m) * dp[i- k]. Pre-computing the powers of m will lead to a time complexity O(n). UPD: My bad this is not true.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    This isn't right: you are not handling the possibility that some suffix of the first $$$i - K$$$ elements and some prefix of the last $$$K$$$ elements combine to form a sequence of $$$K$$$ consecutive identical elements.

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Here's one way to do it: let $$$f(i)$$$ be the number of ways to assign the first $$$i$$$ values subject to the constraint that no $$$K$$$ consecutive values are equal. Then $$$f(0) = 1$$$, $$$f(i < 0) = 0$$$, and $$$f(i) = (M - 1) \sum_{k = 1}^{K - 1} f(i - k)$$$.

Why? Suppose that the value of the last assigned element is $$$x \in [1, M]$$$. The number of consecutive elements with value $$$x$$$ appearing at the tail of the sequence is between $$$1$$$ and $$$K - 1$$$. Call that number $$$k$$$. The $$$(i-k)^{th}$$$ element should differ from $$$x$$$. For each assignment to the first $$$i - k$$$ values, there are $$$M - 1$$$ choices for $$$x$$$ which do not match the value assigned to the $$$(i-k)^{th}$$$ element.

So, we can find $$$f(N)$$$ in $$$O(NK)$$$ or with prefix sums in $$$O(N)$$$. The answer you want is $$$M^N - f(N)$$$.

When $$$K$$$ is small, we can also write the recurrence for $$$f$$$ as a matrix and find $$$f(N)$$$ with fast exponentiation in $$$O(K^3logN)$$$.

→ Reply