题目描述

由于科协里最近真的很流行数字游戏。

某人又命名了一种取模数，这种数字必须满足各位数字之和$ mod N $为 0。

现在大家又要玩游戏了，指定一个整数闭区间 [a.b]，问这个区间内有多少个取模数。

数据范围

$1≤a,b≤2^{31}−1,$
$1≤N<100$

样例

输入
1 19 9

输出
2

数位DP

在几道数位Dp题目练习过后，这类题目重点在于找到左边那一类如何直接计算
对于这一题来说，假设我们当前枚举到的第i位，且第i位上的数字是x，那么对于答案中的第i位数字j来说，可以填两类数：

• 1.0~x-1
  我们用last表示到当前为止，前面数位上的数字之和，对此，当前第i位数字为j，前面数字之和为last，那么
  后i位(包括j这一位)数字之和sum与last的关系就是(last+sum)%N == 0,那么sum%N的结果等价于(-last)%N,
  所以res += f[i+1][j][(-last%N)]; (后面会提到f数组的处理)
• 2.x
  如果j填x，那么不用枚举了，last += x，再枚举下一位即可

f数组的处理

f[i][j][k] 表示一共有i位，且最高位数字是j，且所有位数字和模N结果为k的数的个数

状态转移： 因为第i位已经是j，且所有数字之和模N为k，所以我们考虑第i-1位，假设第i-1位数字是x，由于j已经知道，
那么剩下的i-1位数字之和模N的结果就是(k-j)%N，那么状态转移方程就是：

$ f[i][j][k] = \sum_{k=0}^{N-1}\sum_{x=0}^{9} f[i-1][x][mod(k-j,N)]$

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 12, M = 102;

int f[N][10][M];  //f[i][j][k] 表示一共有i位，且最高位数字是j，且所有位数字和模p位k的数字个数
int p;

int mod(int u,int v){
    return (u%v+v)%v;  //c++的%会得到负数，需要做一个偏移
}

void init(){
    memset(f,0,sizeof f);   //多组测试数据，f数组要清空
    for(int i = 0; i<=9; i++) f[1][i][i%p]++;

    for(int i = 2; i<N; i++)
        for(int j = 0; j<=9; j++)
            for(int k = 0; k<p; k++)
                for(int x = 0; x<=9; x++)
                    f[i][j][k] += f[i-1][x][mod(k-j,p)];
}

int dp(int n){
    if(!n) return 1;
    int res = 0,last = 0;

    vector<int> a;
    while(n) a.push_back(n%10),n/=10;

    int len = a.size()-1;
    for(int i = len; i>=0; --i){
        int x =a[i];    
        for(int j = 0; j<x; j++)  //第i位放0~x-1
            res += f[i+1][j][mod(-last,p)]; //0~i位，所以一共有i+1位

        last += x;
        if(!i && last % p == 0) res ++; 
    }
    return res;
}
int main()
{

    int l,r;
    while(cin>>l>>r>>p){
        init();
        cout<<dp(r)-dp(l-1)<<endl;
    }

    return 0;
}