数位dp模板(灵神的)仅为个人学习使用

给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：

num1 <= x <= num2
min_sum <= digit_sum(x) <= max_sum.
请你返回好整数的数目。答案可能很大，请返回答案对 1e9 + 7 取余后的结果。

注意，digit_sum(x) 表示 x 各位数字之和。

class Solution {
public:
    int count(string num1, string num2, int min_sum, int max_sum) {
        int MOD = 1E9+7;
        int n = num2.size();
        num1 = string(n-num1.size(),'0') + num1;
        vector<vector<int>> cache(n+1,vector<int>(10*n,-1));
        function<int(int,int,bool,bool)> dfs = [&](int u,int sum,bool limit_low,bool limit_high) ->int{
            if(sum>max_sum||sum<min_sum&&u==n) return 0;
            if(u == n) return 1;
            if(!limit_high&&!limit_low&&cache[u][sum]!=-1) return cache[u][sum];
            int low = limit_low?num1[u]-'0':0;
            int high = limit_high?num2[u]-'0':9;
            int res = 0;
            for(int i = low;i<=high;i++)
            {
                res = (res+dfs(u+1,sum+i,limit_low&&i == low,limit_high&&i == high))%MOD;
            }
            if(!limit_high&&!limit_low) cache[u][sum] = res;
            return res;
        };

        return dfs(0,0,true,true);
    }
};

2.

#include<bits/stdc++.h>
using namespace std;
const int N = 100;
typedef long long LL;
const int mod = 1e9+7;
int n,used[12];
char a[N],b[N],to[12];
LL dfs(int u,int sum,bool is_limit)
{
    if(u == n+1) return sum == 0;
    if(a[u]>='0'&&a[u]<='9')
    {
        if(a[u]>b[u]&&is_limit) return 0;
        return dfs(u+1,(sum*10+a[u]-'0')%8,is_limit&&a[u] == b[u]);
    }
    LL res = 0;
    if(a[u]>='a'&&a[u]<='d')
    {
        if(to[a[u]-'a'] != '#')
        {
            if(is_limit&&to[a[u]-'a'] >b[u]) return 0;
            return dfs(u+1,(sum*10+to[a[u]-'a']-'0')%8,is_limit&&to[a[u]-'a'] == b[u]);
        }
        else 
        {
            int start = (u == 1)&&(n>1)?1:0;//去除前导0
            for(int i= start;i<=9;i++)
            {
                if(used[i]) continue;
                if(is_limit&&i>b[u]-'0') continue;
                used[i] = 1;
                to[a[u]-'a'] = i+'0';
                res = (res+dfs(u+1,(sum*10+i)%8,is_limit&&(i == b[u]-'0')))%mod;
                used[i] = 0;
                to[a[u]-'a'] = '#';
            }
        }
    }
    else if(a[u] == '_')
    {
        int start = (u == 1)&&(n>1)?1:0;//去除前导0
            for(int i= start;i<=(is_limit?b[u]-'0':9);i++)
            {
                res = (res+dfs(u+1,(sum*10+i)%8,is_limit&&(i == b[u]-'0')))%mod;
            }
    }
    return res;
}
void solve()
{
    scanf("%d",&n);
    scanf("%s",a+1);
    scanf("%s",b+1);
    memset(to,'#',sizeof to);    
    if(a[1] == '0')
    {
        if(n>1) puts("0");
        else puts("1");
    }
    else printf("%lld\n",dfs(1,0,1));
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}