不要666 （数位dp

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e6;
const int MOD = 1e9 + 7;

struct status{
    ll cnt; //满足条件的数的个数
    ll sum; //满足条件的数之和
    status() {cnt = -1 ; sum = 0;}
    status(ll cnt , ll sum ) : cnt(cnt) , sum(sum) {}
}dp[20][10][10]; //第一维表示位数，第二位表示数位和mod6的值，第三维表示数值mod7的值
ll digit[20]; //用来保存每一位的数字
ll p[25]; // 存储10的i次方

status dfs(int pos, int pre , int sta ,bool limit){ //pos位数，pre数位和mod 6的值，数值mod 6的值 ，数字是否打到边界 即213的百位是否枚举到2 然后枚举十位只能枚举到1
    if(!pos) return pre != 0 && sta != 0 ? status(1 , 0) : status(0 , 0);  //如果当前数位和mod6不等于0并且数值mod6不为0 就表示这个数是合法的
    if(!limit && dp[pos][pre][sta].cnt != -1) return dp[pos][pre][sta];  
    int limitmax = limit ? digit[pos] : 9;
    status ans;
    ans.cnt = 0;
    for(int i = 0 ; i <= limitmax ; ++i){
        if(i == 6) continue;
        status next = dfs(pos - 1 ,  (pre + i) % 6 , (sta * 10 + i) % 6 , limit && i == limitmax);
        ans.cnt += next.cnt; //数的个数
        ans.cnt %= MOD;
        ans.sum += (next.sum + ((p[pos] * i ) % MOD) * next.cnt %MOD) % MOD;
        ans.sum %= MOD; 
    }
    if(!limit) dp[pos][pre][sta] = ans;
    return ans;
}

ll solve(ll x){  
    int pos = 0;
    while(x){
        digit[++pos] = x % 10;
        x /= 10;
    }
    status tt = dfs(pos , 0 , 0 ,true);
    return tt.sum;
}

int main(void){
    ll l , r;
    p[1] = 1;
    for(int i = 2 ; i <= 20 ; ++i) 
        p[i] = (p[i - 1] * 10) % MOD;
    while(~scanf("%lld%lld", &l , &r)){
        ll ans = solve(r);
        ans -= solve(l - 1);
        printf("%lld\n" , (ans % MOD + MOD) % MOD);
    }
    return 0;
}

大佬博客数位dp总结之从入门到模板

类似题目 HDU 4507

求平方和可以用完全平方公式，比如讲 $123^{2} = (100 + 23)^{2}=100^{2}+2*100*23+23^{2}$
如此来求

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e6;
const int MOD = 1e9 + 7;

struct status{
    ll cnt; //满足条件的数的个数
    ll sum; //满足条件的数之和
    ll ssum; //满足条件的数的平方和
    status() {cnt = -1 ; sum = 0 ; ssum = 0;}
    status(ll cnt , ll sum ,ll ssum) : cnt(cnt) , sum(sum) ,ssum(ssum) {}
}dp[20][10][10]; //第一维表示位数，第二位表示数位和mod6的值，第三维表示数值mod7的值
ll digit[20]; //用来保存每一位的数字
ll p[25]; // 存储10的i次方

status dfs(int pos, int pre , int sta ,bool limit){ //pos位数，pre数位和mod 6的值，数值mod 6的值 ，数字是否打到边界 即213的百位是否枚举到2 然后枚举十位只能枚举到1
    if(!pos) return pre != 0 && sta != 0 ? status(1 , 0 , 0) : status(0 , 0 , 0);  //如果当前数位和mod6不等于0并且数值mod6不为0 就表示这个数是合法的
    if(!limit && dp[pos][pre][sta].cnt != -1) return dp[pos][pre][sta];  
    int limitmax = limit ? digit[pos] : 9;
    status ans;
    ans.cnt = 0;
    for(int i = 0 ; i <= limitmax ; ++i){
        if(i == 7) continue;
        status next = dfs(pos - 1 ,  (pre + i) % 7 , (sta * 10 + i) % 7 , limit && i == limitmax);
        ans.cnt += next.cnt; //数的个数
        ans.cnt %= MOD;
        ans.sum += (next.sum + ((p[pos] * i ) % MOD) * next.cnt %MOD) % MOD;
        ans.sum %= MOD; 
        ans.ssum += (next.ssum + ((2 * p[pos] * i) % MOD) * next.sum) % MOD;
        ans.ssum %= MOD;
        ans.ssum += ((next.cnt * p[pos]) % MOD * p[pos] % MOD * i * i % MOD);
        ans.ssum %= MOD;
    }
    if(!limit) dp[pos][pre][sta] = ans;
    return ans;
}

ll solve(ll x){  
    int pos = 0;
    while(x){
        digit[++pos] = x % 10;
        x /= 10;
    }
    status tt = dfs(pos , 0 , 0 ,true);
    return tt.ssum;
}

int main(void){
    ll l , r;
    p[1] = 1;
    int T;
    for(int i = 2 ; i <= 20 ; ++i) 
        p[i] = (p[i - 1] * 10) % MOD;
    cin>>T;
    while(T--){
        scanf("%lld%lld",&l,&r);
        ll ans=solve(r);
        ans-=solve(l-1);
        printf("%lld\n",(ans % MOD + MOD) % MOD);
    }
    return 0;
}