Description

给出a,b，求出[a,b]中各位数字之和能整除原数的数的个数。

Sample Input

10 19

Sample Output

3

HINT

【约束条件】1 ≤ a ≤ b ≤ 10^18

---

 

题解Here!

本蒟蒻表示不会数位$DP$，药丸。。。

首先把询问拆成$sum(b)-sum(a-1)$应该都会。

然后本蒟蒻就不会了。。。

本题记录前面的数字的和，同时还要知道最后产生的数字是否整除和。

记录各位数字的和比较容易，共$9\times 18$个状态。

关键是如何知道已经产生 的数位构成的数字是否整除最后的总和，比较麻烦。

考虑求模，整除的模数为$0$，可以记录已经产生的数字的模数，但是又不知道最后的数字总和是多少，这个模数怎么记录？

可以这样定义：

$dp[i][sum][m][mod]$表示到第i位，前面数字总和为$sum$ ，$\mod mod$的值为$m$，然后枚举$mod$即可计算。

这样可以解决问题，但是计算内存发现：$dp[20][200][200][200]$需要1G的内存，只好想办法压 缩空间，因为$mod$是要在程序中枚举的，所以不必记录这一维状态，这样空间就足够了。

$dp[i][sum][m][0/1]$表示到第$i$位，前面数字总和为$sum$，$\mod mod$的值为$m$，0表示没卡上界，1表示卡了上界,然后枚举$mod$即可计算

写数位dp的时候，我习惯考虑从当前状态进行拓展，也就是所谓的刷表大法。

附代码：

#include
      
       #include
       
        #include
        
         #include
         
          #define MAXN 210#define MAXM 30using namespace std;int top,bit[MAXM];long long a,b,dp[MAXM][MAXN][MAXN][2];inline long long read(){    long long date=0,w=1;char c=0;    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}    return date*w;}long long solve(long long x){    long long ans=0;    top=0;    while(x){bit[++top]=x%10;x/=10;}    reverse(bit+1,bit+top+1);    for(int sum=1;sum<=top*9;sum++){        memset(dp,0,sizeof(dp));        dp[0][0][0][1]=1;        for(int i=0;i
          
           sum)break;                dp[i+1][j+l][(k*10+l)%sum][c&(l==bit[i+1])]+=dp[i][j][k][c];            }        }        ans+=dp[top][sum][0][0]+dp[top][sum][0][1];    }    return ans;}int main(){    a=read();b=read();    printf("%lld\n",solve(b)-solve(a-1));    return 0;}