洛谷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\) 个，则 \[ \begin{cases} g_{i,j}\times[(f_i-2)(f_j-2)-(g_{i,j}-1)],\quad b_{a_2,a_4}=\mathrm{True} \\[6pt] g_{i,j}\times[(f_i-2)(f_j-2)-(g_{i,j}-1)],\quad b_{a_2,a_4}=\mathrm{False} \end{cases} \]

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

代码：

#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;
}