题目描述
B数的定义：能被13整除且本身包含字符串"13"的数。
例如：130和2613是B数，但是143和2639不是B数。
你的任务是计算1到n之间有多少个数是B数。
输入
输入数据只有一个数，为n。（1<=N<=10^15）
输出
输出数据包含一行，为1到n之间B数的个数。
样例输入
13
样例输出
1
题解
数位dp
由于要求被13整除，因此要记录对13的模数。
由于要包含字符串"13"，因此要记录是否出现过字符串"13"，同时还要记录首位是什么以便转移。
于是设 $f[i][j][k][0/1]$ 表示 $i$ 位数，对13取模的结果为 $j$ ，首位为 $k$ ，是否包含字符串"13"的数的个数。
直接预处理出 $f$ 数组以及 $10^k$ ，然后数位dp求解即可。
首先算出不满总位数的答案，然后考虑满位数的，那么如果dp的当前位小于原数的当前位则直接计算答案，否则留到下一步处理。这里最好把所求区间转化为 $[1,n+1)$ 的半开半闭区间来求。
细节还算比较少的啦
#include <cstdio>
typedef long long ll;
ll b[17] , f[17][13][10][2];
int main()
{
int i , j , k , l , m , di = 1 , flag = 0;
ll n , now = 0 , ans = 0;
b[0] = f[0][0][0][0] = 1;
for(i = 1 ; i <= 16 ; i ++ )
{
b[i] = b[i - 1] * 10;
for(j = 0 ; j < 13 ; j ++ )
for(k = 0 ; k < 10 ; k ++ )
for(l = 0 ; l < 10 ; l ++ )
for(m = 0 ; m < 2 ; m ++ )
f[i][(j + k * b[i - 1]) % 13][k][m || (k == 1 && l == 3)] += f[i - 1][j][l][m];
}
scanf("%lld" , &n) , n ++ ;
for(i = 1 ; b[i] <= n ; i ++ )
for(j = 1 ; j < 10 ; j ++ )
ans += f[i][0][j][1];
for( ; i ; i -- )
{
for(j = di ; j < n / b[i - 1] % 10 ; j ++ )
ans += f[i][(13 - now * b[i] % 13) % 13][j][1] + (flag || (n / b[i] % 10 == 1 && j == 3)) * f[i][(13 - now * b[i] % 13) % 13][j][0];
now = (now * 10 + n / b[i - 1] % 10) % 13 , di = 0;
if(n / b[i] % 10 == 1 && n / b[i - 1] % 10 == 3) flag = 1;
}
printf("%lld
" , ans);
return 0;
}