{"problem":{"name":"[UESTCPC 2024] Add","description":{"content":"给定一个长度为 $n$ 的序列 $a_1,a_2,\\ldots,a_n$，初始时 $a_i=i$。对该序列进行 $n-1$ 次操作，其中第 $i$ 次操作为在 $[1,n-i]$ 中等概率选择一个整数 $j$，令 $a_j$ 变为 $a_j+2a_{n-i+1}$。 求操作完毕后 $a_1$ 的期望 $\\bmod\\text{ }998244353$ 的值。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10329"},"statements":[{"statement_type":"Markdown","content":"给定一个长度为 $n$ 的序列 $a_1,a_2,\\ldots,a_n$，初始时 $a_i=i$。对该序列进行 $n-1$ 次操作，其中第 $i$ 次操作为在 $[1,n-i]$ 中等概率选择一个整数 $j$，令 $a_j$ 变为 $a_j+2a_{n-i+1}$。\n\n求操作完毕后 $a_1$ 的期望 $\\bmod\\text{ }998244353$ 的值。\n\n## Input\n\n输入第一行一个正整数 $T$ $(1\\leq T\\leq 10^4)$，表示数据组数。\n\n接下来 $T$ 组数据，每组一行一个正整数 $n$ $(1\\leq n\\leq 10^9)$，表示序列的长度。\n\n## Output\n\n$T$ 行，每行一个整数表示 $a_1$ 的期望 $\\bmod\\text{ }998244353$ 的值。\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10329","tags":["数学","递推","2024","O2优化","高校校赛"],"sample_group":[["3\n4\n2\n5","30\n5\n55"],["3\n4\n3\n5","30\n14\n55"],["3\n8\n1\n3","204\n1\n14"]],"created_at":"2026-03-03 11:09:25"}}