手机号码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int L, R;
int d[15], dlen;             // d[dlen]~d[1]
int dp[15][2][2][2][10][10]; // dp[pos][f4][f8][f3][pre][prepre]
// 返回方案数量
// pos: 填到了哪一位
// limit: 之前有没有顶到上限
// f4/8: 之前有没有出现过 4/8
// f3: 之前是否完成了三连
// pre: 前一位是谁
// prepre: 前两位是谁
int dfs(int pos, bool limit, bool f4, bool f8, bool f3, int pre, int prepre)
{
    // 边界
    if (pos == 0)
    {
        if (f3)
            return 1;
        else
            return 0;
    }
    // 记忆化
    if (!limit && dp[pos][f4][f8][f3][pre][prepre] != -1)
        return dp[pos][f4][f8][f3][pre][prepre];
    // 当前这一位怎么选
    int up = limit ? d[pos] : 9;
    int down = (pos == 11) ? 1 : 0;
    int sum = 0; // 记录所有情况的方案之和
    for (int now = down; now <= up; now++)
    {
        // 尝试在 pos 这一位填 now
        if (f4 && now == 8)
            continue;
        if (f8 && now == 4)
            continue;
        sum += dfs(pos - 1,
                   limit && now == d[pos],
                   f4 || now == 4,
                   f8 || now == 8,
                   f3 || (now == pre && pre == prepre),
                   now,
                   pre);
    }
    if (!limit)
        dp[pos][f4][f8][f3][pre][prepre] = sum;
    return sum;
}

// 计算 0~x 不含有不吉利成分的数的数量
int cal(int x)
{
    if (x < 10000000000)
        return 0;
    dlen = 0;
    for (int i = x; i != 0; i /= 10)
        d[++dlen] = i % 10;
    return dfs(dlen, true, false, false, false, -1, -1);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> L >> R;
    memset(dp, -1, sizeof(dp));
    cout << cal(R) - cal(L - 1) << "\n";
    return 0;
}