{"problem":{"name":"十二重骗分法（Cheating XII）","description":{"content":"一阵恍惚过后，你发现自己坐在机房里。一看时间，现在竟然是 2202 年！你又环视了一下周围的情况，原来自己在 CSP-J 2202 的考场上。 你还没搞清楚情况时，似乎听见有人对你低语：「想知道怎么回事吗？那就展现你以往的能力，把这次的 CSP-J 也 AK 掉吧。」 于是你看到四个题分别是：   1. 输入一个正整数 $n$，求 $\\lfloor \\sqrt n \\rfloor$。   ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8562"},"statements":[{"statement_type":"Markdown","content":"一阵恍惚过后，你发现自己坐在机房里。一看时间，现在竟然是 2202 年！你又环视了一下周围的情况，原来自己在 CSP-J 2202 的考场上。\n\n你还没搞清楚情况时，似乎听见有人对你低语：「想知道怎么回事吗？那就展现你以往的能力，把这次的 CSP-J 也 AK 掉吧。」\n\n于是你看到四个题分别是：  \n\n1. 输入一个正整数 $n$，求 $\\lfloor \\sqrt n \\rfloor$。  \n\n2. 给定一个左右各有 $n$ 个点的二分图，与其中的边，求它完美匹配的方案数，答案对 $998244353$ 取模。\n\n3. 生命游戏（Conway's Game of Life）进行于一个无限大的二维网格上，每个格子要么是空地，要么有一个细胞。每个时刻都会进行一轮**迭代**，规则如下：\n![](https://cdn.luogu.com.cn/upload/image_hosting/do0c6ras.png)  \n现在，给定你初始状态，求迭代 $k$ 次后的细胞数。  \nps：你可以在 [这里](https://playgameoflife.com/) 试玩。\n\n4. 给你一个 $n$ 个点、 $m$ 条边的无向图，每个点都可以涂上 $k$ 种颜色中的一种，且相邻的点（即有边直接相连的点）不能有相同的颜色。求有多少种染色方案，答案对 $998244353$ 取模。\n\n「这怎么可能啊！」你差点惊叫出来。不过你发现，唯独你的电脑上有题目的输入数据！你想暴力跑出答案，却发现 2202 年的评测机性能和一百多年前没差别。\n\n那该怎么办呢？总之只能靠自己了吧。\n\n**输入数据可以在题目下方的附件中下载。**\n\n## Input\n\n第一行一个正整数 $T$，表示测试点编号。\n\n若 $T \\in \\{ 1,2\\}$，表示 Subtask 1。接下来一行仅一个正整数 $n$。\n\n若 $T \\in \\{3,4,5,6\\}$，表示 Subtask 2。第二行一个正整数 $n$。\n接下来 $n$ 行，第 $i$ 行先输入一个正整数 $m_i$，表示左部分第 $i$ 个点（记作 $u_i$）的度数为 $m_i$；后面接着 $m_i$ 个整数 $v_{i,1},v_{i,2},\\cdots,v_{i,m_i}$，依次表示与 $u_i$ 连接的右部分节点编号。  \n\n若 $T \\in\\{ 7,8,9\\}$，表示 Subtask 3。第二行输入三个正整数 $n,m,k$，表示输入的初始形态有 $n$ 行 $m$ 列（除此之外是无限大的二维平面，没有其它细胞），迭代 $k$ 次。接下来 $n$ 行，每行一个长度为 $m$ 的 01 串，`0` 表示空地，`1` 表示细胞，描述了一行的形态。\n\n若 $T \\in\\{ 10,11,12\\}$，表示 Subtask 4。第二行输入三个正整数 $n,m,k$。接下来 $m$ 行，每行两个正整数 $u,v$ 描述一条无向边，保证无重边和自环。\n\n## Output\n\n输出一行一个正整数，表示答案。\n\n[samples]\n\n## Note\n\n【样例 $1$ 解释】  \n输入中 $T=3$，要求的问题是二分图完美匹配计数。  \n可以发现，只有两种匹配方案：$1 \\leftrightarrow 1,2 \\leftrightarrow 2,3 \\leftrightarrow 3$\n 或 $1 \\leftrightarrow 2,2 \\leftrightarrow 3,3 \\leftrightarrow 1$。\n \n 【样例 $2$ 解释】  \n 输入中 $T=7$，要求的问题是预测生命游戏细胞数。给出的输入是：  \n ![](https://cdn.luogu.com.cn/upload/image_hosting/0ukc526n.png)   \n 经过 $133$ 轮迭代后为：  \n ![](https://cdn.luogu.com.cn/upload/image_hosting/g6yz6nf3.png)  \n 可以数出其中细胞数为 $129$。  \n \n样例中虽然有 $T\\in[1,12]$，但并不代表实际输入。  \n\n【测试点分数信息】   \n\n| 编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |\n| -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: |\n| **分数** | $7$ | $8$ | $6$ | $7$ | $9$ | $11$ | $8$ | $9$ | $10$ | $7$ | $8$ | $10$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8562","tags":["数学","洛谷原创","提交答案","枚举","组合数学"],"sample_group":[["3\n3\n2 1 2\n2 2 3\n2 1 3","2"],["7\n5 5 133\n10001\n00000\n11111\n00000\n01010","129"]],"created_at":"2026-03-03 11:09:25"}}