写在前面

这道题真有意思

$Idea$

题意

求$[L,R]$内不被$9$整除且每一位都不是$9$的数的个数。

思路：

数位$DP$，由$(x+y)\%m=(x\%m+y\%m)%m$。直接维护前$l$位对9取模的值，向后$dfs$到最后一位发现模数不是0就计数。

$Code$

int sum[maxn];
int dp[maxn][maxn];
inline int dfs(int l,int p,bool flag){
    if(!flag&&~dp[l][p]) return dp[l][p];
    if(l==0){
        if(p%9==0) return dp[l][p]=0;
        return dp[l][p]=1;
    }
    int pos=flag?sum[l]:9;
    int res=0;
    for(int i=0;i<=pos;i++){
        if(i==9) continue;
        res+=dfs(l-1,(p*10+i)%9,flag&&(i==pos));
    }
    if(!flag) dp[l][p]=res;
    return res;
}
inline int find(int x){
    int tot=0;
    while(x){
        sum[++tot]=x%10;
        x/=10;
    }
    return dfs(tot,0,1);
}
signed main(){
    int T=read(),_=0;
    mem(dp,-1);
    while(T--){
        int L=read(),R=read();
        printf("Case #%d: %lld\n",++_,find(R)-find(L-1));
    }
    return 0;
} 

$P.S:$不要私信问我某某地方为什么这样写，本人一向无法解释。$QAQ$

因为
$$The \quad End$$

$$\text{原谅我藏在心里燎燎的狂傲，去战，面对天地荡浩。-《剑心》张杰}$$