[DTOI 2023] D. Goodbye 2022

Luogu

IDLGP8941

Time1000ms

Memory128MB

DifficultyP5

洛谷原创O2优化洛谷月赛

这次的题目背景和 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$。 - $\forall i,j\in[1,p],i\neq j$，$a_i\neq a_j$。答案对 $998244353$ 取模。 --- - 其中 $\operatorname{popcount}(x)$ 表示 $x$ 在二进制表达下 $1$ 的个数。 - $\oplus$ 表示按位异或操作。 - 两个有序 $p$ 元组 $(a_1,a_2,\dots,a_p)$，$(b_1,b_2,\dots,b_p)$ 不同当且仅当存在 $i\in[1,p]$ 使得 $a_i\neq b_i$。 ## Input 一行三个正整数 $n,k,p$。 ## Output 一行一个数，表示答案。 [samples] ## Background > 我用烟花宣告，用挥手告别，用鞠躬感谢，过去的都已经过去，接下来的路我要悠闲地走，愉悦地走，脚步如同时间不会停止，下一年，我们还会再会。 ## Note 对于所有测试数据，保证 $1\leq n \leq 1000$，$1\leq k\leq \lfloor \log_2 n\rfloor$，$1 \leq p \leq 5$。每个测试点的具体限制见下表： | 测试点编号 | $n\leq$ | $p =$ | | :-: | :-: |:-:| | $1$ | $1000$ | $1$ | | $2 \sim 3$ | $1000$ |$2$| | $4 \sim 5$ | $300$ |$3$| | $6 \sim 12$ | $1000$ |$3$| | $13 \sim 15$ | $1000$ |$4$| | $16 \sim 21$ | $300$ |$5$| | $22 \sim 25$ | $1000$ |$5$|

Samples

Input #1

5 1 2

Output #1

Input #2

6 1 3

Output #2

Input #3

7 1 4

Output #3

Input #4

8 3 5

Output #4

Input #5

9 2 5

Output #5

Input #6

114 3 3

Output #6

Input #7

514 3 4

Output #7

296097032

Input #8

1000 7 5

Output #8

569405945

Input #9

1000 7 1

Output #9

API Response (JSON)

{
  "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- $\\f...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments