题目描述

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

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

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

样例

输入样例

1 19 9

输出样例

2

算法1

(数位dp) $ O( log_{10} b * N) $

主要思路：
- 预处理出dp[i][j] 表示所有位数为i，模N余j的数的总数。可发现补上前缀0后mod包含 N余数不变，所以可以将位数广义认为是包含所有含有前缀0的数。
- 转移方程（状态划分）：枚举第一位，可得$dp[i][j] = \sum_{k=0}^9\ dp[i - 1][j - k]$
- 那么，如何计算出区间$[a , b]$中满足数的和呢？
- 想到可以使用前缀和，拆为$[1\ ,\ b]$ - $[1\ , a\ -\ 1]$，所以，我们只需算出$[1\ ,\ n]$中所有满足条件的数即可
- 计算$[1\ ,\ n]$，可以将n拆位，后枚举每一位，对答案进行拆分，分为比i位数小（可直接算出），以及等于第i位数（继续枚举），注意，最后，如果枚举到了第一位，则需特判是否满足。

时间复杂度

• 预处理$ O( log_{10} b * N ) $
• 计算$ O( log_{10} b ) $

C++ 代码

# include <iostream>
# include <cstdio>
# include <cstring>

using namespace std ;

int N ;
int a , b ;
int dp[25][105] ;
int num[25] ;

void init()
{
    memset( dp , 0 , sizeof( dp ) ) ;
    dp[0][0] = 1 ;
    for ( int i = 1 ; i <= 20 ; i++ )
    {
        for ( int j = 0 ; j < N ; j++ )
        {
            for ( int k = 0 ; k <= 9 ; k++ )
            {
                dp[i][j] += dp[i - 1][( ( j - k ) % N + N ) % N] ;
            }
        }
    }
    return ;
}

int count( int w )
{
    if ( ! w ) return 1 ;
    memset( num , 0 , sizeof( num ) ) ;
    while ( w )
    {
        num[++ num[0]] = w % 10 ;
        w /= 10 ;
    }
    int res = 0 , last = 0 ;
    for ( int i = num[0] ; i >= 1 ; i-- )
    {
        int x = num[i] ;
        for ( int j = 0 ; j < x ; j++ )
        {
            res += dp[i - 1][( ( last - j ) % N + N ) % N] ;
        }
        last = ( ( last - x ) % N + N ) % N ;
        if ( i == 1 && last == 0 ) res ++ ;
    }
    return res ;
}

int main()
{
    while ( scanf("%d%d%d" , &a , &b , &N) == 3 )
    {
        init() ;
        printf("%d\n" , count( b ) - count( a - 1 ) ) ;
    }
    return 0 ;
}