HDU 3555 Bomb(1-n含有“49”的数字个数)

题目链接：
HDU 3555 Bomb
题意：
求1到$n$中含有“49”序列的数字的个数。491，149都是含有“49”序列但是“419”不是的。
数据范围：$n\leq 2^{63} -1$
分析：
数位dp。差不多也是模版题了。
从高位到低位$dfs$记录前一位数字，并且记录当前是否已出现“49”序列，最后判断下状态，记忆化搜索。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;