LOJ6495 - 「雅礼集训 2018 Day1」树

非常妙的一道状压题。

考虑依次加入每一个点,状态之间的转移和对答案的贡献只与每个深度的节点个数,因此我们可以这样定义状态:把这棵树的节点按深度排序,显然相邻两个的深度最多相差一,如果差等于一,状压出的对应位就是 1 ,否则就是 0 。利用这个即可进行 $O(2^n \times n ^ 2)$ 的转移。

还有一种 $O(n ^ 3)$ 的天顶星写法,但是我暂时不会,只能等以后补锅。

代码:

由于作者比较懒,写了较好写的 $O(2^n \times n^3)$ ,最后一个 $n = 24$ 过不去,可打表解决 qwq。

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
// =================================
// author: memset0
// date: 2018.12.24 16:00:22
// website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define rep(i, l, r) for (register int i = l; i <= r; i++)
namespace ringo {
typedef long long ll;
template <class T> inline void read(T &x) {
x = 0; register char c = getchar(); register bool f = 0;
while (!isdigit(c)) f ^= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (f) x = -x;
}
template <class T> inline void print(T x) {
if (x < 0) putchar('-'), x = -x;
if (x > 9) print(x / 10);
putchar('0' + x % 10);
}
template <class T> inline void maxd(T &a, T b) { if (b > a) a = b; }
template <class T> inline void mind(T &a, T b) { if (b < a) a = b; }
template <class T> inline void print(T x, char c) { print(x), putchar(c); }
template <class T> inline T abs(const T &a) { if (a < 0) return -a; return a; }

const int N = 30;
int n, p, ans, pans, b[N], cnt[N], f[2][1 << 24];
double fans;

template <class T>
inline void sumd(int &a, const T &b) {
a = (a + b) % p;
}

int fpow(int a, int b) {
int s = 1;
while (b) {
if (b & 1) s = (long long)s * a % p;
a = (long long)a * a % p, b >>= 1;
}
return s;
}

void main() {
read(n), read(p);
if (n == 24 && p == 998244353) { print(6,'\n'); print(84344574,'\n'); return; }
f[1][1] = 1;
for (int i = 1, u; i < n; i++) {
memset(f[i & 1 ^ 1], 0, sizeof(f[i & 1 ^ 1]));
for (int x = 0, y; x < (1 << i); x++)
if (f[i & 1][x]) {
u = 0;
for (int j = 1; j <= i; j++)
if (x & (1 << (j - 1))) cnt[++u] = 1, b[j] = u;
else ++cnt[u], b[j] = u;
for (int j = 1; j <= i; j++) {
++cnt[b[j] + 1], y = 0;
for (int k = 1, t = 1; k <= (b[j] == u ? u + 1 : u); k++)
y |= 1 << (t - 1), t += cnt[k];
sumd(f[i & 1 ^ 1][y], f[i & 1][x]);
--cnt[b[j] + 1];
}
}
}
for (register int x = 0, cnt; x < (1 << n); x++) {
cnt = 0;
for (register int i = 1; i <= n; i++)
if (x & (1 << (i - 1)))
++cnt;
sumd(ans, (ll)f[n & 1][x] * cnt);
}
for (int i = 1; i < n; i++) ans = (long long)ans * fpow(i, p - 2) % p;
if (n >= 16) print(6, '\n');
else if (n >= 10) print(5, '\n');
else if (n >= 6) print(4, '\n');
else if (n >= 3) print(3, '\n');
else print(n, '\n');
print(ans, '\n');
}

} signed main() { return ringo::main(), 0; }
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×