Description

求一颗nn个节点树的期望深度（ii号节点的父亲在[1,i)[1,i)中均匀随机）

第一问不取模，四舍五入到整数

第二问对质数pp取模

Constraints

n≤24,p≤109+7n \leq 24, p \leq 10^9 + 7 且pp为质数

Solution

第一问直接打表

第二问由于每一种情况的概率相同，便能将期望问题转化为计数问题，考虑Dp

暴力记录每个点的深度状态显然不行，考虑到树上节点深度都是连续的，那么排序，差分过后一定是一个0/10/1序列

那么就可以记录这个0/10/1序列，进行状压Dp了

我的做法好像和std有一点不一样，常数大一些，需要加一些优化才能过

设dp[state]dp[state]表示0/10/1序列为statestate的树有多少种

那么新增一个节点，枚举它的深度ii，设sumsum 为在statestate中深度-1的节点个数

那么dp[state′]=dp[state′]+dp[state]∗sumdp[state'] = dp[state'] + dp[state] * sum

直接暴力转移即可

优化：加法取模函数，快速乘瞬间从6s变成1.6s

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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
#include <bits/stdc++.h>

#define double long double
#define x first
#define y second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
template <typename T> T read()
{
	int fl = 1, sum = 0; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fl = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - '0', ch = getchar();
	return sum * fl;
}
#include <bits/stdc++.h>

#define double long double
#define x first
#define y second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
template <typename T> T read()
{
	int fl = 1, sum = 0; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fl = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - '0', ch = getchar();
	return sum * fl;
}

const int Maxn = 30;

int N, Mod, Dp[(1 << 25) + 100];
bool Vis[(1 << 25) + 100];

inline void Add (int &x, int y)
{
	x += y;
	if (x >= Mod) x -= Mod;
}

inline int Mult (int a, int b)
{
	int ans = 0;
	while (b)
	{
		if (b & 1) Add (ans, a);
		Add (a, a);
		b >>= 1;
	}
	return ans;
}

inline int Pow (int a, int b)
{
	int ans = 1;
	while (b)
	{
		if (b & 1) ans = Mult (ans, a);
		a = Mult (a, a);
		b >>= 1;
	}
	return ans;
}

int Ans[30] = {0, 1, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6};
int Pow2[30];
struct node
{
	int cnt, pos;
}A[30];

main()
{
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	N = read<int>(), Mod = read<int>();
	printf("%d\n", Ans[N]);
	for (int i = 0; i < 30; ++i) Pow2[i] = (1ll << i);
	int POS = 0;
	Dp[1] = 1;
	Vis[1] = 1;
	for (int state = 1; state < Pow2[N]; ++state)
	{
		if (state >= Pow2[POS]) ++POS;
		if (!Vis[state]) continue;
		int sum = 0, fl = 0, cnt = 0;
		for (int i = 0; i < POS; ++i)
		{
			++cnt;
			if (state & (Pow2[i]))
				A[++sum].cnt = cnt, A[sum + 1].pos = i + 1, cnt = 0;
		}
		Add (Dp[state << 1 | 1], Mult (Dp[state], A[1].cnt)); 
		Vis[state << 1 | 1] = 1;
		for (int i = 1; i < sum; ++i)
		{
			int now = state & (Pow2[A[i].pos] - 1);
			Add (Dp[(state ^ now) << 1 | now], Mult (Dp[state], A[i + 1].cnt));
			Vis[(state ^ now) << 1 | now] = 1;
		}
	}
	int ans = 0;
	for (int state = Pow2[N - 1]; state < Pow2[N]; ++state) 
	{
		if (!Vis[state]) continue;
		int cnt = __builtin_popcount(state);
		//		cout<<state<<" "<<Dp[state]<<" "<<cnt<<endl;
		Add (ans, Mult (Dp[state], cnt));
	}
	//	cout<<"*"<<ans<<endl;

	int sum = 1;
	for (int i = 1; i < N; ++i) sum = Mult (sum, i);
	cout<<Mult (ans, Pow(sum, Mod - 2))<<endl;
	return 0;
}
const int Maxn = 30;

int N, Mod, Dp[(1 << 25) + 100];
bool Vis[(1 << 25) + 100];

inline void Add (int &x, int y)
{
	x += y;
	if (x >= Mod) x -= Mod;
}

inline int Mult (int a, int b)
{
	int ans = 0;
	while (b)
	{
		if (b & 1) Add (ans, a);
		Add (a, a);
		b >>= 1;
	}
	return ans;
}

inline int Pow (int a, int b)
{
	int ans = 1;
	while (b)
	{
		if (b & 1) ans = Mult (ans, a);
		a = Mult (a, a);
		b >>= 1;
	}
	return ans;
}

int Ans[30] = {0, 1, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6};
int Pow2[30];
struct node
{
	int cnt, pos;
}A[30];

main()
{
	freopen("tree.in", "r", stdin);
	freopen("tree.out", "w", stdout);
	N = read<int>(), Mod = read<int>();
	printf("%d\n", Ans[N]);
	for (int i = 0; i < 30; ++i) Pow2[i] = (1ll << i);
	int POS = 0;
	Dp[1] = 1;
	Vis[1] = 1;
	for (int state = 1; state < Pow2[N]; ++state)
	{
		if (state >= Pow2[POS]) ++POS;
		if (!Vis[state]) continue;
		int sum = 0, fl = 0, cnt = 0;
		for (int i = 0; i < POS; ++i)
		{
			++cnt;
			if (state & (Pow2[i]))
				A[++sum].cnt = cnt, A[sum + 1].pos = i + 1, cnt = 0;
		}
		Add (Dp[state << 1 | 1], Mult (Dp[state], A[1].cnt)); 
		Vis[state << 1 | 1] = 1;
		for (int i = 1; i < sum; ++i)
		{
			int now = state & (Pow2[A[i].pos] - 1);
			Add (Dp[(state ^ now) << 1 | now], Mult (Dp[state], A[i + 1].cnt));
			Vis[(state ^ now) << 1 | now] = 1;
		}
	}
	int ans = 0;
	for (int state = Pow2[N - 1]; state < Pow2[N]; ++state) 
	{
		if (!Vis[state]) continue;
		int cnt = __builtin_popcount(state);
		//		cout<<state<<" "<<Dp[state]<<" "<<cnt<<endl;
		Add (ans, Mult (Dp[state], cnt));
	}
	//	cout<<"*"<<ans<<endl;

	int sum = 1;
	for (int i = 1; i < N; ++i) sum = Mult (sum, i);
	cout<<Mult (ans, Pow(sum, Mod - 2))<<endl;
	return 0;
}