题目传送门
题意
给你
l
l
l 和
r
r
r ，问你
0
∼
9
0\sim9
0∼9在这里面分别出现了多少次。
解题方法
这个题是数位
d
p
dp
dp 的板子题，对于每一个数我们关注的是他第
i
i
i 位上的数是什么，而不是关注其他的东西，那么我们这个样子就非常好处理了，我们就一位一位向前转移好了，我们定义一个三维数组
d
p
[
i
]
[
j
]
[
k
]
dp[i][j][k]
dp[i][j][k]，表示到第
i
i
i 位上首位数是
j
j
j 内
k
k
k 出现的次数，初始化很好想，就是把左右的
d
p
[
1
]
[
i
]
[
i
]
dp[1][i][i]
dp[1][i][i] 都赋值为1，然后我们该如何转移呢，很好想的是:
d
p
[
i
]
[
j
]
[
k
]
=
∑
t
=
0
9
d
p
[
i
−
1
]
[
t
]
[
k
]
dp[i][j][k]=\sum_{t=0}^{9}dp[i-1][t][k]
dp[i][j][k]=t=0∑9dp[i−1][t][k] 但是这个样子我们显然少计算了在首位上对答案的更新，我们发现在
d
p
[
i
]
[
j
]
[
j
]
dp[i][j][j]
dp[i][j][j] 上贡献了
1
0
i
−
1
10^{i-1}
10i−1 个
j
j
j 的，因为在后面的位数都计算完毕以后，我们只需要计算在最顶位上
j
j
j 出现的次数即可，那么首位数上是
j
j
j 的数出现了
1
0
i
−
1
10^{i-1}
10i−1 次，那么答案就增加了这么多，最后我们统计答案的时候，我们先计算出位数比端点的数的位数少的
d
p
dp
dp 值统计出来，然后再统计位数一样的答案，对于每一位，我们只需要把小于这位的答案加起来，然后要注意一点的是，我们还要统计在这位数上面的那些数位对答案的贡献。 最后我们运用一下前缀和的思想，算出
0
∼
r
0\sim r
0∼r的答案减去
0
∼
l
−
1
0\sim l-1
0∼l−1的答案就是
l
∼
r
l\sim r
l∼r的答案，但是这个数位
d
p
dp
dp算出来的值并不是统计
i
i
i之前的数，而是
i
−
1
i-1
i−1，所以要记得加一统计答案。
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std
;
long long a
[15];
long long dp
[15][10][10];
long long ans
[10][2];
long long ksm(long long x
,long long y
)
{
long long ans
=1;
while(y
)
{
if(y
&1)ans
*=x
;
x
*=x
;
y
>>=1;
}
return ans
;
}
long long weishu
;
void work(long long x
,long long zkt
)
{
memset(dp
,0,sizeof(dp
));
memset(a
,0,sizeof(a
));
weishu
=0;
while(x
)
{
weishu
++;
a
[weishu
]=x
%10;
x
/=10;
}
for(long long i
=0;i
<=9;i
++)
dp
[1][i
][i
]=1;
for(long long i
=2;i
<=weishu
;i
++)
for(long long j
=0;j
<=9;j
++)
{
for(long long k
=0;k
<=9;k
++)
{
for(long long t
=0;t
<=9;t
++)
dp
[i
][j
][t
]+=dp
[i
-1][k
][t
];
}
dp
[i
][j
][j
]+=ksm(10,i
-1);
}
for(long long i
=1;i
<weishu
;i
++)
for(long long j
=1;j
<=9;j
++)
for(long long k
=0;k
<=9;k
++)
ans
[k
][zkt
]+=dp
[i
][j
][k
];
for(long long i
=1;i
<a
[weishu
];i
++)
for(long long k
=0;k
<=9;k
++)
ans
[k
][zkt
]+=dp
[weishu
][i
][k
];
for(long long i
=weishu
-1;i
;i
--)
{
for(long long j
=0;j
<a
[i
];j
++)
{
for(long long k
=0;k
<=9;k
++)
ans
[k
][zkt
]+=dp
[i
][j
][k
];
}
for(long long p
=weishu
;p
>i
;p
--)
ans
[a
[p
]][zkt
]+=a
[i
]*ksm(10,i
-1);
}
}
int main()
{
long long x
,y
;
scanf("%lld%lld",&x
,&y
);
work(y
+1,0);work(x
,1);
for(long long i
=0;i
<=9;i
++)
cout
<<ans
[i
][0]-ans
[i
][1]<<' ';
return 0;
}
