[日常训练]准考证号

Description

小$Z$在一次大考中失利，留下了严重的心理阴影。他记得当时他的准考证号是$37$，所以他不希望准考证是存在连续的$2$位是$37$，此外，由于$4$是一个不吉利的数字，所以小$Z$同样不希望出现$4$。现在已知小Z的准考证号在$[A,B]$之间，请计算有多少个符合要求的准考证号码。

Input

一行，$2$个整数$A,B$。

Output

一行，一个整数，表示符合要求的准考证号的数量。

Sample Input

25 50

Sample Output

14

HINT

$A,B\;\leq\;2\;\times\;10^9$.

Solution

$a_i$记录上限每一位的值.

$f[i][j][0/1]$表示第$i$位填$j$,前$i$位是否与上限相同的方案数.

$f[i][j][0]=\begin{cases}0&j=4\\\sum_{k=0,k\not=3}^{9}f[i-1][k][0]+\sum_{k=0,k\not=3}^{a_i-1}f[i-1][k][1]&j=7\\\sum_{k=0}^{9}f[i-1][k][0]+\sum_{k=0}^{a_i-1}f[i-1][k][1]&j\not=4,j\not=7\\\end{cases}$

$f[i][a_i][1]=\begin{cases}0&a_i=4\\0&a_i=7,a_{i-1}=3\\f[i-1][a_{i-1}][1]&a_i=7,a_{i-1}\not=3\\f[i-1][a_{i-1}][1]&a_i\not=4,a_i\not=7\\\end{cases}$

类似前缀和思想求解.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 15
using namespace std;
typedef long long ll;
int f[N][N][2],a[N],b[N],n;
inline int func(int k){
    if(!k) return 1;
    int ret=0;n=0;
    while(k){
        b[++n]=k%10;k/=10;
    }
    for(int i=1,j=n;i<=n;++i,--j)
        a[i]=b[j];
    memset(f,0,sizeof(f));
    for(int i=0;i1];++i)
        if(i!=4) f[1][i][0]=1;
    f[1][a[1]][1]=1;
    for(int i=2;i<=n;++i){
        for(int j=0;j<=9;++j){
            if(j!=4&&j!=7){
                for(int k=0;k<=9;++k){
                    if(k!=4) f[i][j][0]+=f[i-1][k][0];
                }
                if(j<a[i]){
                    for(int k=0;k<=a[i-1];++k)
                        if(k!=4) f[i][j][0]+=f[i-1][k][1];
                }
                else if(j==a[i]&&a[i-1]!=4)
                    f[i][j][1]+=f[i-1][a[i-1]][1];
            }
            else if(j==7){
                for(int k=0;k<=9;++k){
                    if(k!=4&&k!=3) f[i][j][0]+=f[i-1][k][0];
                }
                if(j<a[i]){
                    for(int k=0;k<=a[i-1];++k)
                        if(k!=4&&k!=3) f[i][j][0]+=f[i-1][k][1];
                }
                else if(j==a[i]&&a[i-1]!=4&&(a[i-1]!=3||a[i]!=7))
                    f[i][j][1]+=f[i-1][a[i-1]][1];
            }
        }
    }
    for(int i=0;i<=9;++i)
        ret+=f[n][i][0]+f[n][i][1];
    return ret;
}
inline void Aireen(){
    int a,b;
    scanf("%d%d",&a,&b);
    printf("%d\n",func(b)-func(a-1));
}
int main(){
    freopen("exam.in","r",stdin);
    freopen("exam.out","w",stdout);
    Aireen();
    fclose(stdin);
    fclose(stdout);
    return 0;
}