传送门
(1e9)的数据，让你找到
- 数字里包含13
- 且是13的倍数。
包含13子串很好找，就是普通的数位dp模板，(pre == 1 and i == 3)就行了
数字是13的倍数，本来可以记录一下当前的数字为什么，最后再判断一下就行了，但是为了记忆话搜索，就就必须修改策略
考虑每次都取模，比如123对13取模就等于100 % 13 + 20 % 13 + 3 % 13,也就是说是(((1 % 13) * 10 + 2) % 13 * 10 + 3) % 13
那么就在dp数组里加一维度，表示对13取模后的结果，然后再记忆话就行了
数位dp里面包含某些数字就直接存pre，是某些数字的倍数，就考虑加一维存放一下对这些数的余数即可。
#include <iostream>
#include <cstdio>
#include <cstring>
#define ll long long
using namespace std;
ll dp[20][10][15][2];
int a[20];
ll dfs(int pos, int pre, bool limit, int remind, bool have){
if(pos == -1) {
if(remind % 13 == 0) return have;
return 0;
}
if(!limit && dp[pos][pre][remind][have] != -1) return dp[pos][pre][remind][have];
int up = limit ? a[pos] : 9;
ll tmp = 0;
for(int i = 0; i <= up; i++) {
int has = 0;
if(pre == 1 && i == 3) has = 1;
tmp += dfs(pos - 1, i, limit && i == a[pos], (remind * 10 + i) % 13, have | has);
}
if(!limit) dp[pos][pre][remind][have] = tmp;
return tmp;
}
ll solve(ll n){
memset(dp, -1, sizeof(dp));
int pos = 0;
while(n){
a[pos++] = n % 10;
n /= 10;
}
return dfs(pos - 1, 0, 1, 0, 0);
}
int main(){
ll l, r;
while(~scanf("%lld", &r)){
printf("%lld
", solve(r));
}
return 0;
}