{"problem":{"name":"「RiOI-2」likely","description":{"content":"对于一个长度为 $n$ 的仅包含 $\\pm1$ 的序列 $a_0\\dots a_{n-1}$，我们定义 $S(a, m) = \\displaystyle \\sum_{k = 0}^{n - 1} \\prod_{l = 0}^{m - 1} a_{(k + l) \\bmod n}$。 给定 $n, m, k$，求在 $2^n$ 个不同的序列 $a$ 里，试求出有多少不同的 $a$ 满足 $S(a,","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9501"},"statements":[{"statement_type":"Markdown","content":"对于一个长度为 $n$ 的仅包含 $\\pm1$ 的序列 $a_0\\dots a_{n-1}$，我们定义 $S(a, m) = \\displaystyle \\sum_{k = 0}^{n - 1} \\prod_{l = 0}^{m - 1} a_{(k + l) \\bmod n}$。\n\n给定 $n, m, k$，求在 $2^n$ 个不同的序列 $a$ 里，试求出有多少不同的 $a$ 满足 $S(a, m) = k$。\n\n答案对 $998,\\!244,\\!353$ 取模。\n\n## Input\n\n**本题有多组数据。**\n\n第一行，一个正整数 $T$ 表示测试数据组数。\n\n接下来 $T$ 行，每行三个整数，依次表示 $n, m, k$。\n\n## Output\n\n共 $T$ 行，每行一个整数，表示一组数据的答案。\n\n[samples]\n\n## Background\n\n小 E 喜欢把东西排成环状，而不是一条链。\n\n近些天，她在学校学到了正负号。她把它们放在了环上，作为密码。\n\n然而，她现在已然忘却了，只看到草稿纸上的一个数字。那是什么？\n\n## Note\n\n### 样例解释\n\n对于第一组样例的第一组数据，不符合要求的只有 $a=[1,1,1,1]$，$a=[-1,-1,-1,-1]$，$a=[1,-1,1,-1]$ 和 $a=[-1,1,-1,1]$，所以答案为 $2^4-4=12$。\n\n对于第一组样例的第二组数据，符合要求的只有 $a$ 中恰有奇数个 $-1$，所以答案为 $2^8=256$。\n\n### 数据规模与约定\n\n**本题开启捆绑测试。**\n\n| $\\text{Subtask}$ | 分值 | $T \\leq$ | $\\sum n \\leq$ | $m \\leq$ |\n| :-: | :-: | :-: | :-: | :-: |\n| $0$ | $5$ | $1$ | $20$ | / |\n| $1$ | $10$ | $5$ | $10^5$ | $2$ |\n| $2$ | $10$ | $5$ | $10^5$ | $4$ |\n| $3$ | $15$ | / | $7\\times10^3$ | / |\n| $4$ | $20$ | / | $10^5$ | / |\n| $5$ | $40$ | / | / | / |\n\n对于所有数据，保证 $2 \\leq m \\leq n \\leq 5\\times 10^6$，$0 \\leq \\lvert k\\rvert \\leq n$，$1 \\leq T \\leq 10$，$\\sum n\\leq 5\\times10^6$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9501","tags":["数学","数论","洛谷原创","O2优化","生成函数","快速数论变换 NTT","洛谷月赛"],"sample_group":[["9\n4 2 0\n9 9 -9\n9 3 3\n20 8 -12\n114 5 14\n191 9 81\n1036 854 104\n998244 353 4\n2147483 64 7","12\n256\n108\n10000\n661235724\n741150826\n500003636\n222931421\n404094315"],["6\n8 4 0\n12 4 0\n16 4 0\n20 4 0\n24 4 0\n28 4 0","176\n1728\n26160\n368000\n5413856\n80212608"],["4\n6 2 0\n10 2 0\n9 9 7\n9 3 6","0\n0\n0\n0"]],"created_at":"2026-03-03 11:09:25"}}