{"problem":{"name":"[HUSTFC 2023] 序列配对","description":{"content":"你有一个长度为 $n$ 的序列 $a_1,a_2,\\dots,a_n$，初始序列内任意元素 $a_i=0$。 之后会告诉你 $n$ 组配对信息，每组配对信息形如整数对 $(l,r)$，表示将 $a_l$ 和 $a_r$ 进行配对。在配对之后，你必须执行下面两种操作之一（不可全选）： - 令 $a_l$ 加 $1$，随后 $a_r$ 减 $1$。 - 令 $a_r$ 加 $1$，随后 $a_l$ ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9773"},"statements":[{"statement_type":"Markdown","content":"你有一个长度为 $n$ 的序列 $a_1,a_2,\\dots,a_n$，初始序列内任意元素 $a_i=0$。\n\n之后会告诉你 $n$ 组配对信息，每组配对信息形如整数对 $(l,r)$，表示将 $a_l$ 和 $a_r$ 进行配对。在配对之后，你必须执行下面两种操作之一（不可全选）：\n- 令 $a_l$ 加 $1$，随后 $a_r$ 减 $1$。\n- 令 $a_r$ 加 $1$，随后 $a_l$ 减 $1$。\n\n你得知这些配对信息遵循着一个奇妙的规定：在 $n$ 组整数对内的 $2n$ 个整数中，每个序列的下标都恰好出现 $2$ 次！\n\n此时你想知道，在所有操作方案中，使 $\\sum_{i=1}^n{a_i}^2=k$ 的方案数，由于答案可能会很大，你只需要求出其对 $998\\,244\\,353$ 取模后的结果。\n\n## Input\n\n第一行包含一个整数 $n\\ (1\\le n\\le 2\\cdot 10^5)$，表示序列的长度。\n\n接下来 $n$ 行，其中第 $i$ 行包含两个整数 $l_i,r_i\\ (1\\le l\\le r \\le n)$，表示第 $i$ 组配对信息。保证输入的这 $2n$ 个整数符合题目要求。\n\n最后一行包含一个整数 $k\\ (0\\le k \\le 10^9)$，其含义如题目所述。\n\n## Output\n\n输出一个整数，表示使 $\\sum_{i=1}^n{a_i}^2=k$ 的方案数对 $998\\,244\\,353$ 取模后的结果。\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9773","tags":["2023","O2优化","高校校赛"],"sample_group":[["3\n1 3\n2 3\n1 2\n0","2\n"],["6\n2 5\n3 6\n2 5\n4 6\n1 3\n1 4\n8","28\n"]],"created_at":"2026-03-03 11:09:25"}}