Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP3896 [湖南集训]Clever Rabbit

Posted on Edited on In
Symbols count in article: 2.2k Reading time ≈ 2 mins.

一道很暴力的题

Clever Rabbit

一看 $n \le 30$ ，时限4s，第一反应打表能过，仔细回味，发现 $10^{30}$ 铁挂，而且20分的 $n \le 10$ 都会挂，这……

但不能浪费我辛苦打出来的表（由于 $x = 0$ 对答案无贡献，故保证 $x > 0$ ）：

n x
1 -
2 -
3 495
4 6174
5 -
6 549945
631764
7 -
8 63317664
97508421
9 554999445
864197532

9的数据都跑了进3min……

然后又是全凭rp的找规律时间，浪费时间ing

发现一个小规律，看图：

竖式

我们发现 $b$ 数是对称且单调下降的（下降不严格），证明也很好证（自己列个竖式就知道了），那么我们可以枚举 $b$ 的一半，计算另一半，然后得到 $b’$ 排序后得到 $c, d$ ，计算检验即可，然鹅， $10^{\frac{n}{2}} = 10^{15}$ 次方也是挂了

突然发现只需枚举 $0 \sim 9$ 每个数出现了多少次，计算 $max,min,max - min$ 判断即可，考虑时间复杂度，看似是 $n^{10} * n$ （跑不满），但实际上用隔板法可知为 $O(\binom{n + 10 - 1}{9}n)$ ， 注意解决一下高精减法，可以得60分（开了O2可以70分）

再考虑我们打表发现的性质，还是生成 $b$ ，但和上面一样，只枚举 $b$ 的前 $\frac{n}{2}$ 个数中 $0 \sim 9$ 各出现了多少次，由于 $b$ 单调，故只有一种合法排列，生成 $b’$ 后暴力检验 ，特殊处理一下 $n$ 为奇数时中间的数（一定是0）

不开O2最慢的点1.89s（时限4s，能过），开了O2快得飞起，最慢的点412ms

考虑优化（毕竟1.89s太讨厌了），那个排序可以开个桶，把 $\log n$ 优化了（然鹅 $n \le 30$ 所以 $\log n$ 几乎就是常数），再就是其实可以先不求出 $b’$ 用 $b$ 的一半即可判断是否合法，合法再求（常数优化），然后卡卡常，时间复杂度为 $O(\binom{\frac{n}{2} + 10 -1}{9}n)$ ，不开O2最慢的点322ms，开了O2最慢的点205ms，好像除了打表的大佬（竟然真的可以打表，蒟蒻想都不敢想）我混了个最快？估计马上就会被大佬们超过

代码：

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
#include <bits/stdc++.h>
#define LL long long
#define IL inline
#define re register
using namespace std;
const int  N = 30 + 5, A = 15;
int n, p, m, o;
int t, cnt;
int a[A], b[N], c[N], d[N];
int B[A]; //桶
int ans = 0;
IL void check()
{
	t = 0;
	for (re int i = 0; i <= 9; ++i)
		for (re int j = 1; j <= B[i]; ++j)
			c[++t] = i, d[n - t + 1] = i;
	for (re int i = 1; i <= cnt; ++i)
		d[i] = d[i] - c[i];
	for (re int i = 1; i <= cnt; ++i)
		if (d[i] != b[i])
			return ;
	for (re int i = 1; i <= cnt; ++i)
		b[n + 1 - i] = -b[i];
	for (re int i = n; i >= 1; --i)
		if (b[i] < 0)
			b[i] += 10, --b[i - 1];
		else
			break;
	t = 0;
	for (re int i = 1; i <= n; ++i)
		t = ((LL)t * 10 + b[i]) % p;
	ans = (((LL)t * t % p) + ans) % p;
}
IL void work() //生成b'
{
	for (re int i = 0; i <= 9; ++i)
		B[i] = 0;
	cnt = 0;
	for (re int i = 9; i >= 0; --i)
		for (re int j = 1; j <= a[i]; ++j)
			b[++cnt] = i;
	if (o)
		b[cnt + 1] = 0, ++B[9];
	for (re int i = cnt, f = 1; i >= 1; --i)
	{
		if (i != 1)
			++B[9 - b[i]];
		else
			++B[10 - b[i]];
		if (b[i] == 0 && f)
			++B[9];
		else if (f)
			++B[b[i] - 1], f = 0;
		else
			++B[b[i]];
	}
}
IL void dfs(int x, int r)
{
	if (x == 9)
	{
		a[x] = r;
		work();
		check();
		return ;
	}
	for (re int i = 0; i <= r; ++i)
	{
		a[x] = i;
		dfs(x + 1, r - i);
	}
}
int main()
{
	scanf("%d%d", &n, &p);
	o = n & 1;
	m = n >> 1;
	dfs(0, m);
	printf("%d\n", ans % p);
	return 0;
}