I_love_PMK's blog

An interesting problem about sequence
By I_love_PMK, 10 years ago, In English

Given an array A has N integer (1 <= a[i] <= 100, N <= 100) and a number X (X <= 10^9)

Counting number of ways that can get X from a subsequences of A (an element can be used as many as you want)

anyone has a idea for it ?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What do you mean by getting? Is it appending or sum?

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

    it's sum

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

      Even though X is really big, it doesn't really matter because N can be maximum 100, and every element can be maximum 100; therefore, maximum sum can be 10000. Can't we just do a simple dp?

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

        an element can be used as many time as you want

        So if A = {2,1}, X = 4, so ways are : {2, 2} {2,1,1} {1,1,1,1} etc..

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

        An element can be used as many as you want, so maximum sum isn't 10^4. You can't do a simple dp here.

        → Reply
»
10 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Looks pretty straight-forward. Let dx be the answer for x. If you know dx, dx + 1, ..., dx + 99, then , so it is a linear combination of dx, dx + 1, ..., dx + 99. Which means that transition from dx, dx + 1, ..., dx + 99 to dx + 1, ..., dx + 100 can be done by matrix multiplication, and the whole problem can be solved by taking a power of this matrix (with complexity max(a[i])^3 * log(X)).

→ Reply