本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-01 23:40:08

ABC-356D题解

注:借鉴官方题解

题意

给出 $n,m$ 求 $(\sum_{k=0}^{n}\operatorname{popcount}( k& m) ) \bmod 998244353$ 。

其中 $\operatorname{popcount}(x)$ 表示 $x$ 的二进制中 $1$ 的个数。

思路

显然可以发现，对于第 $j$ 位，当 $k$ 与 $m$ 的第 $j$ 位为 $1$ 时，才会产生贡献。

于是，本题转化成了，对于每个满足 $m$ 的第 $j$ 位为 $1$ 的 $j$，求出 $[0,n]$ 中第 $j$ 位为 $1$ 的 $k$ 的个数。

首先，$[0,2^j-1]$ 中的数，它的第 $j$ 位一定不为 $1$。

其次，$[2^j,2^{j+1})$ 中的数，它的第 $j$ 位一定为 $1$ 。

（可以写出二进制的形式加深理解）

因此，在 $[0,2^{j+1})$ 中，共有 $2^j$ 个满足上述要求的数。

而对于一个数 $i$，它的第 $j$ 位一定与 $i+2^{j+1}$ 一致（因为只对 $j+1$ 以及它左边的位有影响）。

因此，$[2^{j+1},2\times2^{j+1})$ 之间也有 $2^j$ 个数满足要求，以此类推。

所以，对于非负整数 $k$，在 $[0,k\times2^{j+1})$ 之间的整数中，有 $k\times 2^j $ 个数符合要求。

再来讨论剩下的不足 $2^{j+1}$ 的部分。

设 $l=n \bmod 2^{j+1}$。

则如果 $l \geq 2^j$，则 $k\times2^{j+1}+2^j$ 到 $k\times 2^{j+1}+l$ 之间共 $l-2^j+1$ 个数符合要求。

否则无贡献。

最后统计答案。

Code

#include <bits\/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
const int p=998244353;
int n,m;
int ans;
int fun(int i,int n)
{
    int p2=(1ll<<i);
    int k=n\/(2*p2);
    int res=k*p2;
    int l=n%(2*p2);
    if(l>=p2) res+=(l-p2+1);
    return res%p;
}
signed main()
{
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=0;i<60;i++)
	{
	    if((1ll<<i)&m) 
	    {
	        ans+=fun(i,n);
	        ans%=p;
        }
    }
    cout<<ans;
    return 0;
}