{"problem":{"name":"[DTOI 2023] D. Goodbye 2022","description":{"content":"这次的题目背景和 luanmenglei 没有一点关系。 给定 $n,k,p$，求有多少有序 $p$ 元组 $(a_1,a_2,\\cdots,a_p)$ 满足 - $\\forall i \\in [1,p]$，$a_i\\in [1,n]$。 - $\\forall i\\in [1,p)$，$\\operatorname{popcount}(a_i\\oplus a_{i+1})=k$。 - $\\f","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":"LGP8941"},"statements":[{"statement_type":"Markdown","content":"这次的题目背景和 luanmenglei 没有一点关系。\n\n给定 $n,k,p$，求有多少有序 $p$ 元组 $(a_1,a_2,\\cdots,a_p)$ 满足\n\n- $\\forall i \\in [1,p]$，$a_i\\in [1,n]$。\n\n- $\\forall i\\in [1,p)$，$\\operatorname{popcount}(a_i\\oplus a_{i+1})=k$。\n\n- $\\forall i,j\\in[1,p],i\\neq j$，$a_i\\neq a_j$。\n\n答案对 $998244353$ 取模。\n\n---\n\n- 其中 $\\operatorname{popcount}(x)$ 表示 $x$ 在二进制表达下 $1$ 的个数。\n- $\\oplus$ 表示按位异或操作。\n- 两个有序 $p$ 元组 $(a_1,a_2,\\dots,a_p)$，$(b_1,b_2,\\dots,b_p)$ 不同当且仅当存在 $i\\in[1,p]$ 使得 $a_i\\neq b_i$。\n\n## Input\n\n一行三个正整数 $n,k,p$。\n\n## Output\n\n一行一个数，表示答案。\n\n[samples]\n\n## Background\n\n> 我用烟花宣告，用挥手告别，用鞠躬感谢，过去的都已经过去，接下来的路我要悠闲地走，愉悦地走，脚步如同时间不会停止，下一年，我们还会再会。\n\n## Note\n\n对于所有测试数据，保证 $1\\leq n \\leq 1000$，$1\\leq k\\leq \\lfloor \\log_2 n\\rfloor$，$1 \\leq p \\leq 5$。\n\n每个测试点的具体限制见下表：\n\n|  测试点编号  |      $n\\leq$ | $p =$ |\n| :-: | :-: |:-:|\n| $1$ | $1000$ | $1$ |\n|  $2 \\sim 3$  |       $1000$       |$2$|\n| $4 \\sim 5$ | $300$ |$3$|\n|  $6 \\sim 12$  |      $1000$      |$3$|\n| $13 \\sim 15$ | $1000$ |$4$|\n| $16 \\sim 21$ | $300$ |$5$|\n| $22 \\sim 25$ | $1000$ |$5$|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8941","tags":["洛谷原创","O2优化","洛谷月赛"],"sample_group":[["5 1 2","8"],["6 1 3","12"],["7 1 4","48"],["8 3 5","6"],["9 2 5","72"],["114 3 3","106624"],["514 3 4","296097032"],["1000 7 5","569405945"],["1000 7 1","1000"]],"created_at":"2026-03-03 11:09:25"}}