20190830模拟赛统计

发表于 分类于

$Problem’s$ $Website$

统计

（没有权限查看题目的同学不要打我）

$Solution$

这道题是一道 思想 + 码农 题，很不错。

题意清楚明了，但做法却十分复杂。。。

根据数据范围$n \le 50$，我们得出结论——要用高精度计算。

因为有前导$0$ 的存在，所以对于$k\ =\ 0$时要单独讨论。

下面详细说一下做法。

  • $k\ =\ 0$

当$k\ =\ 0$时，我们发现，只要有一位是$0$就符合要求，对于$n$位数，根据乘法原理，一共有$\prod\limits_{i=1}^{n}{10}$种方案数，其中不包含$0$的有$\prod\limits_{i=1}^{n}{9}$种，所以答案作差即可。

  • $k\ \neq\ 0$

当$k\ \neq\ 0$时，我们考虑进行$dp$，不难得出状态$f[i][j]$为第$i$位组成$j$的方案数，然而观察数据范围，我们发现$k \le 10^9$，那么这样是定义不了数组的，于是我们想改善，我们可以把$k$分解因数，$f[i][j]$为第$i$位由第$j$个因数所能组成数的方案数，首先用一个数组存因数并且进行排序，然后第一遍枚举位数，第二遍枚举因数个数，第三遍枚举$1-9$(因为一位最多到$9$，用这些数去$\times$当前循环到的因数来转移状态)，如果当前乘出来的数也是一个因数，那么$f[i + 1][temp]\ += \ f[i][j];$，最后答案即为$f[n][cnt]$($cnt$为因数个数)。

最后再次强调，这道题要写高精度！！！

同时注意定义变量的细节！！！

$Code$

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
int n, k, cnt;
long long num[1010];
#define re register
const int mod = 1e4;
struct HN {
	int p[60], len;
	HN() {
		len = 0;
		memset(p, 0, sizeof(p));
	}
	inline void print() {
		printf("%d", p[len]);
		for(re int i = len - 1; i > 0; --i) {
			if(!p[i]) {
				printf("0000");
				continue;
			}
			for(re int k = 10; k * p[i] < mod; k *= 10)
				printf("0");
			printf("%d", p[i]);
		}
	}
}f[60][1010];
using std :: max;
HN operator  + (const HN &x, const HN &y) {
	HN temp;
	int num = 0;
	temp.len = max(x.len, y.len);
	for(re int i = 1; i <= temp.len; ++i) {
		temp.p[i] = x.p[i] + y.p[i] + num;
		num = temp.p[i] / mod;
		temp.p[i] %= mod;
	}
	while(num > 0) {
		temp.p[++temp.len] = num % mod;
		num /= mod;
	}
	return temp;
}
using std :: swap;
HN operator - (const HN &x, const HN &y) {
	HN temp;
	temp.len = max(x.len, y.len);
	for(re int i = 1; i <= temp.len; ++i) {
		if(temp.p[i] + x.p[i] - y.p[i] < 0)
			temp.p[i] += mod, temp.p[i + 1]--;
		temp.p[i] += x.p[i] - y.p[i];
	}
	while(temp.len > 0 && temp.p[temp.len] == 0)
		--temp.len;
	return temp;
}
HN operator * (const HN &x, int y) {
	HN temp;
	int num = 0;
	temp.len = x.len;
	for(re int i = 1; i <= temp.len; ++i) {
		temp.p[i] = x.p[i] * y + num;
		num = temp.p[i] / mod;
		temp.p[i] %= mod;
	}
	while(num > 0) {
		temp.p[++temp.len] = num % mod;
		num /= mod;
	}
	return temp;
}
inline int find(long long x) {
	int res = std :: lower_bound(num + 1, num + cnt + 1, x) - num;
	return num[res] == x ? res : -1;
}
int main() {
	scanf("%d%d", &n, &k);
	if(!k) {
		HN num1, num2;
		num1.p[1] = num2.p[1] = 1;
		num1.len = num2.len = 1;
		for(re int i = 1; i <= n; ++i)
			num1 = num1 * 10;
		for(re int i = 1; i <= n; ++i)
			num2 = num2 * 9;
		HN num3 = num1 - num2;
		num3.print();
		putchar('\n');
		return 0;
	}
	for(re int i = 1; i * i <= k; ++i) {
		if(k % i == 0) {
			num[++cnt] = i;
			if(i * i != k)
				num[++cnt] = k / i;
		}
	}
	std :: sort(num + 1, num + cnt + 1);
	f[0][1].p[1] = 1, f[0][1].len = 1;
	for(re int i = 2; i <= cnt; ++i)
		f[0][i].p[1] = 0, f[0][i].len = 1;
	for(re int i = 0; i < n; ++i) {
		for(re int j = 1; j <= cnt; ++j) {
			for(re int l = 1; l <= 9; ++l) {
				if((long long)(l * num[j]) <= k) {
					int temp = find(l * num[j]);
//					printf("%d ", temp);
					if(temp != -1)
						f[i + 1][temp] = f[i + 1][temp] + f[i][j];
				}
			}
		}
	}
	f[n][cnt].print();
	putchar('\n');
	return 0;
}

$rp++$