题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3652
题目大意：
求区间 \([1, n]\) 范围内包含连续的数位“13”并且能被13整数的数的数量。
解题思路：
使用 数位DP 进行求解。
开一个状态 \(f[pos][pre][num][flag]\) ，用于表示：
- 当前所处的数位为第
pos位； - 之前所有的数位模13的余数为
pre； - 当前数位的前一位（即第
pos+1位）为num； flag用于表示当前数位的前面那些位中是否有连续的两位为‘13’（flag==true表示有过，flag==false表示还没有过）
时的方案总数。
函数 dfs(int pos, int pre, int num, int flag, bool limit) 用于求解答案，其中：
pos、pre、num、flag的含义同上；limit用于表示当前是否处于限制状态。
实现代码如下：
#include <bits/stdc++.h>
using namespace std;
int f[33][13][10][2], a[33];
void init() {
memset(f, -1, sizeof(f));
}
int dfs(int pos, int pre, int num, int flag, bool limit) {
if (pos < 0) return flag && pre==0;
if (!limit && f[pos][pre][num][flag] != -1) return f[pos][pre][num][flag];
int up = limit ? a[pos] : 9;
int tmp = 0;
for (int i = 0; i <= up; i ++) {
tmp += dfs(pos-1, (pre*10+i)%13, i, flag || num==1&&i==3, limit && i==up);
}
if (!limit) f[pos][pre][num][flag] = tmp;
return tmp;
}
int get_num(int x) {
int pos = 0;
while (x) {
a[pos++] = x % 10;
x /= 10;
}
return dfs(pos-1, 0, 0, 0, true);
}
int main() {
init();
int n;
while (cin >> n) {
cout << get_num(n) << endl;
}
return 0;
}