Problem Description
题库链接
666是一个网络用语，用来形容某人或某物很厉害很牛。而在西方，666指魔鬼，撒旦和灵魂，是不吉利的象征。所以邓志聪并不喜欢任何与6有关的数字。什么数字与6有关呢：
满足以下3个条件中的一个，我们就认为这个整数与6有关。
1.这个整数在10进制下某一位是6.
2.这个整数在10进制下的数位和是6的倍数.
3.这个数是6的整数倍。
那么问题来了：邓志聪想知道在一定区间内与6无关的数的和。
Input
本题为多组输入，请处理到文件结尾，每行包含两个正整数L，R。（1<=L<=R<=1e18）。
Output
输出一个正整数，该正整数为区间【L，R】中与6无关的数字的和。由于这个数字可能很大，请对1e9+7取模。
Sample Input
1 9
1 20
Sample Output
39
143
Analysis of ideas
数位dp进阶的难度吧,也不是很难,和kuangbin里面的一题类似(777),那题更变态,题目链接
第一次发现可以定义结构体类型的数位dp
cnt 满足题意的数 的 个数
sum 满足题意的数 的 和
Accepted code
#include <bits/stdc++.h>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
#define ll long long
const int maxn = 100100;
const int inf = 0x3f3f3f3f;
const int M = 1e9+7;
int a[20];
struct node
{
ll cnt,sum;
}dp[20][10][10];//sw,sum,he
ll p[20];
void init()
{
p[0] = 1;
for(int i = 1; i <= 18; i++)
{
p[i] = (p[i-1]*10)%M;
}
for(int i = 0; i < 20; i++)
{
for(int j = 0; j < 10; j++)
{
for(int k = 0; k < 10; k++)
{
dp[i][j][k].cnt = -1;
}
}
}
}
node dfs(int sw,ll sum,ll h,bool limit) //个数,数,数位和,限制条件
{
if(sw == -1)
{
return node{sum!=0&&h!=0,0}; //个数,和
}
if(!limit && dp[sw][sum][h].cnt != -1) return dp[sw][sum][h];
int up = limit?a[sw]:9;
node ans,tmp;
ans.cnt = 0,ans.sum = 0;
for(int i = 0; i <= up; i++)
{
if(i == 6) continue;
tmp = dfs(sw-1,(sum*10+i)%6,(h+i)%6,limit&&i==a[sw]); //sw-1,(sum*10+i)%6,(h+i)%6,limit
//当前满足条件的数的个数 += 之前(前一位)满足条件的数的个数
ans.cnt = (ans.cnt+tmp.cnt)%M;
//当前的数字和 += 之前(前一位)的数字和 + (当前符合条件的数的个数 * i * 10的当前位数次方);
ans.sum = (ans.sum + ( tmp.sum + ((p[sw]*i) %M)*(tmp.cnt %M)) %M) %M;
}
if(!limit) dp[sw][sum][h] = ans; //sw,sum和h就一定可以确定一个数吗???
return ans;
}
ll solve(ll n)
{
int sw = 0;
while(n)
{
a[sw++] = n%10;
n /= 10;
}
return dfs(sw-1,0,0,true).sum;
}
int main()
{
ll l,r;
init();
while(~scanf("%lld%lld",&l,&r))
{
ll ans = solve(r)+M-solve(l-1);
cout<<ans%M<<endl;
}
return 0;
}