题解

在看题解前，建议自己先尝试分析本题，个人认为还是挺有意义的

题目分析

根据汉明距离的定义:

$$d_H(x,y)=\sum_{i=0}^{\infty}I((x\&2^i)\neq(y\&2^i))$$

不难得出，题目大意就是在求区间 $[0,n]$ 内有多少个数对 $(x,y)$ 满足：$0\le x<y\le n,\ d_H(x,y)\le k$。
如果直接暴力，在 $n\le 10^6$ 的条件下一定超时，但在 $10^6$ 的情况下，不难发现如果按位统计二进制位上的 $1$ 的个数，不仅可以计算数对间的汉明距离，也只需要 $\mathcal{O}(|n|)$ 的复杂度，再加上二进制位运算与杨辉三角（组合数）的优化，完全可以在 $\mathcal{O}(t)$ 的时间复杂度下跑完。
因为要求统计汉明距离 $d_H\le k$ 的方案数，可以想到运用组合数来进行快速计算，又由于每一次都是统计从 $0$ 至 $n$ 的情况，可以通过预处理组合数的前缀和来实现 $\mathcal{O}(1)$ 查询。

前置芝士

组合数学

组合：从n个不同元素中取出 $m（m\le n）$ 个元素并成一组，不考虑顺序的方案数用符号 $C_n^m$ 或 $\binom{n}{m}$ 表示。

组合数杨辉三角优化

递推公式：$\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}$。
其实也不能算是优化。

前缀和

这应该不用说了吧。

模逆元

为了实现正确计算在模运算下的除法计算，需要使用对应模逆元的乘法来达成（参考模反元素）。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=998244353;//模数
const int inv=(MOD+1)/2;//除 2 的模逆元
int C[25][25],pref[25][25];//C 为组合数，pref 记录了前缀和
inline int cntb(int  n,int b)//用于统计二进制位上数的个数（或者说贡献）
{
    int l=1LL<<(b+1),h=1LL<<b;
    int r=(n+1)%l;
    int f=n-r+1;
    if(r>h)f+=(r-h)*2;
    return f;
}
inline int addmod(int a,int b)//加法取模（主要是怕爆了，虽然几乎不可能）
{
    a+=b;
    if(a>=MOD)a-=MOD;
    return a;
}
inline int mulmod(int a,int b)//乘法取模
{
    return (a%MOD)*(b%MOD)%MOD;
}
/*
inline int mulmod(int a,int b)//本来想用这一版更安全的取模方式的，结果复杂度太高，TLE 了，QwQ
{
    a=a%MOD;
    b=b%MOD;
    int res=0;
    while(b)
    {
        if(b&1)res=(res+a)%MOD;
        a=(a+a)%MOD;
        b>>=1;
    }
    return res;
}
*/
inline void init()//预处理组合数与前缀和
{
    for(int i=0;i<=21;i++)
    {
        C[i][0]=C[i][i]=1;
        for(int j=1;j<i;j++)
        {
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
        }
    }
    for(int i=0;i<=20;i++)
    {
        pref[i][0]=0;
        for(int j=1;j<=21;j++)
        {
            int minn=min(i,j-1);
            if(minn>=0)
            {
                int t=0;
                for(int k=0;k<=minn;k++)t=(t+C[i][k])%MOD;
                pref[i][j]=t;
            }
            else pref[i][j]=0;
        }
    }
}
signed main() 
{
    init();
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        k=min(k,21LL);
        int ans=(n+1)%MOD;
        for(int b=0;b<=20;b++)
        {
            ans=addmod(ans,mulmod(cntb(n,b)%MOD,pref[b][k]%MOD));//用一下取模即可
        }
        ans-=((n+1)%MOD);
        //while(ans<0)ans+=MOD;//防止爆成负数了，其实不加也可以，但比赛的时候怕前面多减了，这里判一下
        ans=mulmod(ans,inv);
        cout<<ans%MOD<<endl;//之后就是快乐的输出了
    }
    return 0;
}

看着思路很简单，可是我好几个小时的成果，QwQ，若哪里思路错了或没讲清楚，勿喷。

最后，为什么这只是一道黄题，蚌埠住了，还以为至少是绿起步，QwQ。