P8440 题解
donghanwen1225
·
·
题解
------------
$\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：
```cpp
#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;
}
```