Guessing Permutation for as Long as Possible

AtCoder

IDagc059_c

Time2000ms

Memory256MB

Difficulty—

A teacher has a hidden permutation $P=(P_1,P_2,\ldots,P_N)$ of $(1,2,\cdots,N)$. You are going to determine it. To do this, you prepared a sequence of pairs of integers $(A_1,B_1),(A_2,B_2),\ldots,(A_{N(N-1)/2},B_{N(N-1)/2})$; this is a permutation of all pairs of the form $(a,b)$ ($1 \le a < b \le N$). Now, you will go over the pairs from the beginning. For a pair $(A_i, B_i)$, you will ask if $P_{A_i}<P_{B_i}$, and the teacher will tell you the answer. However, you will skip this question if you can already determine the answer to it from previous answers. Find the number of permutations $P$, for which with your algorithm you will have to ask all $\frac{N(N-1)}{2}$ questions, modulo $10^9+7$. ## Constraints * $2 \le N \leq 400$ * $1 \le A_i < B_i \le N$ * $(A_i,B_i) \neq (A_j,B_j)$ ($i \neq j$) * All values in the input are integers. ## Input Input is given from Standard Input in the following format: $N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_{N(N-1)/2}$ $B_{N(N-1)/2}$ [samples]

Samples

Input #1

2
1 2

Output #1

2

Clearly, for any permutation $P$, you need to ask $1$ question.

Input #2

Output #2

4

Consider $P=(2,3,1,4)$ as an example. In this case, you will skip the third question since you know $P_1 < P_2$ and $P_1 > P_3$ from previous questions and you can determine $P_2 > P_3$. Therefore, $P=(2,3,1,4)$ should not be counted.

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "Guessing Permutation for as Long as Possible",
    "description": {
      "content": "A teacher has a hidden permutation $P=(P_1,P_2,\\ldots,P_N)$ of $(1,2,\\cdots,N)$. You are going to determine it. To do this, you prepared a sequence of pairs of integers $(A_1,B_1),(A_2,B_2),\\ldots,(A_",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc059_c"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A teacher has a hidden permutation $P=(P_1,P_2,\\ldots,P_N)$ of $(1,2,\\cdots,N)$. You are going to determine it.\nTo do this, you prepared a sequence of pairs of integers $(A_1,B_1),(A_2,B_2),\\ldots,(A_...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments