数学、bitset

能和每个 $i$ 相邻的数可以 $O(n^2)$ 预处理得到，二进制表示中 $1$ 的数量可以用 __builtin_popcount 快速求，接下来对于每个 $p$ 讨论解法。

$$\bf{p=1}$$

输出 $n$，时间复杂度 $O(1)$。

$$\bf{p=2}$$

枚举所有数对，时间复杂度 $O(n^2)$。

$$\bf{p=3}$$

使用 $w_i$ 表示能和 $i$ 相邻的数的数量，使用 bitset 以 $O \left( \dfrac{n}{\omega} \right)$ 时间复杂度求出 $w_i$，时间复杂度 $O(n^2)$，答案如下式。

$$\sum\limits_{i=1}^{n} (w_i - 1) w_i$$

$$\bf{p=4}$$

首先预处理能和 $i$ 相邻的数，用 bitset 存起来，而 $w_i$ 直接调用 bitset.count() 求就可以了。

枚举 $4$ 元组的第 $2,3$ 个数，使用 $i,j$ 表示这俩数。用两个 bitset 与一下得到能和它俩相邻的数的数量 $x$，它们对答案的贡献为 $(w_i-1) \times (w_j-1) - x$，时间复杂度 $O \left( \dfrac{n^3}{\omega} \right)$。

$$\bf{p=5}$$

故技重施，枚举 $5$ 元组的第 $2,4$ 个数，还是使用 $i,j$ 表示这俩数。用两个 bitset 与出可选的第 $3$ 个数的数量 $x$，应该可以容斥掉重复贡献得到最终贡献。但是我没想明白咋容斥，所以直接分讨了。

显然第 $3$ 个数必须同时能和 $i,j$ 挨着，这种数有 $x$ 个。只能和第 $i$ 个数挨着的数有 $w_i - x$ 个，只能和第 $j$ 个数挨着的数有 $w_j - x$ 个。记得处理 $i,j$ 能够相邻的情况，如果它们能相邻则修改 $i,j$ 对应的 bitset $s_i,s_j$ 使得 $s_{i,j}=0,s_{j,i}=0$ 并在计算后复原，否则会由于 $w_i,w_j$ 的值错误而多算，因为此时 $i$ 不能作第 $5$ 个数，$j$ 不能作第 $1$ 个数。

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

#include<bits/stdc++.h>
using namespace std;
constexpr int mod=998'244'353;
function<int()> solution[6];
bitset<1'005> s[1'005];
int n,k,p;
int main(){
    solution[1]=[&](){return n;};
    solution[2]=[&](){
        int ret=0;
        for(int i=1;i<=n;i++) ret+=s[i].count();
        return ret;
    };
    solution[3]=[&](){
        int ret=0;
        for(int i=1;i<=n;i++) ret+=(s[i].count()-1)*s[i].count();
        return ret;
    };
    solution[4]=[&](){
        int ret=0;
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(s[i][j])
            ret=(ret+(s[i].count()-1)*(s[j].count()-1)-(s[i]&s[j]).count())%mod;
        ret=(ret+mod)%mod;
        return ret;
    };
    solution[5]=[&](){
        int ret=0;
        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(i!=j){
            if(s[i][j]) s[i][j]=0,s[j][i]=0;
            int x=(s[i]&s[j]).count();
            ret=(ret+1ll*x*(s[i].count()-x)*(s[j].count()-x))%mod;
            ret=(ret+1ll*x*(x-1)*(s[j].count()-x))%mod;
            ret=(ret+1ll*x*(s[i].count()-x)*(x-1))%mod;
            ret=(ret+1ll*x*(x-1)*(x-2))%mod;
            if(__builtin_popcount(i^j)==k) s[i][j]=1,s[j][i]=1;
        }
        ret=(ret+mod)%mod;
        return ret;
    };
    scanf("%d%d%d",&n,&k,&p);
    for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) s[i][j]=(__builtin_popcount(i^j)==k);
    printf("%d\n",solution[p]());
    return 0;
}