题解：CF2086E Zebra-like Numbers

dayz_break404 · 2025-04-12 14:52:24 · 题解

一道不那么板的数位 DP，感觉思路很清奇。

显然斑马数不超过 30 个，记斑马数为 num_i，那么答案是一个多项式的形式，考虑将其转化为进制的形式。

考虑这个进制，由于斑马值是最小的系数和，从高位到低位贪心一定是最优的。并且由于有 num_i=num_{i-1}\times 4+1，所以每一位上的数值都不大于 4，并且如果有一位为 4，则它的更低位一定是 0。

那么 DP 状态为 dp_{i,j,lim1,lim2}，表示当前 pos 位，数位和为 j，是否达到数值限制，是否出现了 4，转移即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
bool mbs;
ll t,l,r,k,num[32],val[32],dp[32][100][2][2];
ll dfs(int pos,int sum,int lim1,int lim2){
    if(!pos) return sum==k;
    if(dp[pos][sum][lim1][lim2]!=-1) return dp[pos][sum][lim1][lim2];
    int up=4;ll res=0;
    if(lim2) up=0;
    else if(lim1) up=val[pos];
    for(int i=0;i<=up;i++) res+=dfs(pos-1,sum+i,lim1&&i==val[pos],lim2||i==4);
    return dp[pos][sum][lim1][lim2]=res;
}
inline ll get_val(ll x){
    for(int i=30;i>=1;i--) val[i]=(x/num[i]),x-=(x/num[i])*num[i];
    memset(dp,-1,sizeof(dp));
    return dfs(30,0,1,0);
}
inline void solve(){
    l=read(),r=read(),k=read();
    printf("%lld\n",get_val(r)-get_val(l-1));
}
bool mbt;
int main(){
//  cout<<(&mbs-&mbt)/1024.0/1024.0<<endl;
    num[1]=1;
    for(int i=2;i<=30;i++) num[i]=num[i-1]*4+1;
    t=read();
    while(t--) solve();
    return 0;
}