P2518-[HAOI2010]计数
题目:
题目描述:
你有一组非零数字（不一定唯一），你可以在其中插入任意个0，这样就可以产生无限个数。比如说给定{1, 2}, 那么可以生成数字12, 21, 102, 120, 201, 210, 1002, 1020, 等等。
现在给定一个数，问在这个数之前有多少个数。（注意这个数不会有前导0）.
输入格式:
只有1行，为1个整数n.
输出格式:
只有整数，表示N之前出现的数的个数。
样例:
样例输入1:
样例输出1:
思路:
我们发现$a_1个1, a_2个2, a_3个3\cdots$的可重集排列的答案:
记m为数的总数, n为数的总类.
$\tbinom{m}{a_1}+\tbinom{m-a_1}{a_2}+\tbinom{m-a_1-a_2}{a_3}+\cdots$
实现:
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
| // Problem: P2518 [HAOI2010]计数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2518
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Author: Ybw051114
//
// Powered by CP Editor (https://cpeditor.org)
#include "ybwhead/ios.h"
const int maxn = 101;
int a[maxn];
long long c[maxn][maxn];
long long calc(int nw)
{
long long ans = 1;
for (int i = 0; i <= 9; i++)
{
ans *= c[nw][a[i]];
nw -= a[i];
}
// yout << ans << endl;
return ans;
}
int main()
{
string s;
yin >> s;
int n = s.size();
c[0][0] = 1;
for (int i = 1; i <= n; i++)
{
c[i][0] = c[i][i] = 1;
for (int j = 1; j < i; j++)
{
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
}
}
for (int i = 0; i < s.size(); i++)
a[s[i] - '0']++;
long long ans = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < s[i] - '0'; j++)
{
a[j]--;
ans += calc(n - i - 1);
a[j]++;
}
a[s[i] - '0']--;
}
yout << ans << endl;
return 0;
}
|