小圆前辈的888

题目大意:

在[0,n]的区间里找到数字末尾为8的数,且贡献为各个位数和,求其贡献总和.

思路:

首先题目问区间[0,n]，可以考虑用数位dp写，题目需要计算每个数的数位和，显然我们不能将他当参数放入dfs中最后return，所以我们需要考虑如何在dfs的过程中计算每个数位的贡献。可以参考下面图片。

假设黄点是0，蓝点是1，假设题目是二进制，要计算的是数位末尾为1的各个数位相加，那么上图是区间[0,5]的贡献，明显可以看到，每个节点需要算个贡献就是其数位 ,为以该节点为根的子树的叶子节点是的数量。

代码实现：

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=2e5+7;
const ll mod=1e9+7;
int n,a[N];
ll f[N][10][2],dp[N][10][2];
char s[N];
ll ikuzo(int p,int k,int lim){
    if(p>n){
        if(k==8) return 1;
        return 0;
    }
    if(f[p][k][lim]) return f[p][k][lim]%mod;
    int up=lim? a[p]:9;
    ll ans=0;
    for(int i=0;i<=up;i++){
        ans=(ans+ikuzo(p+1,i,lim&&(i==up))%mod)%mod;
    }
    return f[p][k][lim]=ans%mod;
}

ll dfs(int p,int k,int lim){
    if(p>n){
        if(k==8) return 8;
        return 0;
    }
    if(dp[p][k][lim]!=-1) return dp[p][k][lim];
    int up=lim? a[p]:9;
    ll ans=0;
    for(int i=0;i<=up;i++){
        ans=((ans+dfs(p+1,i,lim&&(i==up)))%mod+i*f[p+1][i][lim&&(i==up)]%mod)%mod;
    }
    return dp[p][k][lim]=ans%mod;
}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    memset(f,0,sizeof(f));
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++){
        a[i]=s[i]-'0';
    }
   ikuzo(1,0,1);
   printf("%lld\n",dfs(1,0,1)%mod);
}