OI题解 - The Counting Problem [POJ 2282]

做这道题有一点烦,知道怎么做,但是码代码都码错了几次

QwQ


· 题意

给定正整数 $A,B$ ,统计$0$~$9$这些数字在 $A$ 到 $B$ 的整数中出现的次数(如 $2979$ 中$2$和$7$出现$1$次,$9$出现$2$次),不考虑前导零。

多组询问,对于每个询问输出 $10$ 个整数,依次表示 $0,1,2,3,4,5,6,7,8,9$ 的出现的次数。

数据规模:$1\leq A,B\leq 10^8$ ,不超过 $500$ 组询问,不保证 $A\leq B$ 。


· 解析

- 初步思考

可以采用类似前缀和的方法,分别算出 $1$到$B$的整数中$0\text~9$出现的次数 和 $1$到$(A-1)$的整数中$0\text~9$出现的次数,两个答案的对应项作差即可。

1
void GetCnt(ll cnt[10],char num[]);//num是将T储存为字符串的格式,答案储存在cnt中

温馨提醒:以下公式中提到的$C_n^m$都是组合数,表示“$n$个数中取$m$个的方案数”

- 求解 位数小于lenT 的正整数中$0\text~9$出现次数

记 T 的位数为 lenT(100的位数为3,7的位数为1)。

先考虑位数小于 lenT 的所有数 X。因为 lenX<lenT ,所以 X<T。这样的话,我们构造 X 就只需要保证 X 的首位不为 0。
那么我们枚举 lenX ,从 1 到 (lenT-1) 。

我们现在要统计数字 h(h≠0) 出现的次数恰好为 i 的位数为 lenX 的数 X 的个数:

  1. 如果 X 的最高位为 h,那么除去最高位的 (lenX-1) 位中,h 还要出现 (i-1) 次,则 (i-1) 个 h 出现的位置总共有 $C_{lenX-1}^{i-1}$ 种;
    确定 h 出现的数位后,还有 (lenX-i) 个数位没有确定,这些数位可以填除了 h 的任何数字(因为不是最高位,可以取 0 ,而且 h 只能出现 i 次,不能在这些数位中再出现),所以每个数位有 9 个数字可以填,统计一下就是 $9^{lenX-i}$ 种填法。
    综上,这种情况总共有 $(9^{lenX-i}\times C_{lenX-1}^{i-1})$ 个满足条件的数 X,而其中 h 出现的次数为 i ,则这种情况 h 共出现了 $(i\times 9^{lenX-i}\times C_{lenX-1}^{i-1})$ 个。

  2. 如果 X 的最高位不是 h,那么在剩下的 (lenX-1) 位中,h 要出现 i 次,则 h 出现的位置总共有 $C_{lenX-1}^i$ 种;
    再考虑其他不是 h 的数位:最高位不能填 h 和 0,有 8 种选择;除了最高位以及填 h 的数位,还有 (lenX-i-1) 个数位,这些数位可以填除了 h 的任何数,则有 9 种选择;总计 $8\times 9^{lenX-i-1}$ 种;

    综上,这种情况共有 $8\times 9^{lenX-i-1}\times C^i_{lenX-1}$ 个满足条件的 X,而其中 h 出现的次数为 i,则这种情况 h 共出现了 $(i\times 8\times 9^{lenX-i-1}\times C^i_{lenX-1})$ 个。

上述的两种情况相加就是满足条件的 X 的个数。

然后我们单独统计数字 0 出现的此时恰好为 i 的位数为 lenX 的 X 的个数:

由于 0 不能填在最高位,所以 i 个 0 必须填在除最高位的 (lenX-1) 个数位中,填 0 的位置的方案数为 $C_{lenX-1}^i$ ;

剩余还有 (lenX-i) 个数位,这些数位可以填除了 0 的任何数,共 9 种选择,所以共有 $9^{lenX-i}$ 种方案;

综上,总共有 $C^i_{lenX-1}\times 9^{lenX-i}$ 个满足条件的 X;而其中 0 出现的次数为 i,则这种情况 0 共出现了 $i\times C^i_{lenX-1}\times 9^{lenX-i}$ 个。

- 求解 位数等于lenT且小于等于T 的数中0~9出现的次数

假设整数 X 的(从左到右)前 (i-1) 个数位上的数字和 T 相同,设 T 的第 i 个数位上的数字为 p。

Tab. 第1个数位即最高位

= X的第 i 个数位填入小于 p 的数字

