「DROI」Round 2 单图

Luogu
IDLGP9374
Time1000ms
Memory128MB
DifficultyP5
图论O2优化组合数学
我们称[简单有向图](https://www.luogu.com.cn/paste/4oz6fep2) $G,H$ **本质相同**,当且仅当: - 对于任意点对 $(u,v)$,若在图 $G$ 中从 $u$ 出发能走到 $v$,则在图 $H$ 中从 $u$ 出发能走到 $v$。反之若在图 $H$ 中从 $u$ 出发能走到 $v$,则在图 $G$ 中从 $u$ 出发也能走到 $v$。 若对于简单有向图 $G$,不存在其他简单有向图 $H$ 与其本质相同,则我们称图 $G$ 为 **单图**。 $T$ 次询问,每次询问给定一个正整数 $n$,请你回答 $n$ 个点的**有标号**单图数。 ## Input **本题采用多组输入。** 第一行输入两个整数 $T,mod$,表示数据组数与模数。 接下来 $T$ 行每行一个整数,表示这组数据的 $n$。 ## Output 输出 $T$ 行,第 $i$ 行表示第 $i$ 组数据的答案对 $mod$ 取模的值。 [samples] ## Background 与其编写苍白无力的背景,不如出更有质量的题。 ## Note #### 数据范围 **「本题采用捆绑测试」** - $\operatorname{Subtask} 1(30\%)$:$T = 1$,$n \leq 5$。 - $\operatorname{Subtask} 2(50\%)$:$T \leq 10$。 - $\operatorname{Subtask} 3(20\%)$:无特殊限制。 对于 $100\%$ 的数据满足:$1 \leq T,n \leq 1000$,$1\leq mod \leq 10^9$。 #### 说明提示 这里给出一些例子来帮助理解单图的含义: ------------ ![](https://cdn.luogu.com.cn/upload/image_hosting/kykl8fg8.png)[](https://www.luogu.com.cn/paste/0tbbkesd) 这是一张单图,可以证明不存在其他图与其本质相同。 ------------ ![](https://cdn.luogu.com.cn/upload/image_hosting/5appj8pr.png) 这不是一张单图,因为我们可以添加边 $(5,2)$ 构造出与其本质相同的图。 ------------ ![](https://cdn.luogu.com.cn/upload/image_hosting/wtsep329.png) 这不是一张单图,因为我们可以删去边 $(1,3)$ 构造出与其本质相同的图。
Samples
Input #1
5 998244353
1
3
5
12
888
Output #1
1
16
986
328006912
535268381
API Response (JSON)
{
  "problem": {
    "name": "「DROI」Round 2 单图",
    "description": {
      "content": "我们称[简单有向图](https://www.luogu.com.cn/paste/4oz6fep2) $G,H$ **本质相同**,当且仅当: - 对于任意点对 $(u,v)$,若在图 $G$ 中从 $u$ 出发能走到 $v$,则在图 $H$ 中从 $u$ 出发能走到 $v$。反之若在图 $H$ 中从 $u$ 出发能走到 $v$,则在图 $G$ 中从 $u$ 出发也能走到 $v$。 若对于简",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9374"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "我们称[简单有向图](https://www.luogu.com.cn/paste/4oz6fep2) $G,H$ **本质相同**,当且仅当:\n\n- 对于任意点对 $(u,v)$,若在图 $G$ 中从 $u$ 出发能走到 $v$,则在图 $H$ 中从 $u$ 出发能走到 $v$。反之若在图 $H$ 中从 $u$ 出发能走到 $v$,则在图 $G$ 中从 $u$ 出发也能走到 $v$。\n\n若对于简...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments