J. Abstract Painting

Codeforces

IDCF10283J

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Once there was a painter, expert in drawing circles on a canvas. As a tasteful painter, he found that if he drew circles according to the following restrictions, the resulting canvas would look like an abstract painting. Specially, an empty canvas was also considered an abstract painting, as it broke none of the above restrictions. There had already been $k$ circles drawn on the canvas, not breaking the above restrictions. The painter could further draw one or more circles on the canvas to get an abstract painting, or he could draw nothing and claim that it was already an excellent abstract painting. He wondered how many different abstract paintings he could possibly get. As the number may be very large, you only need to output it modulo $10^9 + 7$. The first line contains two integers $n$ and $k$ ($2 <= n <= 10^3$, $0 <= k <= 5 n$). If $k > 0$, each of the next $k$ lines contains two integers $c$ and $r$ ($1 <= c < n, 1 <= r <= floor.l frac(n, 2) floor.r$), indicating that there was already a circle centering at $(c, 0)$ with radius $r$ on the plane. It is guaranteed that the drawn $k$ circles satisfy the above restrictions. Print the number of different abstract paintings the painter might get, modulo $10^9 + 7$. ## Input The first line contains two integers $n$ and $k$ ($2 <= n <= 10^3$, $0 <= k <= 5 n$).If $k > 0$, each of the next $k$ lines contains two integers $c$ and $r$ ($1 <= c < n, 1 <= r <= floor.l frac(n, 2) floor.r$), indicating that there was already a circle centering at $(c, 0)$ with radius $r$ on the plane.It is guaranteed that the drawn $k$ circles satisfy the above restrictions. ## Output Print the number of different abstract paintings the painter might get, modulo $10^9 + 7$. [samples]

**Definitions** Let $ n \in \mathbb{Z} $, $ k \in \mathbb{Z} $ with $ 2 \leq n \leq 10^3 $, $ 0 \leq k \leq 5n $. Let $ \mathcal{C} = \{ (c, r) \mid c \in \{1, 2, \dots, n-1\},\ r \in \{1, 2, \dots, \lfloor n/2 \rfloor\} \} $ be the set of all valid circles. Let $ C_{\text{fixed}} \subseteq \mathcal{C} $ be the set of $ k $ already drawn circles, satisfying the abstract painting restrictions. **Constraints** 1. A circle $ (c, r) \in \mathcal{C} $ is valid iff $ 1 \leq c < n $ and $ 1 \leq r \leq \lfloor n/2 \rfloor $. 2. The set of circles in any abstract painting must satisfy: no two circles intersect or touch. 3. $ C_{\text{fixed}} $ is a subset of $ \mathcal{C} $ satisfying the non-intersection constraint. **Objective** Count the number of subsets $ S \subseteq \mathcal{C} \setminus C_{\text{fixed}} $ such that $ C_{\text{fixed}} \cup S $ satisfies the non-intersection constraint. Output the result modulo $ 10^9 + 7 $.

API Response (JSON)

{
  "problem": {
    "name": "J. Abstract Painting",
    "description": {
      "content": "Once there was a painter, expert in drawing circles on a canvas. As a tasteful painter, he found that if he drew circles according to the following restrictions, the resulting canvas would look like a",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10283J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Once there was a painter, expert in drawing circles on a canvas. As a tasteful painter, he found that if he drew circles according to the following restrictions, the resulting canvas would look like a...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $, $ k \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 10^3 $, $ 0 \\leq k \\leq 5n $.  \nLet $ \\mathcal{C} = \\{ (c, r) \\mid c \\in \\{1, 2, \\dots, n-1\\},\\ r \\in \\{1, 2, \\dot...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments