ABC406E 题解

E. Popcount Sum 3

题意

多测，共 $T$ 组数据。

给你整数 $N$ 和 $K$，找到所有满足以下条件的数 $x$ 的和：

• $\text{popcount}(x)=K$ 且 $ x\le N$，其中 $\text{popcount(x)}$ 表示 $x$ 在二进制形式中 $1$ 的数量

思路

提供一个不是 $\text{DP}$ 的做法。为了方便表示，设 $998244353=M$；

对于 $N$ 二进制形式中每个是 $1$ 的位数 $d$（从后往前数，最右边的是第 $1$ 位），把它之前（不包括自己）的所有是 $1$ 的位都默认设成 $1$，设之前有 $cnt$ 位是 $1$（可以预处理 出前面是 $1$ 的数位表示的数的总和，即 $sum={\sum }_{i=[x]在二进制形式下的位数}^{d+1}{2}^{d-1}$），在之后（不包括自己）的共 $d-1$ 位中任意放入 $K-cnt$ 个 $1$，很明显，方案数为 ${\text{C}}_{d-1}^{K-cnt}$。我们把这些方案全部列出来：

下图展示了 $k-cnt=3,d-1=5$ 的情况 ：

它是 ${\text{C}}_{d-1}^{K-cnt}$ 个长度为 $K-cnt$ 的序列，每个数在 $1\sim d-1$ 之间，可以证明，$1\sim d-1$ 之间的每一个数（每一位）出现的次数都一样，即每个数字（每一位）出现了 $t=\frac{{\text{C}}_{d-1}^{K-cnt}\times (K-cnt)}{d-1}$ 次：
第 $i$ 位表示的数为 $2^i$，则本次答案增加 $\Delta ={\sum }_{i=1}^{d-2}{2}^i\times t+{\text{C}}_{d-1}^{K-cnt}\times sum=\frac{{\text{C}}_{d-1}^{K-cnt}\times (K-cnt)}{d-1}\times (2^{d-1}-1)+{\text{C}}_{d-1}^{K-cnt}\times sum$。

如果 $cnt=K$ 就把答案加上 $sum$ 并跳出循环。

注意点：

• 因为先取模再除法可能会出错，所以我们把除法换成乘法逆元，即 $\frac{1}{d-1}\mathrm{mod}M=(d-1{)}^{M-2}\mathrm{mod}M$（可以用费马小定理证明）。

• 同理，${\text{C}}_n^k$ 也需要预处理，预处理出 $fac{t}_i=i!\mathrm{mod}M$，$re{v}_i=\frac{1}{i!}\mathrm{mod}M$， ${\text{C}}_n^k=fac{t}_n\times re{v}_k\times re{v}_{n-k}$。

• 记得开 $\text{long long}$，计算幂要用快速幂，不然超时。

C++ 代码

#include<bits/stdc++.h>
#define int long long
#define mpr make_pair
#define pb push_back
#define sz(v) (int)v.size()
using namespace std;
const int MOD=998244353;
int n,k;
int fact[64],rev[64];
int pw(int a,int b){int res=1;while(b){if(b&1) res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;
}
int C(int n,int k){if(n<k) return 0;return fact[n]*rev[k]%MOD*rev[n-k]%MOD;
}
void solve(){cin>>n>>k;vector<bool> v;while(n!=0){v.pb(n&1);n>>=1;}reverse(v.begin(),v.end());int ans=0,cnt=0,sum=0;for(int i=0;i<sz(v);i++){if(v[i]==0) continue;int dig=sz(v)-i;ans=(ans+(pw(2,dig-1)-1)*(C(dig-1,k-cnt)*(k-cnt)%MOD*pw(dig-1,MOD-2)%MOD)%MOD)%MOD;ans=(ans+C(dig-1,k-cnt)*sum)%MOD;cnt++;sum+=pw(2,dig-1);if(cnt==k){ans=(ans+sum)%MOD;break;}}cout<<ans<<endl;
}
signed main(){fact[1]=fact[0]=rev[0]=1;for(int i=2;i<=61;i++){fact[i]=fact[i-1]*i%MOD;}rev[61]=pw(fact[61],MOD-2);for(int i=60;i>=1;i--){rev[i]=rev[i+1]*(i+1)%MOD;}int T;cin>>T;while(T--){solve();}return 0;
}