题意
定义两个整数 \(A,B\) 之间的距离为这两个整数所有对应位上的数的差的绝对值之和，记为 \(\operatorname{dist}(A,B)\)。特别地，如果 \(A,B\) 两数的位数不相同，则在位数较小的数前补足前导 \(0\)。
现在，给定两个整数 \(L,R\)，请你求出所有在区间 \([L,R]\) 内的整数对的距离和。请对 \(\bf 10^9+7\) 取模。
分析
考虑记录在每一个数位上每个数出现了多少次。
令 \(cnt_{i,j}\) 表示第 \(i\) 位上数码 \(j\) 出现了多少次。
这样我们就可以枚举数码 \(j\) 以统计答案，答案即为：
\[2\cdot\sum_{i=1}^{\text{len}(R)}\sum_{j=0}^9\sum_{k=j+1}^9(k-j)\times cnt_{i, j}\times cnt_{i, k} \]我们只需要解决 \(cnt\) 的计数问题就行了。
首先将问题转化为求 \([0, L-1]\) 和 \([0, R]\) 各数码在每一位出现的次数，二者相减即是答案区间 \([L, R]\)。
上面所求的可以使用数位 dp 解决。
时间复杂度 \(O(\log R)\)。
Code
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int64_t ksm(int64_t x, int l)
{
int64_t ret=1;
for(;l;l>>=1, x=x*x%mod)
if(l&1) ret=ret*x%mod;
return ret;
}
int64_t cnt[50004][10];
int64_t tag[50004];
int64_t calc(const string &s, int p, int op)
{
if(p<0) return 1;
int64_t mx=s[p]^48;
int64_t w=ksm(10, p);
if(p) tag[p-1]=((tag[p-1]+op*ksm(10, p-1)*mx)%mod+mod)%mod;
for(int i=0;i<mx;i++) cnt[p][i]=((cnt[p][i]+w*op)%mod+mod)%mod;
int64_t ret=mx*w%mod;
int64_t tmp=calc(s, p-1, op);
cnt[p][mx]=((cnt[p][mx]+tmp*op)%mod+mod)%mod;
return (ret+tmp)%mod;
}
string a, b;
void reduce(string &s)
{
reverse(s.begin(), s.end());
for(auto &c:s)
{
if(c^48) {c--; break;}
c='9';
}
if(s.back()=='0') s.pop_back();
reverse(s.begin(), s.end());
}
int main()
{
cin>>a>>b;
reduce(a);
reverse(b.begin(), b.end());
reverse(a.begin(), a.end());
while(a.size()<b.size()) a.push_back('0');
calc(b, b.size()-1, 1);
calc(a, a.size()-1, -1);
for(int i=b.size()-1;~i;i--)
{
tag[i]=(tag[i]+tag[i+1])%mod;
for(int j=0;j<10;j++)
cnt[i][j]=(cnt[i][j]+tag[i])%mod;
}
int64_t ans=0;
for(int i=b.size()-1;~i;i--)
for(int j=0;j<10;j++)
for(int k=j+1;k<10;k++)
ans=(ans+(k-j)*cnt[i][j]%mod*cnt[i][k])%mod;
cout<<ans*2%mod;
}