[RC-07] 超超立方体

Luogu

IDLGP9005

Time1000ms

Memory512MB

DifficultyP6

O2优化

有一个 $n$ 维 $(a_1-1)\times (a_2-1)\times \dots \times (a_n-1)$ 超立方体。左下角坐标为 $(1,1,\dots,1)$，右上角坐标为 $(a_1,a_2,\dots,a_n)$。考虑一个无向图，有 $a_1\times a_2\times \dots \times a_n$ 个有标号的结点。结点的标号分别为 $(x_1,\dots,x_n)\ (1\le x_i\le a_i)$，每个节点对应超立方体内部或者边界上一个整点。对于一对图上的顶点 $(U,V)\ (U=(x_1,\dots,x_n),V=(y_1,\dots,y_n))$，它们之间有边相连当且仅当 $UV$ 平行于超立方体的一条棱。换句话说，也就是 $\sum_{1\le i\le n}[x_i=y_i]=n-1$。计算该图生成树个数对 $998244353$ 取模的结果。 ## Input 第一行一个正整数 $n$。接下来一行 $n$ 个正整数 $a_1,a_2,\dots,a_n$。 ## Output 输出答案对 $998244353$ 取模的结果。 [samples] ## Note 所有数据均满足：$1\le n\le 100$，$2\le a_i\le 5000$。 - 子任务 $1$（$5$ 分）：$n=1$。 - 子任务 $2$（$5$ 分）：$n\le 3,\prod a_i\le 500$。 - 子任务 $3$（$10$ 分）：$n=2$。 - 子任务 $4$（$80$ 分）：无特殊限制。

Samples

Input #1

1
5

Output #1

Input #2

5
2 3 4 5 6

Output #2

676736091

API Response (JSON)

{
  "problem": {
    "name": "[RC-07] 超超立方体",
    "description": {
      "content": "有一个 $n$ 维 $(a_1-1)\\times (a_2-1)\\times \\dots \\times (a_n-1)$ 超立方体。左下角坐标为 $(1,1,\\dots,1)$，右上角坐标为 $(a_1,a_2,\\dots,a_n)$。 考虑一个无向图，有 $a_1\\times a_2\\times \\dots \\times a_n$ 个有标号的结点。结点的标号分别为 $(x_1,\\dots,x_",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9005"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一个 $n$ 维 $(a_1-1)\\times (a_2-1)\\times \\dots \\times (a_n-1)$ 超立方体。左下角坐标为 $(1,1,\\dots,1)$，右上角坐标为 $(a_1,a_2,\\dots,a_n)$。\n\n考虑一个无向图，有 $a_1\\times a_2\\times \\dots \\times a_n$ 个有标号的结点。结点的标号分别为 $(x_1,\\dots,x_...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments