【模板】Pfaffian

Luogu

IDLGP10216

Time1000ms

Memory512MB

DifficultyP7

模板题

给定偶数 $n$ 与反对称矩阵 $\mathbf{A}=(a_{i,j})_{1\le i<j\le n}$，求 $\textup{Pf}(\mathbf{A})$ 对 $10^9+7$ 取模的结果。 ## Input 第一行一个正整数 $n$，保证 $n$ 是偶数。接下来 $n-1$ 行，第 $i$ 行有 $n-i$ 个非负整数，其中第 $j$ 个整数表示 $a_{i,i+j}$。 ## Output 一行一个非负整数，表示答案。 [samples] ## Background 称一个长度为 $2n$ 的排列 $\pi$ 是完美匹配，当且仅当其满足 - $\forall 1\le i\le n,\pi_{2i-1}<\pi_{2i}$ - $\forall 1\le i< n,\pi_{2i-1}<\pi_{2i+1}$ 记 $\textup{inv }\pi$ 表示 $\pi$ 的逆序对数，$\textup{sgn }\pi=(-1)^{\textup{inv }\pi}$，$\mathfrak{M}_{2n}$ 表示全体长度为 $2n$ 的完美匹配构成的集合。令 $\mathbf{A}=(a_{i,j})_{1\le i<j\le 2n}$ 是一个反对称矩阵，定义 $\mathbf{A}$ 的 $\text{Pfaffian}$ 为 $$\textup{Pf}(\mathbf{A})=\sum\limits_{\pi\in\mathfrak{M}_{2n}}(\textup{sgn }\pi)\prod\limits_{i=1}^{n}a_{\pi(2i-1),\pi(2i)}$$ ## Note 对于 $30\%$ 的数据，$n\le 10$。对于 $100\%$ 的数据，$2\leq n\le 500$，$0\le a_{i,j}<10^9+7$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "【模板】Pfaffian",
    "description": {
      "content": "给定偶数 $n$ 与反对称矩阵 $\\mathbf{A}=(a_{i,j})_{1\\le i<j\\le n}$，求 $\\textup{Pf}(\\mathbf{A})$ 对 $10^9+7$ 取模的结果。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10216"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定偶数 $n$ 与反对称矩阵 $\\mathbf{A}=(a_{i,j})_{1\\le i<j\\le n}$，求 $\\textup{Pf}(\\mathbf{A})$ 对 $10^9+7$ 取模的结果。\n\n## Input\n\n第一行一个正整数 $n$，保证 $n$ 是偶数。\n\n接下来 $n-1$ 行，第 $i$ 行有 $n-i$ 个非负整数，其中第 $j$ 个整数表示 $a_{i,i+j}$。\n\n#...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments