例题

A.B数计数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 13;

int n;
int s[N] ,c[N];
int f[N][N][3]; // 第三维上的 0 / 1 / 2 分别表示 什么也没找到 / 这一位是1 / 13都找到了

int check(int x,int y)
{
    if (x == 0) // 如果前面一位不是 1 也不是 3
    {
        if (y == 1) return 1; // 如果这一位是 1 ,那就返回 1
        return 0; // 否则啥也不是
    }
    else if (x == 1) // 如果前一位是 1
    {
        if (y == 1) return 1; // 如果这一位还是 1 ,也没关系,可以为后面找 3 做准备
        if (y == 3) return 2; // 如果前一位是 1 ,这一位是 3 ,那就凑成了
        return 0; // 否则啥也不是
    }
    else if (x == 2) return 2; // 如果已经有 13 了,那就随意
}

int dfs(int pos,int res,int op,int limit)
{
    if (!limit && f[pos][res][op] >= 0) return f[pos][res][op];

    if (!pos) return op == 2 && res == 0; // 判断两个条件是否同时成立

    int s = 0,ans = 0;

    if (!limit) s = 9; // 如果没有限制,则取0 ~ 9
    else s = c[pos]; // 如果有限制,只能去 n 的 pos 位上的数

    for (int i = 0; i <= s; i ++)
        ans += dfs(pos - 1 , (res * 10 + i) % N , check(op , i) , limit && i == s);

    if (!limit) f[pos][res][op] = ans;

    return ans;
}

int solve(int x)
{
    int cnt = 0;
    while (x)
    {
        c[++ cnt] = x % 10; // 找到 n 的每一位上的数字
        x /= 10;
    }

    return dfs(cnt , 0 , 0 , 1); // 从高位往地位找
}

int main()
{
    while (scanf ("%d",&n) != EOF)
    {
        memset(f , -1 , sizeof f);
        printf ("%d\n",solve(n));
    }
}