[集训队互测 2023] Permutation Counting 2

Luogu

IDLGP10004

Time5000ms

Memory512MB

DifficultyP7

集训队互测2023组合数学容斥原理

给定 $n$，对于每组 $x,y\in [0,n)$ 求出有多少个 $1\sim n$ 的排列 $p$ 满足以下条件： - $\sum\limits_{i=1}^{n-1}[p_i<p_{i+1}]=x$。 - $\sum\limits_{i=1}^{n-1}[p^{-1}_i<p^{-1}_{i+1}]=y$。其中 $p^{-1}$ 表示 $p$ 的逆排列，满足 $p^{-1}_{p_i}=i$。答案对给定的质数 $MOD$ 取模。 ## Input 共一行，两个整数，表示 $n,MOD$。 ## Output 共 $n$ 行，每行共 $n$ 个整数，第 $i$ 行第 $j$ 列的数表示 $x=i-1,y=j-1$ 时的答案。 [samples] ## Note 对于 $100\%$ 数据，$1\le n\le 500$，$10^9\le MOD\le 1.01\times 10^9$，保证 $MOD$ 为质数。 $\operatorname{Subtask} 1(10\%):n\le 8$。 $\operatorname{Subtask} 2(15\%):n\le 16$。 $\operatorname{Subtask} 3(25\%):n\le 40$。 $\operatorname{Subtask} 4(25\%):n\le 100$。 $\operatorname{Subtask} 5(25\%):$ 无特殊限制。

Samples

Input #1

3 1000000007

Output #1

1 0 0
0 4 0
0 0 1

Input #2

5 1000000007

Output #2

Input #3

10 1000000007

Output #3

1 0 0 0 0 0 0 0 0 0
0 165 462 330 55 1 0 0 0 0
0 462 9273 22023 13750 2266 66 0 0 0
0 330 22023 147301 203610 75306 6556 66 0 0 
0 55 13750 203610 592130 423236 75306 2266 1 0
0 1 2266 75306 423236 592130 203610 13750 55 0
0 0 66 6556 75306 203610 147301 22023 330 0
0 0 0 66 2266 13750 22023 9273 462 0
0 0 0 0 1 55 330 462 165 0
0 0 0 0 0 0 0 0 0 1

API Response (JSON)

{
  "problem": {
    "name": "[集训队互测 2023] Permutation Counting 2",
    "description": {
      "content": "给定 $n$，对于每组 $x,y\\in [0,n)$ 求出有多少个 $1\\sim n$ 的排列 $p$ 满足以下条件： - $\\sum\\limits_{i=1}^{n-1}[p_i<p_{i+1}]=x$。 - $\\sum\\limits_{i=1}^{n-1}[p^{-1}_i<p^{-1}_{i+1}]=y$。 其中 $p^{-1}$ 表示 $p$ 的逆排列，满足 $p^{-1}_{p_i",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10004"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n$，对于每组 $x,y\\in [0,n)$ 求出有多少个 $1\\sim n$ 的排列 $p$ 满足以下条件：\n\n- $\\sum\\limits_{i=1}^{n-1}[p_i<p_{i+1}]=x$。\n\n- $\\sum\\limits_{i=1}^{n-1}[p^{-1}_i<p^{-1}_{i+1}]=y$。\n\n其中 $p^{-1}$ 表示 $p$ 的逆排列，满足 $p^{-1}_{p_i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments