自动搬运

查看原文

来自洛谷，原作者为

	kbtyyds 恶臭骐羽

搬运于2025-08-24 22:43:57，当前版本为作者最后更新于2023-01-28 10:58:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P8941 题解

建议在博客里食用：

题目链接

---

题目描述

给定 $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$。

（此处分别记为约束 1,2,3）

答案对 $998244353$ 取模。

前置知识：

bitset，不会的可以参考这个。

1. 预处理

我们先定义 $n$ 个长度为 $n$ 的 bitset，记为 $b$

bitset < Size > b[Size];

接着，枚举 $i,j$，并让 $b[i][j]=[\operatorname{popcount}(i\oplus j)=k]$

再记：

$$f[i]=\sum_{j=1}^n[\operatorname{popcount}(i\oplus j)=k]=b[i].\operatorname{count}() $$$$g[i][j]=\sum_{l=1}^n[\operatorname{popcount}(i\oplus l)=k][\operatorname{popcount}(j\oplus l)=k]=(b[i]\&b[j]).\operatorname{count}() $$

此处复杂度为 $\mathcal O(\dfrac {n^3} w)$，稍后会讲这两个数组的用途。

2. 计算

看题目数据范围的 $1\le p\le 5$ 可以知道我们要对 $p$ 分类讨论！

---

$p=1$

显然，约束 2,3 在只有一个数的情况下没有用。因此只需考虑约束 1 的值域约束。

显然 $ans=n$。

$p=2$

我们可以枚举 $a_1$，那么前文提到的 $f[a_1]$ 就是 $a_2$ 的合法数量。

所以 $ans=\sum\limits_{i=1}^n f[i]$

$p=3$

类似于 $p=2$，我们可以枚举 $a_2$，那么 $a_1$ 的可行方案数为 $f[a_2]$，$a_3$ 的可行方案数为 $f[a_2]-1$。（因为题目规定 $a_1\ne a_3$，因此要减去 $1$）

由乘法原理知 $ans=\sum\limits_{i=1}^n f[i](f[i]-1)$

$p=4$

说实话我不知道为什么联想到了 CSP-S 2022 T1。

考虑枚举 $a_2,a_3$，由约束 2 知只有当 $b[a_2][a_3]$ 为 $1$ 时，才有符合的 $p$ 元组。

那么 $a_1$ 的合法数量为 $f[a_2]-1$（因为 $a_1\ne a_3$），$a_4$ 的合法数量为 $f[a_3]-1$（因为 $a_2\ne a_4$）

但是，我们多算了 $a_1=a_4$ 的情况，因此要减去（即 $g[a_2][a_3]$）。

易得 $ans=\sum\limits_{i=1}^n\sum\limits_{j=1}^n[b[i][j]=1]((f[i]-1)(f[j]-1)-(g[i][j]))$

$p=5$

类似的思路，枚举 $a_2,a_4$（首先要保证 $a_2\ne a_4$），那么 $a_3$ 的合法数量为 $g[a_2][a_4]$

接下来分两种情况讨论：

1. $b[a_2][a_4]=1$。此时 $a_1$ 的合法数量为 $f[a_2]-2$（除去 $a_3,a_4$）,$a_5$ 的合法数量为 $f[a_4]-2$（除去 $a_2,a_3$）。
2. $b[a_2][a_4]=0$。此时 $a_1$ 的合法数量为 $f[a_2]-1$（除去 $a_3$）,$a_5$ 的合法数量为 $f[a_4]-1$（除去 $a_3$）。

当然，不要忘记舍去 $a_1=a_5$ 的情况。由于 $a_3$ 已经占了一个 $g[a_2][a_4]$ 的位置，因此 $a_1=a_5$ 的数量为 $g[a_2][a_4]-1$

那么 $ans=\sum\limits_{i=1}^n\sum\limits_{j=1}^n [i\ne j]\begin{cases}g[i][j](f[i]-2)(f[j]-2)-(g[i][j]-1)& b[i][j]=1\\g[i][j](f[i]-1)(f[j]-1)-(g[i][j]-1)&b[i][j]=0\end{cases}$

---

代码

可以直接根据上方公式计算，于是代码放云剪切板。

时间复杂度 $\mathcal O(\dfrac {n^3} w)$，空间复杂度 $\mathcal O(n^2)$，可以通过本题（而且跑的飞快）。