Блог пользователя matrix4

Автор matrix4, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 года назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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