处女座与小姐姐(三)

描述

经过了选号和漫长的等待,处女座终于拿到了给小姐姐定制的手环,小姐姐看到以后直呼666!
处女座其实也挺喜欢6这个数字的,实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样,想起了小姐姐。
现在你要给处女座展示一系列数字,你想知道他的内心会激动多少次。对于同一个数字,他最多只会激动一次,即如果这个数是66666,他还是只会激动一次。

输入

一行包括两个数字l,r,表示你给处女座展示的数字范围为[l,r]。

输出

一行一个整数,表示处女座内心激动的次数。

样例

  • Input
    10 20
  • Output
    1

题解

  • 数位dp,dp[len]表示长度为len的数里面不包含6的数的个数

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
#define LL long long
#define INIT(a,b) memset(a,b,sizeof(a))
using namespace std;
LL dp[20],num[20];
LL dfs(LL len,bool limit){
if(!len)return 1;
if(!limit && dp[len])
return dp[len];
LL ans=0;
LL up=limit?num[len]:9;
for(LL i=0;i<=up;i++){
if(i==6)continue;
ans+=dfs(len-1,limit && (i==up));
}
return limit?ans:dp[len]=ans;
}
LL solve(LL n){
if(n<0)return 0;
LL k=0;
while(n>0){
num[++k]=n%10;
n/=10;
}
return dfs(k,true);
}
int main(){
LL n,m;
scanf("%lld %lld",&n,&m);
printf("%lld\n",m-n+1-(solve(m)-solve(n-1)));
return 0;
}
Donate comment here