题解：CF2086E Zebra-like Numbers

_O_v_O_ · 2025-04-06 16:39:20 · 题解

我们发现，最多只有 30 个 \le 10^{18} 的「斑马数」。

我们设从小到大第 i 个为 t_i，很显然，t_i=t_{i-1}\times 4+1。
我们设 x 可以表示为 \sum_{i=1}^{30} v_i\times t_i，我们发现，\max\{v_i\}\le 4，因为若一个 v_i>4，那么不如换成一个 v_{i+1}。
同时，我们发现若有 v_i=4，那么 v_{i-1}=v_{i-2}=\cdots =v_1=0，因为如果有的话也可以换算成一个更高位的数。

那么我们不妨把 x 放在一个特殊的进制下考虑，第 i 位的进制为 v_i，然后我们就发现这个东西可以数位 dp，具体的，我们设 dp_{pos,limit_1,sum,limit_2} 为当前来到了 pos 位，有/没有抵着数位，当前的数位和，前面是否有 4，的方案数，转移是容易的。

#include<bits/stdc++.h>
using namespace std;
#define int long long

int l,r,k;
int t[40],dp[40][2][90][2],dig[40];

int dfs(int pos,bool limit,int sum,bool limit2){
    if(sum>k) return 0;
    if(pos==0) return sum==k;
    if(dp[pos][limit][sum][limit2]!=-1) return dp[pos][limit][sum][limit2];
    int up;
    if(limit2) up=0;
    else if(limit) up=dig[pos];
    else up=4;
    int ans=0;
    for(int i=0;i<=up;i++){
        ans+=dfs(pos-1,(limit&&i==up),sum+i,(limit2||i==4));
    }
    return dp[pos][limit][sum][limit2]=ans;
}

int solve(int x){
    memset(dp,-1,sizeof dp);
    int cnt=30;
    for(int i=30;i>=1;i--){
        dig[i]=0;
        while(x>=t[i]) x-=t[i],dig[i]++;
    }
    return dfs(30,1,0,0);
} 

signed main(){
    ios::sync_with_stdio(0),cin.tie(0);
    t[1]=1;for(int i=2;i<=30;i++) t[i]=4*t[i-1]+1;
    int T;cin>>T;while(T--){
        cin>>l>>r>>k;
        cout<<solve(r)-solve(l-1)<<endl;
    }
    return 0;
}