P4999 烦人的数学作业

不会数位dp,遂来补习
题意:给定区间$[L,R]$求这个区间每个数字拆成10进制后的数字和.
按照固定套路,先要解决$0到n$每个数字拆成10进制后的数字和.
然后把$n$拆成一个长度为$len$的串,$dfs$找到合法的$len$位置上的合法解并且记录下来.
具体方法为$dfs(cur,sum,top)$表示当前在$cur$位,和是$sum$,是否贴着上界$top$
之后当前$cur$位能取的数字有两种情况:
1.$top$是$1$,之前的情况已经贴着了,所以只能取$0到a[cur]$.
2.$top$是$0$,之前取数没有贴着上界,所以取数范围是$0到9$.
如果当前是$top==1\&\&i==a[cur]$,那么下一个状态就会贴着上界,否则就不是贴着上界的状态.
在$dfs$求解数位dp的情况,贴着上界的情况的讨论十分重要.

/*
I don't wanna be left behind,Distance was a friend of mine.
Catching breath in a web of lies,I've spent most of my life.
Catching my breath letting it go turning my cheek for the sake of this show
Now that you know this is my life I won't be told what's supposed to be right
Catch my breath no one can hold me back I ain't got time for that.
*/
#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair<int,int> pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector<int> G[maxn];
ll mod = 1e9+7;int a[20];
ll dp[20][200][2];
int dfs(int cur,int sum,bool top){
	if(cur==0) return sum;
	ll &ans = dp[cur][sum][top];
	if(ans!=-1) return ans;
	ans = 0;
	int bound = (top==1) ? a[cur] : 9;
	for(int i=0;i<=bound;i++){
		ans = ( ans+dfs(cur-1,sum+i,(top==1&&i==bound))%mod)%mod; 
	}
	return ans%mod;
}
ll solve(ll n){
	memset(dp,-1,sizeof(dp));
	int len = 0;
	while(n) a[++len] = n%10,n/=10;
	return dfs(len,0,1)%mod;
}
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;cin>>T;
	while(T--){
		ll L,R;cin>>L>>R;
		cout<<(((solve(R)-solve(L-1))%mod+mod)%mod)<<"\n";
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46