学步园

数位DP，DP[I][J][K][L]表示到第i位，末尾为j，mod13为k，l的01表示是否出现过13了，然后就是数位DP的状态转移即可

代码：

#include <cstdio>
#include <cstring>

char num[12];

int n, dp[12][10][14][2];

int main() {
	while (~scanf("%s", num)) {
		n = strlen(num);
		memset(dp, 0, sizeof(dp));
		int pre = 0, mod = 0, flag = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < 10; j++) {
				for (int k = 0; k < 10; k++) {
					for (int x = 0; x < 13; x++) {
						dp[i + 1][j][(x * 10 + j) % 13][1] += dp[i][k][x][1];
						if (j == 3 && k == 1) dp[i + 1][j][(x * 10 + j) % 13][1] += dp[i][k][x][0];
						else dp[i + 1][j][(x * 10 + j) % 13][0] += dp[i][k][x][0];
					}
				}
			}
			for (int j = 0; j < num[i] - '0'; j++) {
				if (flag || (j == 3 && pre == 1)) dp[i + 1][j][(mod * 10 + j) % 13][1]++;
				else dp[i + 1][j][(mod * 10 + j) % 13][0]++;
			}
			if (pre == 1 && num[i] - '0' == 3) flag = 1;
			pre = num[i] - '0';
			mod = (mod * 10 + num[i] - '0') % 13;
		}
		int ans = (flag && mod == 0);
		for (int i = 0; i < 10; i++)
				ans += dp[n][i][0][1];
		printf("%d\n", ans);
	}
	return 0;
}