【数位动规练习】准考证

2014年12月13日1,6820

escription

蒟蒻hzwer NOIP2014惨跪,他依稀记得他的准考证号是37,现在hzwer又将要面临一场比赛,他希望准考证号不出现37(连续),同时他又十分讨厌4,所以也不希望4出现在准考证号中。。。现在他想知道在A和B之间有多少合法的准考证号

Input

包含两个整数,A B

Output

一个整数。

Sample Input

【输入样例一】
1 10
【输入样例二】
25 50

Sample Output

【输出样例一】
9
【输出样例二】
14
【数据规模和约定】
20%
的数据,满足 1 <= A <= B <= 1000000 。
100%
的数据,满足 1 <= A <= B <= 2000000000 。

题解

f(i,j)表示长度i,开头为j的合法方案

则f(i,j)= ∑ f(i-1,k) (k≠4,j≠4,k≠7 or j≠3)

套数位dp模板