OI题解 - The Counting Problem [POJ 2282] | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI题解 - The Counting Problem [POJ 2282]

发表于 更新于 分类于 Valine：

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

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 ，欢迎提问~