Digital DP template

Simply save a board , In order to avoid going through documents and websites everywhere in the future .

notes ： Not to explain , For personal use only .

explain

choose P2602 [ZJOI2010] The problem of number counting AC Code as a template .

1.dp Of n Each dimension of the dimension group represents a certain current state , Take this question as an example ,dp[pos][sum][st] in ,pos Represents the current number ,sum Indicates the number of occurrences of a number in the higher-order digits of the current digit ,st Indicates whether there is a leading 0.

2.dfs Search the possible value of each digit and save the current state . Again , Take this question as an example ,pos Indicates the current digit ,pre Indicates the size of the previous digit （ This question seems useless ）,st Indicates whether it is a leading 0,sum Indicates the number of occurrences of a certain number so far ,limit Indicates whether there is a size limit for the current digit .

3.solve What you get is [0,x] The number of intervals that meet the requirements , Want to get [L,R], use solve(R)-solve(L-1) that will do .

4. Make a reasonable plan dp Number and meaning of dimensions of array ,dfs The state of being carried , The filter condition is digits dp The key to .

Templates

/*@_krito*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LM LLONG_MAX
#define IM INT_MAX
#define _for(i,a,b) for(int i=a;i<=b;i++)
ll dp[15][15][2];
int a[15];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int spot;
ll dfs(int pos,int pre,int st,int sum,int limit){
	if(!pos) return sum;
	if(!limit&&dp[pos][sum][st]!=-1) return dp[pos][sum][st];
	ll res=0;
	int maxn=limit?a[pos]:9;
	_for(i,0,maxn){
		res+=dfs(pos-1,i,st&&(i==0),sum+((!st||i)&&(i==spot)),limit&&i==maxn);
	}
	dp[pos][sum][st]=res;
	return res;
}
ll solve(ll x)
{
	ll ans;
	int len=0;
	while(x) a[++len]=x%10,x/=10;
	memset(dp,-1,sizeof(dp));
	return ans=dfs(len,0,1,0,1);
}
int main(){
	ll ANS=0;
	ll L,R;
	scanf("%lld%lld",&L,&R);
	_for(i,0,9){
		spot=i;
		printf("%lld ",solve(R)-solve(L-1));
	}
	
}