D. Regular Bracket Sequence Again?

Codeforces

IDCF10276D

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You have a collection of $N$ opening brackets '_(_' and $N$ closing brackets '_)_'. A bracket sequence is $N$ periodic if it has a period of length $N$. Example - "_)()(_" $N = 2$. It is $N$ periodic but "_)(()_" is not. Your task is to find out how many distinct *regular bracket sequence* can be formed using these $2 N$ brackets such that sequence is *not $N$ periodic*. As the answer can be rather large, print the remainder after dividing it by $1000000007 (10^9 + 7)$. Recall what the regular bracket sequence is: For example, "_()()_", "_(())()_", "_(())_" and "_()_" are regular bracket sequences, but "_)(_", "_()(_" and "_)))_" are not. The first line contains a single integer $T (1 <= T <= 10^3)$ — the number of test cases in the input. Then $T$ test cases follow. Each query contains one integer $N (1 <= N <= 10^3)$: the number of opening and closing brackets you have. For each test from the input print the number of distinct regular bracket sequence we can form using $N$ opening bracket and $N$ closing bracket and sequence is not $N$ periodic modulo $1000000007 (10^9 + 7)$. Print the answers to the tests in the order in which the tests are given in the input. In the first query — The regular bracket sequence which can be formed by $1$ opening bracket and $1$ closing bracket is "_()_". In the second query — The regular bracket sequence which can be formed by $2$ opening bracket and $2$ closing bracket are "_(())_" and "_()()_". We discard second one because "_()()_" is $2$ periodic. In the third query — The regular bracket sequence which can be formed by $3$ opening bracket and $3$ closing bracket are "_((()))_" , "_(())()_" , "_()(())_" , "_()()()_" and "_(()())_". No one is $3$ periodic. ## Input The first line contains a single integer $T (1 <= T <= 10^3)$ — the number of test cases in the input. Then $T$ test cases follow.Each query contains one integer $N (1 <= N <= 10^3)$: the number of opening and closing brackets you have. ## Output For each test from the input print the number of distinct regular bracket sequence we can form using $N$ opening bracket and $N$ closing bracket and sequence is not $N$ periodic modulo $1000000007 (10^9 + 7)$. Print the answers to the tests in the order in which the tests are given in the input. [samples] ## Note In the first query — The regular bracket sequence which can be formed by $1$ opening bracket and $1$ closing bracket is "_()_".In the second query — The regular bracket sequence which can be formed by $2$ opening bracket and $2$ closing bracket are "_(())_" and "_()()_". We discard second one because "_()()_" is $2$ periodic.In the third query — The regular bracket sequence which can be formed by $3$ opening bracket and $3$ closing bracket are "_((()))_" , "_(())()_" , "_()(())_" , "_()()()_" and "_(()())_". No one is $3$ periodic.

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case: - Let $ n \in \mathbb{Z} $ be the number of defensive towers. - Let $ P = \{(x_i, y_i, d_i) \mid i \in \{1, \dots, n\}\} $ be the set of towers, where: - $ (x_i, y_i) \in \{1, \dots, n\}^2 $ is the position of tower $ i $, - $ d_i \in \{1, 2, 3, 4\} $ is its direction, mapping to: - $ d_i = 1 $: protects $ [x_i, n+1] \times [y_i, n+1] $ (northeast), - $ d_i = 2 $: protects $ [0, x_i] \times [y_i, n+1] $ (northwest), - $ d_i = 3 $: protects $ [0, x_i] \times [0, y_i] $ (southwest), - $ d_i = 4 $: protects $ [x_i, n+1] \times [0, y_i] $ (southeast). **Constraints** 1. $ 1 \le T \le 10^4 $ 2. $ 1 \le n \le 10^6 $ per test case 3. $ 1 \le x_i, y_i \le n $ 4. $ 1 \le d_i \le 4 $ 5. $ \sum_{\text{all test cases}} n \le 5 \times 10^6 $ **Objective** Find the minimum number of towers to cover the entire rectangular region $ [0, n+1] \times [0, n+1] $. If impossible, output "Impossible".

API Response (JSON)

{
  "problem": {
    "name": "D. Regular Bracket Sequence Again?",
    "description": {
      "content": "You have a collection of $N$ opening brackets '_(_' and $N$ closing brackets '_)_'. A bracket sequence is $N$ periodic if it has a period of length $N$. Example - \"_)()(_\" $N = 2$. It is $N$ periodi",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10276D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You have a collection of $N$ opening brackets '_(_' and $N$ closing brackets '_)_'.\n\nA bracket sequence is $N$ periodic if it has a period of length $N$.\n\nExample - \"_)()(_\" $N = 2$. It is $N$ periodi...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ be the number of defensive towers.  \n- Let $ P = \\{(x_i, y_i, d_i) \\mid i \\in...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments