不会数位dp,遂来补习
题意:给定区间 [ L , R ] [L,R] [L,R]求这个区间每个数字拆成10进制后的数字和.
按照固定套路,先要解决 0 到 n 0到n 0到n每个数字拆成10进制后的数字和.
然后把 n n n拆成一个长度为 l e n len len的串, d f s dfs dfs找到合法的 l e n len len位置上的合法解并且记录下来.
具体方法为 d f s ( c u r , s u m , t o p ) dfs(cur,sum,top) dfs(cur,sum,top)表示当前在 c u r cur cur位,和是 s u m sum sum,是否贴着上界 t o p top top
之后当前 c u r cur cur位能取的数字有两种情况:
1. t o p top top是 1 1 1,之前的情况已经贴着了,所以只能取 0 到 a [ c u r ] 0到a[cur] 0到a[cur].
2. t o p top top是 0 0 0,之前取数没有贴着上界,所以取数范围是 0 到 9 0到9 0到9.
如果当前是 t o p = = 1 & & i = = a [ c u r ] top==1\&\&i==a[cur] top==1&&i==a[cur],那么下一个状态就会贴着上界,否则就不是贴着上界的状态.
在 d f s dfs 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<bits/stdc++.h>
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";}
}