令 X 的第 i 个数位填入 q,则 q<p 。这样就保证了 X<T ,所以剩下的 (lenT-i) 个数位上就可以随便填数。

设剩下的 (lenT-i) 个数位中恰好有 j 个数位填数字 h,方案为 $C_{lenT-i}^j$;剩下的 (lenT-i-j) 个数位中除了 h 都可以填,方案为 $9^{lenT-i-j}$;总共有 $C^j_{lenT-i}\times9^{lenT-i-j}$。这里 h 可以取任何数字。

设第 i 个数位填入 q,剩下的 (lenT-i) 个数位随便填,就有 $10^{lenT-i}$ 种方案。

= X的第 i 个数位填入 p

也就是说我们已经确定了 X 和 T 的前 i 个数位相同。若要使 X≤T ,则必须使 X 的剩下的数位小于等于 T 剩下的数位,换个说法,也就是 $X \mod 10^{lenT-i}\leq T\mod 10^{lenT-i}$。

则 X 剩下的数位的取值有 $(T\mod 10^{lenT-i})+1$ 种(因为剩下的数位可以全部取0,所以要加1),所以 X 的第 i 位的数字 p 会出现 $(T\mod 10^{lenT-i})+1$ 次。

将以上的所有情况统计起来就好了。


· 源代码

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
int lef,rig;
ll cntl[10],cntr[10];
const ll jc[10]={1,1,2,6,24,120,720,5040,40320,362880};
ll C(int A,int B){
//C_B^A
return jc[B]/jc[A]/jc[B-A];
}
//求数字0~9在整数 1~T 中出现的次数
void GetCnt(ll cnt[],char num[]){ //num[] 即 T 的字符串形式
int LEN=strlen(num); //T 的位数
for(int i=0;i<10;i++) cnt[i]=0;
if(LEN==1 && num[0]=='0') return; //如果T=0,则“1~T”中没有数
for(int len=1;len<LEN;len++){ //枚举 lenX,长度小于 lenT
for(int i=1;i<=len;i++){ //数字h在X中恰好出现i次
ll tot;
/*最高位数字为h(h!=0)*/
tot=1;
//除了填h的数位还有 (lenX-i) 个数位可以填 9 个数字
for(int j=i+1;j<=len;j++) tot*=9;
tot=tot*C(i-1,len-1)*i;
for(int j=1;j<=9;j++) cnt[j]+=tot;
/*最高位数字不为h(h!=0)*/
if(i!=len){
tot=1;
//除了填h的数位和最高位,还有 (lenX-i-1) 个数位可以填 9 个数字
for(int j=i+2;j<=len;j++) tot*=9;
//最高位只能填 8 个数字
tot*=8;
tot=tot*C(i,len-1)*i;
for(int j=1;j<=9;j++) cnt[j]+=tot;
}
/*计算0*/
if(i!=len){ //0 不能填最高位
tot=1;
//除了填 0 的数位,还有 (lenX-i) 个数位可以填 9 个数字
for(int j=i+1;j<=len;j++) tot*=9;
tot=tot*C(i,len-1)*i;
cnt[0]+=tot;
}
}
}
for(int i=0;i<LEN;i++){
/*X的第(i+1)个数位填小于T的第(i+1)个数位的数*/
if(num[i]!='0')
for(int j=1;j<=LEN-i-1;j++){
ll tot=(num[i]-'0'+(i==0? -1:0))*C(j,LEN-i-1)*j;
for(int k=1;k<=LEN-i-1-j;k++) tot*=9;
for(int k=0;k<=9;k++)
cnt[k]+=tot;
}
ll tot=1;
//总共有 10^(lenX-i-2) 种填法
for(int j=i+1;j<LEN;j++) tot*=10;
for(int j=i==0?1:0;j<num[i]-'0';j++)
cnt[j]+=tot;
tot=0;
/*X的前(i+1)个数位与T的前(i+1)个数位相同*/
for(int j=i+1;j<LEN;j++)
tot=tot*10+num[j]-'0';
tot++;
cnt[num[i]-'0']+=tot;
}
}
int main(){
while(scanf("%d%d",&lef,&rig) && lef && rig){
char slef[15]="",srig[15]="";
if(lef>rig) swap(lef,rig);
lef--;
sprintf(slef,"%d",lef);sprintf(srig,"%d",rig);
GetCnt(cntl,slef);GetCnt(cntr,srig);
for(int i=0;i<=9;i++)
printf("%lld%c",cntr[i]-cntl[i],i==9? '\n':' ');
}
return 0;
}

The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~

0%