自动搬运

查看原文

来自洛谷，原作者为

	donghanwen1225 一只啥都不会的蒟蒻

搬运于2025-08-24 22:39:04，当前版本为作者最后更新于2022-07-20 22:54:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\text{upd on 2022.08.02}$：修复一些 LaTeX 的错误，以及 phigros 萌新已经把 Aleph-0 打到 S 959057（acc 98.57%）了（

---

$\text{step 1.}$ 我们考虑 $f(x)$ 的值代表了什么。

我们先进行一些打表：

$$\begin{aligned}f(0)&=0\\f(1)&=1\\f(2)&=2f(1)=2=2\times1\\f(3)&=2f(1)+ \dfrac{2}{3-1}f(1)+3=6=3\times2\\f(4)&=2f(2)=4=4\times1\\f(5)&=2f(2)+\dfrac{2}{5-1}f(2)+5=10=5\times2\\f(6)&=2f(3)=12=6\times2\\f(7)&=2f(3)+\dfrac{2}{7-1}f(3)+7=21=7\times3\end{aligned}$$

由此可以猜想：$f(x)=x\times\text{popcount}(x)$。以下归纳证明此式：

$(1)$ 当 $n=0,1$ 时，有 $f(0)=0,f(1)=1$ 满足此式。

$(2)$ 假设 $n\leq k\;(k\geq 1)$ 时均已满足此式。考虑当 $n=k+1$ 时，

若 $k+1$ 是奇数，则 $k$ 是偶数且 $f(k+1)=2f\left(\dfrac{k}{2}\right)+\dfrac{2}{k}f\left(\dfrac{k}{2}\right)+(k+1)=f(k)+\dfrac{f(k)}{k}+(k+1)=(k+1)(\text{popcount}(k)+1)=(k+1)\text{popcount}(k+1)$，满足此式；

若 $k+1$ 是偶数，则 $f(k+1)=2f\left(\dfrac{k+1}{2}\right)=(k+1)\text{popcount}\left(\dfrac{k+1}{2}\right)=(k+1)\text{popcount}(k+1)$，也满足此式。

于是题目所求的式子即为 $\sum\limits_{i=0}^{r}i^k\text{popcount}^k(i)$。

$\text{step 2.}$ 注意到 $r$ 很大，但 $k$ 较小，这提示我们思考数位 dp。

设 $dp_{i,j,k}$ 表示不超过 $2^i-1$ 的数中，满足 $\text{popcount}(x)=j$ 的 $x$ 的 $k$ 次方和。注意到我们没有把 $j^k$ 也乘进去，这是为了后面方便。

考虑当 $k=0$ 时，$dp_{i,j,0}$ 就表示 $\text{popcount}$ 为 $j$ 的数字个数，显然应当为 $C_{i}^{j}$。

考虑当 $i=1$ 时，我们只考虑 $1$，则有 $dp_{1,1,k}=1$。

接下来，我们考虑如何由 $i-1$ 的状态转移到 $i$ 的状态。首先我们令 $dp_{i,j,k}=dp_{i-1,j,k}$，则只需考虑形如 $2^{i-1}+p\;(p\in[0,2^{i-1}-1])$ 的数的贡献；

对于每个满足 $\text{popcount(p)}=j$ 的 $p$，它的贡献是 $(2^{i-1}+p)^k(j+1)^k=(j+1)^k\left(\sum\limits_{l=0}^{k}C_{k}^{l}\left(2^{i-1}\right)^lp^{k-l}\right)$。

观察此式，如果不考虑 $(j+1)^k$，后面式子中 $p^{k-l}$ 之和应当为 $dp_{i-1,j,k-l}$。这意味着 $dp_{i,j+1,k}=\sum\limits_{l=0}^{k}C_{k}^{l}\left(2^{i-1}\right)^ldp_{i-1,j,k-l}$。

于是我们就完成了 $dp_{i,j,k}$ 的预处理。这部分的时间复杂度为 $O\left(\log^2rk^2\right)=63^2\times30^2\approx3.5\times10^6$。

接下来对于每次询问的 $r$，我们只需对于其每个二进制位，用数位 dp 的方法进行计算。转移与上述过程一样，但是要注意统计当前已经考虑过的部分之和与二进制位为 $1$ 的个数，并把这部分贡献加入（具体参考代码的主函数部分）。

时间复杂度为 $O(t\log^2rk)\approx1.2\times10^8$（由于 $k$ 是给定的，可以减少一个枚举 $k$ 的复杂度），因为常数很小，可以通过此题。

code：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1000000007;
typedef long long ll;
int t,k,fj[65];ll r,dp[65][65][31],C[65][65];
ll ksm(ll d,ll cf)
{
	ll ans=1;
	while(cf)
	{
		if(cf&1) ans=ans*d%mod;
		d=d*d%mod;cf>>=1;
	}
	return ans;
}
void init()
{
	C[0][0]=1;
	for(int i=1;i<=64;i++)
	{
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;
	}
	for(int i=1;i<=30;i++) dp[1][1][i]=1;
	for(int i=1;i<=63;i++)for(int j=0;j<=i;j++)dp[i][j][0]=C[i][j];
	for(int i=2;i<=63;i++)
		for(int j=1;j<=i;j++)
			for(int k=1;k<=30;k++)
			{
				dp[i][j][k]=dp[i-1][j][k];ll q=(1ll<<(i-1))%mod;
				if(j==1){dp[i][j][k]=(dp[i][j][k]+ksm(q,k))%mod;continue;}
				for(int l=0;l<=k;l++)
					dp[i][j][k]=(dp[i][j][k]+C[k][l]*ksm(q,k-l)%mod*dp[i-1][j-1][l]%mod)%mod;
			}
}
int main()
{
	init();
	scanf("%d",&t);
	while(t--)
	{
		scanf("%lld%d",&r,&k);
		if(k==0){printf("%lld\n",(r%mod+1)%mod);continue;}
		int ws=0;ll tr=r;memset(fj,0,sizeof(fj));
		while(tr){fj[++ws]=tr&1;tr>>=1;}
		int cur=0;ll dq=0,ans=0;
		for(int i=ws;i>=1;i--)
			if(fj[i]==1)
			{
				for(int j=0;j<=i-1;j++)
				{
					ll tmp=ksm(cur+j,k);
					if(j==0){ans=(ans+tmp*ksm(dq,k)%mod)%mod;continue;}
					for(int l=0;l<=k;l++)
						ans=(ans+tmp*C[k][l]%mod*ksm(dq,k-l)%mod*dp[i-1][j][l]%mod)%mod;
				}
				cur++;dq=(dq+(1ll<<(i-1)))%mod;
			}
		printf("%lld\n",(ans+ksm(r%mod*cur%mod,k))%mod);
	}
	return 0;
}