学步园

题意：求1----n(n<= 1e9)内含13且能被13整除的数的个数。

算法：数位dp， 可以用递归dfs或非递归写， 前者效率略低但思路很清晰，代码也很容易写，后者效率略高，但编码复杂度高。

思路：根据自己的需要在dfs传入的参数进行修改或添加，dp记忆化一下没有首位限制的并且自己需要的情况。

递归：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[34];
int dp[34][14][3];
/*  0 含13
 *  1 不含13，但以3结尾
 *  2 不含13
 */
int dfs(int len, int pre, int mod, bool has, bool lim) {
	if(!len) return has && !mod;
	if(!lim) {
		if(!has && pre!=1 && ~dp[len][mod][0]) return dp[len][mod][0];
		if(!has && pre==1 && ~dp[len][mod][1]) return dp[len][mod][1];
		if(has && ~dp[len][mod][2]) return dp[len][mod][2];
	}
	int ret = 0;
	int m = lim ? a[len] : 9;
	for(int i = 0; i <= m; i++)
		ret += dfs(len-1, i, (mod*10+i)%13, has|(pre==1&&i==3), lim&&i==m);
	if(!lim) {
		if(!has && pre!=1) dp[len][mod][0] = ret;
		if(!has && pre==1) dp[len][mod][1] = ret;
		if(has) dp[len][mod][2] =ret;
	}
	return ret;
}
int gao(int n) {
	int len = 0;
	while(n) {
		a[++len] = n%10;
		n/=10;
	}
	return dfs(len, 0, 0, 0, 1);
}
int main() {
	int i, j, n;
	memset(dp, -1, sizeof(dp));
	while( ~scanf("%d", &n))
		printf("%d\n", gao(n));
	return 0;
}

非递归：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[12][14][3], f[12];
// 0   不含13
// 1   3开头含13
// 2   含13
void init() {
    int i, j, k;
    f[0] = 1;
    for(i = 1; i <= 10; i++) f[i] = f[i-1] * 10 % 13;
    dp[0][0][0] = 1;
    for(i = 0; i < 10; i++)
        for(j = 0; j < 13; j++) {
            for(k = 0; k < 10; k++)
                dp[i+1][(j+f[i]*k)%13][0] += dp[i][j][0];
            dp[i+1][(j+f[i])%13][0] -= dp[i][j][1];
            dp[i+1][(j+f[i]*3)%13][1] += dp[i][j][0];
            dp[i+1][(j+f[i])%13][2] += dp[i][j][1];
            for(k = 0; k < 10; k++)
                dp[i+1][(j+f[i]*k)%13][2] += dp[i][j][2];
        }
}
int gao(int n) {
    int a[11], len = 0;
    while(n) { a[len++] = n%10; n /= 10; }
    a[len] = 0;
    int ans = 0, tp = 0;
    bool flag = 0;
    int i, j;
    for(i = len-1; i >= 0; i--) {
        for(j = 0; j < a[i]; j++) {
            ans += dp[i][(13-(tp+j*f[i])%13)%13][2];
            if(flag) ans += dp[i][(13-(tp+j*f[i])%13)%13][0];
        }


        if(!flag) {

            if(a[i+1] == 1 && a[i] > 3) ans += dp[i+1][(13-tp)%13][1];
            if(a[i] > 1) ans += dp[i][(13-(tp+f[i])%13)%13][1];
        }
        if(a[i+1] == 1 && a[i] == 3) flag = 1;
        tp = (tp + a[i] * f[i]) % 13;
    }
    if(flag && !tp) ans++;
    return ans;
}
int main() {
    int i, j, n;
    init();
    while( ~scanf("%d", &n)) printf("%d\n", gao(n));
    return 0;
}