DMOPC '17 Contest 5 P4 - Intersecting Arcs

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 2.5s
Python 4.5s
Memory limit: 256M

Problem type

Bob has a row of N dots and wants to connect certain pairs of them with an arc. Define (l, r) to be an arc where l and r are the left and right endpoints respectively. Two arcs (a, b) and (c,d) have an intersection if exactly one of: c < b < d or c < a < d is true. There is an added constraint that no single dot may be the endpoint of two arcs. How many ways can the arcs be drawn so that there are exactly K intersections following the given constraints? Since this number may be very large, please output it modulo 10^9+7. Two ways are different if there is an arc in one of them which is never drawn in the other. In particular, the order in which the arcs are drawn does not matter.

Python users are recommended to use PYPY over CPython. There is a significant performance increase.


Subtask 1 [5%]

1\le N, K \le 10

Subtask 2 [15%]

1 \le N, K \le 100

Subtask 3 [80%]

1\le N, K \le 500

Input Specification

The input will be a single line containing two space-separated integers, N and K.

Output Specification

Output a single integer, the answer modulo 10^9+7.

Sample Input

5 1

Sample Output


Explanation for Sample

There are 5 ways to get exactly 1 intersection. The combinations are: (1,3) and (2,4), (1,3) and (2,5), (1,4) and (2,5), (1,4) and (3,5), (2,4) and (3,5).


  • 0
    Beautiful_Times  commented on March 15, 2018, 3:48 p.m.

    Will an editorial for this question be released?

    • 3
      r3mark  commented on March 15, 2018, 5:07 p.m.