{"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若对于简单有向图 $G$，不存在其他简单有向图 $H$ 与其本质相同，则我们称图 $G$ 为 **单图**。\n\n$T$ 次询问，每次询问给定一个正整数 $n$，请你回答 $n$ 个点的**有标号**单图数。\n\n## Input\n\n**本题采用多组输入。**\n\n第一行输入两个整数 $T,mod$，表示数据组数与模数。\n\n接下来 $T$ 行每行一个整数，表示这组数据的 $n$。\n\n## Output\n\n输出 $T$ 行，第 $i$ 行表示第 $i$ 组数据的答案对 $mod$ 取模的值。\n\n[samples]\n\n## Background\n\n与其编写苍白无力的背景，不如出更有质量的题。\n\n## Note\n\n#### 数据范围\n\n**「本题采用捆绑测试」** \n\n- $\\operatorname{Subtask} 1(30\\%)$：$T = 1$，$n \\leq 5$。\n\n- $\\operatorname{Subtask} 2(50\\%)$：$T \\leq 10$。\n\n- $\\operatorname{Subtask} 3(20\\%)$：无特殊限制。\n\n对于 $100\\%$ 的数据满足：$1 \\leq T,n \\leq 1000$，$1\\leq mod \\leq 10^9$。\n\n#### 说明提示\n\n这里给出一些例子来帮助理解单图的含义：\n\n------------\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/kykl8fg8.png)[](https://www.luogu.com.cn/paste/0tbbkesd)\n\n这是一张单图，可以证明不存在其他图与其本质相同。\n\n------------\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/5appj8pr.png)\n\n这不是一张单图，因为我们可以添加边 $(5,2)$ 构造出与其本质相同的图。\n\n------------\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/wtsep329.png)\n\n这不是一张单图，因为我们可以删去边 $(1,3)$ 构造出与其本质相同的图。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9374","tags":["图论","O2优化","组合数学"],"sample_group":[["5 998244353\n1\n3\n5\n12\n888","1\n16\n986\n328006912\n535268381"]],"created_at":"2026-03-03 11:09:25"}}