P8941 题解

· · 题解

P8941 题解

建议在博客里食用：

题目链接

题目描述

给定 n,k,p，求有多少有序 p 元组 (a_1,a_2,\cdots,a_p) 满足

（此处分别记为约束 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]

接下来分两种情况讨论：

当然，不要忘记舍去 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)，可以通过本题（而且跑的飞快）。