洛谷P8941 [SSOI 2023 easy Round] D. Goodbye 2022 题解

题目链接：P8941 [SSOI 2023 easy Round] D. Goodbye 2022

题意：

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

输入格式：

一行三个正整数 $n,k,p$ 。

输出格式：

一行一个数，表示答案。

数据范围：

对于所有测试数据，保证 $1\leq n \leq 1000$ ， $1\leq k\leq \lfloor \log_2 n\rfloor$ ， $1 \leq p \leq 5$ 。

注意到 $n$ 很小，所以记一个bitset<N> b[N] 有 $b_{i,j} = [\mathrm{popc}(i \oplus j) = k]$ ，然后暴力算出来，并记

$\begin{gathered} f_i=\sum_{j=1}^n[\operatorname{popc}(i \oplus j)=k]=\operatorname{popc}(b_{i}) \\ g_{i,j}=\sum_{l=1}^n[\operatorname{popc}(i \oplus l)=k\land \operatorname{popc}(j \oplus l)=k]=\operatorname{popc}(b_i\, \&\, b_j) \end{gathered}$

接着分类讨论 $p$ 的情况。

$p=1$ ，答案为 $n$ 。
$p=2$ ，枚举 $a_1$ ，答案为 $\sum_{i=1}^{n}f_i$ 。
$p=3$ ，枚举 $a_2$ ，则 $a_1$ 的方案数为 $f_{a_2}$ ， $a_3$ 的方案数为 $f_{a_2}-1$ ，故答案就是 $\sum_{i=1}^n f_i(f_i-1)$
$p=4$ ，枚举 $a_2,a_3$ ，显然 $b_{a_2,a_3}=\mathrm{True}$ ，否则不合法。

此时 $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$ 的情况，答案就是 $\sum_{i=1}^n \sum_{j=1}^n [b_{i,j}=\mathrm{True}]\times[(f_i-1)(f_j-1)-g_{i,j})]$
$p=5$ ，枚举 $a_2,a_4$ ，进一步分类讨论 $b_{a_2,a_4}$ ：
- $b_{a_2,a_4}=\mathrm{True}$ ，此时 $a_1$ 的取值有 $f_{a_2}-2$ 个（除了 $a_3,a_4$ ）， $a_5$ 同理有 $f_{a_4}-2$ 个。
- $b_{a_2,a_4}=\mathrm{False}$ ，此时 $a_1$ 的取值有 $f_{a_2}-1$ 个（除了 $a_3$ ）， $a_5$ 同理有 $f_{a_4}-1$ 个。
去掉 $a_1=a_5$ 的情况，由于 $a_3$ 已经占用了一个 $g_{a_2,a_4}$ 的位置，故该情况有 $g_{a_2,a_4}-1$ 个，则
{gi,j×[(fi−2)(fj−2)−(gi,j−1)],ba2,a4=Truegi,j×[(fi−2)(fj−2)−(gi,j−1)],ba2,a4=False

时间复杂度 $\mathcal{O}\left(\dfrac{n^3}{\omega}\right)$

代码：

cpp

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 998244353;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
void add(int &x, int y) { (x += y) >= mod ? x -= mod : 0; }
#define popc(x) __builtin_popcountll(x)
#define N ((int)(1e3 + 15))

bitset<N> b[N];
int n,k,p,res,f[N],g[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> k >> p;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) b[i][j] = (popc(i ^ j) == k);
    for(int i = 1; i <= n; i++) f[i] = b[i].count();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++) g[i][j] = (b[i] & b[j]).count();
    if(p == 1) return cout << (res = n) << '\n', 0;
    if(p == 2) { for(int i = 1; i <= n; i++) add(res, f[i]); cout << res << '\n'; }
    else if(p == 3) {
        for(int i = 1; i <= n; i++) add(res, f[i] * (f[i] - 1) % mod);
        cout << res << '\n';
    }else if(p == 4) {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++) if(b[i][j])
                add(res, (((f[i] - 1) * (f[j] - 1) - g[i][j]) % mod + mod) % mod);
        cout << res << '\n';
    }else if(p == 5) {
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++) if(i != j) {
                int x = (f[i] - (b[i][j] ? 2 : 1)) * (f[j] - (b[i][j] ? 2 : 1)) % mod;
                add(res, (g[i][j] * (x - g[i][j] + 1) % mod + mod) % mod);
            }
        cout << res << '\n';
    }
    return 0;
}