数位 dp / lianggj 让你学小专题应该怎么办

P4999

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)

using namespace std;

const int N=20, M=9*18+5, P=1e9+7; 

int t, l, r, f[N][M], a[N], len, ans;

/*
Q：查询 i in [l,r] 的 i 的数位和。
A：f[i][j] 表示任意填写 pos=1,...,i 的，以前填了 j 的数和，这个时候的任意合法情况数位和 
*/ 
int dfs(int i,bool limit,int sum) {
	if(!i) return sum; // 边界 
	if(!limit&&f[i][sum]>=0) return f[i][sum]; // 记忆化 
	int d=limit?a[i]:9, res=0; // 求一个上界 
	up(v,0,d) res=(res+dfs(i-1,limit&&v==a[i],sum+v))%P; // 枚举填什么东西 
	if(!limit) f[i][sum]=res; // 记忆化 
	return res;
}

int solve(int x) {
	len=0; // 拆位喵 
	while(x) a[++len]=x%10, x/=10;
	return dfs(len,1,0);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(f,-1,sizeof(f));
	cin >> t;
	while(t--) {
		cin >> l >> r, ans=solve(r)-solve(l-1); // 容斥成 [1,x] 的询问 
		cout << (ans%P+P)%P << '\n';
	}
	return 0;
}

P2602

#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)

using namespace std;

const int N=20, M=9*18+5; 

int t, l, r, f[N][M][2], a[N], len, ans[10], digit; 
/*
Q： i in [l,r] 中每个数码的出现次数，对于 digit=1,...,9 答案显然相同 
A： f[i][j][0/1] 表示任意填 pos=1,...,i，以前填了 j 个这种数码，这个数码是/不是 0 的情况下的该数码出现总次数 
*/ 

int dfs(int i,bool limit,bool lead,int cnt) {
	// 含义是填了 i+1,...,len 现在要填 i，能不能任意填写，前导 0 有没有被消除，现在填了 cnt 个数码的数码出现总次数 
	if(!i) return cnt;
	auto &now=f[i][cnt][digit!=0];
	if(!limit&&!lead&&now>=0) return now;
	int d=limit?a[i]:9, res=0;
	up(v,0,d) {
		int val=(lead&&digit==0&&v==0)?0:(cnt+(v==digit)); // 前导 0 不能算进去 >w< 
		res+=dfs(i-1,limit&&v==a[i],lead&(v==0),val); 
	}
	if(!limit&&!lead) now=res;
	return res;
}

void solve(int x,int k) {
	len=0;
	while(x) a[++len]=x%10, x/=10;
	up(i,0,9) digit=i, ans[i]+=k*dfs(len,1,1,0);
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(f,-1,sizeof(f));
	cin >> l >> r;
	solve(l-1,-1), solve(r,1);
	up(i,0,9) cout << ans[i] << ' ';
	return 0;
}