Codeforces776G

Codeforces776G题解

题意：

• 设$x$的16进制表示为$x_{n-1} \cdots x_1x_0$，那么设$h(x)=2^{x_{n-1}}|2^{x_{n-2}}| \cdots 2^{x_1}|2^{x_0}$，求区间$[l,r]$中满足$x\ xor\ h(x)< x$的数的个数。

题解：

• 显然只跟最后几位有关，就是一个16进制的数位dp。
• 用记忆化搜索的方式，$dfs(x,y,z,flag)$表示目前到第$x$位，各位的最大值为$y$，最后16位的和到现在的值为$z$，$flag$表示是否贴紧上限。

代码：

#include <bits/stdc++.h>
#define gc getchar()
#define ll long long
#define N 16
using namespace std;
int a[N];
ll dp[N][N][1<<N];
ll dfs(int x,int y,int z,int flag)
{
    if (x==0) return z>>y&1;
    if (!flag&&dp[x][y][z]!=-1) return dp[x][y][z];
    ll ret=0;
    int lim=(flag?a[x]:15);
    for (int i=0;i<=lim;i++)
        ret+=dfs(x-1,max(y,i),(x<=4)?(z|(i<<((x-1)<<2))):z,flag&&(i==lim));
    if (!flag) dp[x][y][z]=ret;
    return ret;
}
ll solve(ll now)
{
    if (now<0) return 0;
    int n=0;
    while (now)
    {
        a[++n]=now%16;
        now>>=4;
    }
    return dfs(n,0,0,1);
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int q;
    memset(dp,-1,sizeof(dp));
    cin>>q;
    while (q--)
    {
        ll l,r;
        cin>>hex>>l>>hex>>r;
        cout<<solve(r)-solve(l-1)<<endl;
    }
	return 0;
}