题目链接：[kuangbin带你飞]专题十五 数位DP G - B-number

题意

求1～n的范围里含有13且能被13整除的数字的个数。

思路

首先，了解这样一个式子：a％m == ((b%m)*c+d)%m;

式子的正确是显然的。就不证明了。

那么推断数能否够被13整除就能够分解为一位一位进行处理。

当然。我们也仅仅须要储存取余后的值。

dfs(len, num, mod, flag)

mod记录数字对13取余后的值

len表示当前位数

num＝＝0 不含13且上一位不为1

pre＝＝1 不含13且上一位为1

pre＝＝2 含13

flag表示能否够随意取值(推断范围)。

如此，记忆化搜索就可以得解。

代码

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cstdlib>

#include <vector>

using namespace std;
#define LL long long

#define MOD 13

LL dp[20][3][13];

int dis[20];
LL dfs(int len, int type, int mod, bool flag)

{

    if(len < 0)

        return type == 2 && mod == 0;

    if(!flag && dp[len][type][mod]!=-1)

        return dp[len][type][mod];

    int end = flag?
dis[len]:9;

    int ans = 0;

    for(int i=0; i<=end; i++)

    {

        if(type == 2 || (type == 1 && i == 3))

            ans += dfs(len-1, 2, (mod*10+i)%MOD, flag&&i==end);

        else

            ans += dfs(len-1, i==1?1:0, (mod*10+i)%MOD, flag&&i==end);

    }

    if(!flag)

        dp[len][type][mod] = ans;

    return ans;

}
LL solve(LL n)

{

    int len = 0;

    while(n)

    {

        dis[len++] = n%10;

        n /= 10;

    }

    return dfs(len-1, 0, 0, 1);

}
int main()

{

    int n;

    memset(dp, -1, sizeof(dp));