LuoguP2518「HAOI2010」题解

数(组)位(合)d(数)p(学) 经典题

题目描述

你有一组非零数字(不一定唯一),你可以在其中插入任意个0,这样就可以产生无限个数。比如说给定{1,2},那么可以生成数字12,21,102,120,201,210,1002,1020,等等。

现在给定一个数,问在这个数之前有多少个数。(注意这个数不会有前导0).

输入格式

只有1行,为1个整数n.

输出格式

只有整数,表示N之前出现的数的个数。

Inputs and Outputs examples

Inputs’ e.g. #1

1
1020

Outputs’ e.g. #1

1
7

数据范围

n的长度不超过50,答案不超过$2^{63}-1$.

分析

这玩意为什么要被放到数位dp的试炼场里……

观察题意,我们可以做一个微小的联想--把一个数中的一个0删除相当于把这个0挪到这个数的最前面.

那么题目也就转化成,统计一个数的全排列中比此数小的数的个数.

我们可以模仿数位dp中验证最大值限制时的做法,考虑用$num[i] \quad i \in [0,9]$来统计这个数中$0 - 9$的出现次数.

首先我们从最高位开始填数,设最高位填了数$j$,那么num[j]--.

然后我们从$0$开始填,其方案数为$\binom{n - 1}{num[0]}$

然后开始填$1$,这时候只有$n - 1 - num[0]$个位置了,方案数为$\binom{n - num[0] - 1}{num[1]}$

依次类推,我们根据乘法原理可以得到答案为:

$$\prod_{i=0}^9 \binom{n - 1 - \sum_{j=0}^i num_j}{num_i}$$

具体细节可以康康代码.

代码

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<iostream>
#include<map>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FORL(i,a,b,c) for(long long i=(a);i<=(b);i+=(c))
#define ROFL(i,a,b,c) for(long long i=(a);i>=(b);i-=(c))
#define FORR(i,a,b,c) for(register int i=(a);i<=(b);i+=(c))
#define ROFR(i,a,b,c) for(register int i=(a);i>=(b);i-=(c))
#define lowbit(x) x&(-x)
#define LeftChild(x) x<<1
#define RightChild(x) (x<<1)+1
#define RevEdge(x) x^1
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
#define IOS(x) std::ios::sync_with_stdio(x)
#define Dividing() printf("-----------------------------------\n");
namespace FastIO{
const int BUFSIZE = 1 << 20;
char ibuf[BUFSIZE],*is = ibuf,*its = ibuf;
char obuf[BUFSIZE],*os = obuf,*ot = obuf + BUFSIZE;
inline char getch(){
if(is == its)
its = (is = ibuf)+fread(ibuf,1,BUFSIZE,stdin);
return (is == its)?EOF:*is++;
}
inline int getint(){
int res = 0,neg = 0,ch = getch();
while(!(isdigit(ch) || ch == '-') && ch != EOF)
ch = getch();
if(ch == '-'){
neg = 1;ch = getch();
}
while(isdigit(ch)){
res = (res << 3) + (res << 1)+ (ch - '0');
ch = getch();
}
return neg?-res:res;
}
inline void flush(){
fwrite(obuf,1,os-obuf,stdout);
os = obuf;
}
inline void putch(char ch){
*os++ = ch;
if(os == ot) flush();
}
inline void putint(int res){
static char q[10];
if(res==0) putch('0');
else if(res < 0){putch('-');res = -res;}
int top = 0;
while(res){
q[top++] = res % 10 + '0';
res /= 10;
}
while(top--) putch(q[top]);
}
inline void space(bool x){
if(!x) putch('\n');
else putch(' ');
}
}
inline void read(int &x){
int rt = FastIO::getint();
x = rt;
}
inline void print(int x,bool enter){
FastIO::putint(x);
FastIO::flush();
FastIO::space(enter);
}
/* definitions */
#define type_T long long
const int MAXN = 1e3 + 10;
type_T YH[MAXN][MAXN];
int num[10],val[100],cnt;
/* functions */
inline void Combination(){
memset(YH,0ll,sizeof(YH));
YH[1][0] = YH[1][1] = 1ll;
FOR(i,2,1005,1){
YH[i][0] = 1ll;
FOR(j,1,i,1) YH[i][j] = YH[i-1][j] + YH[i-1][j-1];
}
}
inline type_T calcans(){
type_T ans = 1;
int m = cnt;
FOR(i,0,9,1) {if(num[i]) {ans *= YH[m][num[i]]; m -= num[i];}}
return ans;
}
int main(int argc,char *argv[]){
Combination();
char s = getchar();
while(true){if(!isdigit(s)) break; val[++cnt] = s - 48; num[val[cnt]]++; s = getchar();}
int n = cnt; type_T ans = 0;
FOR(i,1,n,1){
cnt--;
FOR(j,0,val[i] - 1,1)
if(num[j]){num[j]--; ans += calcans(); num[j]++;}
num[val[i]]--;
}
printf("%lld\n",ans);
return 0;
}

THE END