[BZOJ 4521] [CQOI 2016] 핸드폰 번호.

산동성 에서 선택 한 에너지 저장 표 와 비슷 합 니 다. 모두 상한 선 을 가 진 디지털 dp 입 니 다. 먼저 차이 점 을 낸 다음 에 두 번 물 어보 면 됩 니 다.여 기 는 10 ^ 10 을 주의해 야 합 니 다. 1 을 빼 면 10 자리 가 되 기 때문에 여 기 는 1 을 추가 합 니 다.f [i] [j] [a] [b] [c] [d] [e] 로 표시...i 위 까지 올 라 가면 1 위 는 j (0 위 는 10 으로 표시) 이 고 a 는 마지막 두 사람 이 같 는 지, b 는 연속 세 개의 숫자 가 같 는 지, c 는 4 가 있 는 지, d 는 8 이 있 는 지, e 는 상한 보다 작은 지 를 나타 낸다.

#include
#include
#include
#include 
#include
#include
#include
#include
#include
#define ll long long
#define inf 1000000000
#define mod 1000000007
#define N 100000
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
ll f[20][15][2][2][2][2][2],l,r;
int p[20];
ll calc(ll q)
{
    ll num,t,i,j,k,a,b,c,d,e,x,y,z,m,n,res;
    memset(f,0,sizeof(f));
    num = 0; t = q; while (t) {p[++num]=t%10; t/=10;}
    fo(i,1,num/2) swap(p[i],p[num-i+1]);
    f[0][10][0][0][0][0][1] = 1; //    
    fo(i,0,num-1)
    fo(j,0,10)
    fo(a,0,1)
    fo(b,0,1)
    fo(c,0,1)
    fo(d,0,1)
    fo(e,0,1)
        if (f[i][j][a][b][c][d][e])
        fo(k,0,9)
            {
                if ((k > p[i+1]) && e) continue; //    
                x = (k == j); //         
                y = b?b:(a+x)==2; //          
                z = c?c:(k==4); m = d?d:(k==8);
                if (z + m == 2) continue; //      4 8
                n = ((k == p[i+1] && e))?1:0;
                f[i+1][k][x][y][z][m][n] += f[i][j][a][b][c][d][e];
            }
    res = 0; 
    fo(j,0,9)
    fo(a,0,1)
    fo(c,0,1)
    for (d = 0;(d<=1)&&(d+c<2); d++)
        res += f[num][j][a][1][c][d][0];
    return res;
}

int main()
{
    scanf("%lld%lld",&l,&r);
    printf("%lld
",calc(r+1)-calc(l)); //  l=10^10  l-1  11   
    return 0;
}