算法提高课汇总

算法思路

数位$DP$中的$DP$一般指的是针对数字性质的预处理过程, 本题数字性质: 数字所有数位之和模$N$为$0$.

$DP$预处理

状态表示

若使用状态$f(i, j)$ — $i$位数最高位为$j$且数位之和模$N$为$0$的个数. 枚举第$i - 1$位的数字$x$,
假设$0\sim i - 1$位数字之和为$s$, 则$(j + s) \% N = 0$, $s = (0 - j) \% N$, 即我们需要的状态子状态
为$i - 1$位最高位为$x$且数字之和模$N$为$(-j) \% N$ — 需要用额外一个维度表示模$N$的余数.

• 集合: $f(i, j, k)$: $i$位数最高位为$j$且数位之和模$N$为$k$的所有数字.

• 属性: Count

状态计算

$f(i, j, k) = \sum f(i - 1, x, s)$, 其中$(j + s) \% N = k$ --> $s = (k - j)\%s$, $0\le x\le 9$.

具体实现

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

using namespace std;

const int N = 11, M = 110; 

int P; //模数
int f[N][10][M]; //f(i, j, k)

//使x % y的结果在[0, y)
int mod(int x, int y)
{ 
    return (x % y + y) % y;
}

void init()
{
    memset(f, 0, sizeof f);

    //边界情况 个位数
    for ( int i = 0; i <= 9; i ++ ) f[1][i][mod(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;

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

    int res = 0;
    int last = 0; //已经确定数位之和
    for ( int i = nums.size() - 1; i >= 0; i -- )
    {
        int x = nums[i];
        for ( int j = 0; j < x; j ++ ) //左子树
            res += f[i + 1][j][mod(-last, P)]; //( last + s ) % P = 0

        last += x;

        if ( !i && last % P == 0 )   res ++ ; //n自身也满足条件
    }
    return res;
}

int main()
{
    int l, r;

    while ( cin >> l >> r >> P )
    {
        init();

        cout << dp(r) - dp(l - 1) << endl;
    }

    return 0;
}