题解：P16641 [GKS 2018 #B] No Nine

wjsjwl · 2026-06-06 12:52:15 · 题解

题目传送门

题目介绍
求范围 [l,r] 内有多少个数字每一位都不含九而且不被九整除。

解法 [建议先做这道题，题解有非常详细的数位DP模板](P2602 [ZJOI2010] 数字计数)

一位一位考虑该位填什么数，这里从高位向低位枚举。填数限制的话注意当且仅当数位数字和被 9 整除，这个数字被 9 整除。

具体实现看代码，我用的是记忆化，代码更好打：

#include <bits/stdc++.h>
#define int long long//记得开 long long
using namespace std;
const int N=505;
int f[N][N],num[N],cnt,T;
void fun(int x){
    cnt=0; while(x){num[++cnt]=x%10;  x/=10;}        memset(f,-1,sizeof f);
}
int dfs(int pos,int sum,int lmt){//分别表示当前枚举到第几位,数字和,上界是否需特殊处理
    if(pos==0)  return (sum%9!= 0) ? 1 : 0;//注意只需要最后判数位数字和被九整除
    if(lmt==0&&f[pos][sum]!=-1)  return f[pos][sum];//记忆化
    int up=(lmt?num[pos]:8)//上界；
  int ans=0;
    for(int i=0;i<=min(up,int(8);i++){//注意up有可能为9
        ans+=dfs(pos-1,sum+i,(i==up)&&lmt);//pos位前所有位都取上界且此位到上界时lmt才为1
    }
    if(!lmt)  f[pos][sum]=ans;//也可以像另一篇题解一样再开一维
    return ans;
}
signed main()
{
    int a,b;  
    cin>>T;
    for(int i=1;i<=T;i++){
        cin>>a>>b;
        fun(a-1);  int a1=dfs(cnt,0,1);
        fun(b);  int b1=dfs(cnt,0,1);
        cout<<"Case #"<<i<<": "<<b1-a1<<endl;  //前缀和思想
    }
    return 0;
}