matrix4's blog

By matrix4, history, 3 years ago, In English

I tried to use google translator, but still can't understand this problem statement. Can someone translate/explain this problem?

Link: https://atcoder.jp/contests/typical90/tasks/typical90_o

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

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem statement:

There are N pieces of balls where 1-N number are written on them.

Then answer the following question for every k between 1-N.

-How many ways can you choose a set of ball where the absolute difference of the every ball pair's number is equal or greater than k. However, the answer can be very large, so output the result after mod 10e9+7.

Constraint:

1≤N≤10^5 N is an integer

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

    Thanks!

    So just to understand this problem a bit more precise, if N=3 and I have a set of balls {1,2,3} that would result in a difference of 1? And if I have sets like {1}, {2}, ... , {N} a difference of those would be +INF?

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I think N=3 case looks like this:

      k=1 -> answer {1,2,3}, {1,2}, {2,3}, {1,3}

      k=2 -> answer {1, 3}

      {1, 2} can't be an answer, diff(1,2) = 1 < k

      k=3 -> no answer

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        but if you look at Sample 3, for N=3 the answer is 7,4,3. Thus I guess that {1},{2},{3} are always present for any k, and your mentioned sets are added on top of that so: 4+3=7, 1+3=4, 0+3=3