题目大意

给定一个正整数$n(n<=10^9)$,求在$[1,n]$中有多少个数,记在组成上包含字串"$13$",又能被$13$整除。

解题思路

这是一道经典的数位DP,但是难点和细节是颇多的。
首先,被$13$整除,这个条件如何满足?递推时怎么去转移状态呢?
有这么个取模的性质,即$c=a\times b+d$, 则$c%%p = (a*b)%%p + d%%p$, 这是显然的。
那么我们就可以从高位向低位DP,转移时维护当前数对$13$取模的值就行了。
接着是第二个难点,包含字串"$13$",这就和某些要求在一堆物品中,必须选某几种物品的DP十分类似了。
用一个bool型变量$f_1$,如果dp到当前位,之前出现过"$13$"则为真,反之则为假。
但是还是不够,因为$13$有两位,如果上一位是"$1$"且之前无"$13$"出现,而这一位又是"$3$",我们的程序就跑不出来正确的答案了。
所以我们还要用一个bool型变量$f_2$,来确定当前位的上一位是不是"$1$"。
处理完最重要的两个条件后,长吁一口气,然而问题还有一个条件,即你统计的数不能超过$n$。
这怎么办呢?
联想到两数比大小的方法,假设两数位数相同,不同可以在高位补$0$,我们是从高位到低位一次比较,当第一次出现两个位置数字不同时,就比出了大小。
那即然这样,只要某数之前有一位比n的对应位要小,那么这一位后的数字就可以随便取了。
用一个bool型变量$f$来表示之前当前这一为是否可以随意取值,即之前有没有一位小于$n$的对应位。
这样问题就完美解决了,用记忆化搜索的形式搞定此题。
但是记忆化搜索真的好写么?之前有两个bool型变量$f_1$,$f_2$,其实可以用一个type值表示,$type=0$表示之前从未出现$13$并且上一位也不是$1$;$type=1$表示之前从未出现$13$并且上一位是$1$;$type=2$表示之前出现过字串"$13$"。
dp[i][j][k]表示确定前$i$位,$type$值为$j$,前$i$为$mod 13=k$时的方案数。
但是仅仅这样会出错的,因为你没有考虑到这些方案都要小于$n$,所以我们只有当$f$为真时才能记录dp[i][j][k]的值并依次记忆化。
这是道好题。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int a[20], _len;
int dp[20][10][20];

void Make(int n) {
    memset(dp, -1, sizeof(dp));
    _len = 0;
    while(n) {
        a[++_len] = n % 10;
        n /= 10;
    }
}

int DFS(int len, int tp, int mod, bool f) {
    int sum = 0;
    if(len == 0) return ((tp == 2)&&(mod == 0));
    if(!f && dp[len][tp][mod]>=0) return dp[len][tp][mod];
    int bd = (f ? a[len] : 9);
    for(int i=0; i<=bd; i++) {
        int _mod = (mod * 10 + i) % 13;
        int _tp = 0;
        if(tp != 2 && i == 1) _tp = 1;
        if(tp == 1 && i == 3) _tp = 2;
        if(tp == 2) _tp = 2;
        sum += DFS(len-1, _tp, _mod, !(!f || i<bd));
    }
    if(!f) dp[len][tp][mod] = sum;
    return sum;
}

int main() {
    while(scanf("%d", &n) != EOF) {
        Make(n);
        printf("%d\n", DFS(_len, 0, 0, 1));
    }
    return 0;
}