$\text{OEIS}$ $trick$

$\text{score：100 + 0 + 0 = 100 rk：6/35}$

Problem A：数排列

题面

题解

打表，然后 $\text{OEIS}$ 第 A005802 序列

本来想着题解可能会给出正解，然而他这么说

问题是求一个数列的第 $n$ 项，但该数列显然不是线性递推数列， 但可以猜想该数列是整式递推数列。利用高斯消元或扩展 $BM$，可得……

好了那估摸着正解就 $\text{OEIS}$ 吧

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int MAXN = 4e05 + 10;

const int MAX = 4e05;

int T; LL MOD;

inline LL power (LL x, int p) {
	LL cnt = 1;
	while (p) {
		if (p & 1) cnt = cnt * x % MOD;
		x = x * x % MOD;
		p >>= 1;
	}
	return cnt;
}

LL vis[MAXN];

LL a[MAXN]= {0};
LL fact[MAXN]= {0}, invfact[MAXN]= {0};
inline LL C (int n, int m) {
	if (n < m) return 0;
	return fact[n] * invfact[m] % MOD * invfact[n - m] % MOD;
}
void init () {
	fact[0] = invfact[0] = 1;
	for (int i = 1; i <= MAX; i ++) fact[i] = fact[i - 1] * i % MOD;
	invfact[MAX] = power (fact[MAX], MOD - 2);
	for (int i = MAX - 1; i >= 1; i --) invfact[i] = invfact[i + 1] * (i + 1) % MOD;
	a[0] = 1, a[1] = 3;
	for (int n = 1; n < (MAX >> 1); n ++) {
		LL add = (10ll * n % MOD * n % MOD + 10ll * n % MOD + 3) % MOD * a[n] % MOD;
		add = (add - 9ll * n % MOD * n % MOD * a[n - 1] % MOD + MOD) % MOD;
		a[n + 1] = add * power (1ll * (n + 1) * (n + 1) % MOD, MOD - 2) % MOD;
	}
}
/* (n+1)^2 a(n+1) = (10*n^2+10*n+3) * a(n) - 9*n^2 * a(n-1). */

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	memset (vis, - 1, sizeof (vis));
	T = getnum (); cin >> MOD;
	init ();
	for (int Case = 1; Case <= T; Case ++) {
		int n = getnum ();
		if (~ vis[n]) { cout << vis[n] << endl; continue; }
		LL ans = ((18ll * n + 45) % MOD * a[n]- (7ll + 2 * n) % MOD * a[n + 1] % MOD + MOD) % MOD;
		ans = ans * power (6ll * (n + 2) % MOD * (n + 2) % MOD, MOD - 2) % MOD;
		cout << ans << endl;
		vis[n] = ans;
	}

	return 0;
}

/*	
a(n) = 2 * Sum_{k=0..n} binomial(2*k, k) * (binomial(n, k))^2 * 
	  (3*k^2 + 2*k+1 - n - 2*k*n)/((k+1)^2 * (k+2) * (n-k+1)).
*/

Problem B：排列

题面

题解

第一次订正的交互题

大概记录一下交互题咋玩

  • 编译可以通过在电脑 $\text{path}​$ 中添加编译器路径，通过 $\text{cmd}​$ $\text{cd}​$ 到指定文件夹，输入题目给定编译语句编译，再运行 $\text{xxx.exe}​$ 运行，输入数据，最后在 $\text{cmd}​$ 中返回答案正确性及询问次数
  • 编译运行简易方法，可直接加入头文件 #include "grader.cpp"，此时可直接编译运行

回到正题

随机一个排列 $q​$，再随机地改变 $q​$ 中的 $S​$ 个元素，使这 $S​$ 个元素重新错排，设得到排列 $r​$，改变了位置 $a_1, a_2, …, a_S​$，那么有一定概率满足所有 $|p_{a_i} - q_{a_i}|​$ 构成的数的集合 $A​$ 与 $|p_{a_i} - r_{a_i}|​$ 构成的数的集合 $B​$ 完全没有交集，此时取 $S = \frac{\sqrt n}{2}​$ 可以使该概率比较大（证明咱也不会）

假定此时满足 $|A \cup B| = 2S​$，即满足两个集合无交，那么我们由 $A​$ 可以对每个 $q_{a_i}​$ 得到最多 $2 \times S​$ 个它可以匹配的位置，同样对 $B​$ 与 $r_{a_i}​$ 也是一样，这实际上就变成了一个二分图，为了方便，将其反过来记，即每次由 $A​$ 得到每个 $q_{a_i}​$ 不可能匹配到的位置，然后在二分图上将这些边删去，那么最终找到答案的情况等价于二分图匹配具有唯一性，这个用网络流和 $Tarjan​$ 维护一下就好了

进一步优化，随机几次之后可能一些位置已经确定了唯一匹配性，那么每次随机选 $S$ 个元素的时候优先选还未成功匹配的位置

再者，在 $n$ 比较小时可能很难随到答案，就可以在开头时随十个 $q$，然后每次随机使用其中一个 $q$，这样可以比较大的概率避免这样的情况

代码

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
220
221
222
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <ctime>
#include "perm.h"
// #include "grader.cpp"

using namespace std;

const int INF = 0x7fffffff;

namespace graph {
	const int MAXN = 800 + 10;
	const int MAXM = MAXN * MAXN;

	struct LFS { int to, next; } ;
	LFS Link[MAXM];
	int Head[MAXN], size = 0;
	void Insert (int u, int v) {
		Link[++ size].to = v;
		Link[size].next = Head[u];

		Head[u] = size;
	}

	int N;
	int dfn[MAXN], low[MAXN], bel[MAXN], ord = 0, bcc = 0;
	void init () {
		memset (Head, 0, sizeof (Head)), size = ord = bcc = 0;
		for (int i = 1; i <= N; i ++) dfn[i] = low[i] = bel[i] = 0;
	}
	int stack[MAXN], top = 0; bool insta[MAXN]= {false};
	void Tarjan (int u) {
		dfn[u] = low[u] = ++ ord;
		stack[++ top] = u, insta[u] = true;
		for (int i = Head[u]; i; i = Link[i].next) {
			int v = Link[i].to;
			if (! dfn[v]) {
				Tarjan (v);
				low[u] = min (low[u], low[v]);
			}
			else if (insta[v]) low[u] = min (low[u], dfn[v]);
		}
		if (low[u] == dfn[u]) {
			bcc ++; int tp;
			do {
				tp = stack[top --];
				bel[tp] = bcc, insta[tp] = false;
			} while (tp != u);
		}
	}
	void work () {
		for (int i = 1; i <= N; i ++) if (! dfn[i]) Tarjan (i);
	}
} ;
bool con[1000]= {false};
namespace net {
	const int MAXN = 800 + 10;
	const int MAXM = MAXN * MAXN;

	struct LFS { int to, cap, next; } ;
	LFS Link[MAXM];
	int Head[MAXN]= {0}, size;
	void Insert (int u, int v, int cap) {
		Link[++ size].to = v;
		Link[size].cap = cap;
		Link[size].next = Head[u];

		Head[u] = size;
	}
	void addedge (int u, int v, int cap) {
		Insert (u, v, cap), Insert (v, u, 0);
	}

	int n, N, S, T;
	void init () { memset (Head, 0, sizeof (Head)), size = 1; }
	queue<int> que; int depth[MAXN];
	bool BFS () {
		while (! que.empty()) que.pop();
		memset (depth, 0, sizeof (depth));
		depth[S] = 1, que.push(S);
		while (! que.empty()) {
			int u = que.front(); que.pop();
			for (int i = Head[u]; i; i = Link[i].next) {
				int v = Link[i].to, cap = Link[i].cap;
				if (depth[v] || ! cap) continue;
				depth[v] = depth[u] + 1;
				if (v == T) return true;
				que.push(v);
			}
		}
		return false;
	}
	int cur[MAXM];
	int Dinic (int u, int flow) {
		if (u == T) return flow;
		int rest = flow;
		for (int& i = cur[u]; i && rest; i = Link[i].next) {
			int v = Link[i].to, cap = Link[i].cap;
			if (depth[v] != depth[u] + 1 || ! cap) continue;
			int k = Dinic (v, min (rest, cap));
			if (! k) depth[v] = - 1;
			Link[i].cap -= k, Link[i ^ 1].cap += k;
			rest -= k;
		}
		return flow - rest;
	}
	int maxflow () {
		int ret = 0;
		while (BFS ()) {
			for (int i = 1; i <= N; i ++) cur[i] = Head[i];
			ret += Dinic (S, INF);
		}
		return ret;
	}
	int match[MAXN];
	bool check () {
		graph::N = 2 * n, graph::init ();
		for (int i = 1; i <= n; i ++)
			for (int j = Head[i]; j; j = Link[j].next) {
				int v = Link[j].to, cap = Link[j].cap;
				if (! cap) graph::Insert (i, match[i] = v);
				else graph::Insert (v, i);
			}
		graph::work ();
		bool suc = true;
		for (int i = 1; i <= n; i ++) {
			if (graph::bel[i] == graph::bel[match[i]]) suc = false;
			else con[i] = true;
		}
		return suc;
	}
} ;

const int MAXN = 400 + 10;

bool ext[MAXN][MAXN];
int N, S, B = 10;
vector<int> trans (vector<int> p) {
	vector<int> ret; ret.resize(N);
	for (int i = 0; i < N; i ++) ret[p[i] - 1] = i + 1;
	return ret;
}
vector<int> ask (vector<int> p) { return query (trans (p)); }
vector<int> q[11], r, rkc, rkd, rk;
vector<int> qq[11], qr, f1, f2;
vector<int> ret;
int cnt1[MAXN]= {0}, cnt2[MAXN]= {0};
void build () {
	net::init (), net::n = N, net::N = 2 * N + 2;
	net::S = 2 * N + 1, net::T = 2 * N + 2;
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= N; j ++)
			if (ext[i][j]) net::addedge (i, j + N, 1);
	for (int i = 1; i <= N; i ++) net::addedge (net::S, i, 1);
	for (int i = 1; i <= N; i ++) net::addedge (i + N, net::T, 1);
}

int vis1[MAXN], vis2[MAXN];
bool work () {
	int p = rand () % B + 1; rkc.clear();
	for (int i = 0; i < N; i ++) if (! con[i + 1]) rkc.push_back(i);
	random_shuffle (rkc.begin(), rkc.end());
	rkd.clear(); for (int i = 0; i < N; i ++) if (con[i + 1]) rkd.push_back(i);
	random_shuffle (rkd.begin(), rkd.end());
	for (int i = 0; i < (int) rkd.size(); i ++) rkc.push_back(rkd[i]);
	rk.clear(); for (int i = 0; i < S; i ++) rk.push_back(rkc[i]);
	for (int i = 1; i < S; i ++) swap (rk[i], rk[rand () % i]);
	r.resize(N); for (int i = 0; i < N; i ++) r[i] = q[p][i];
	for (int i = 0; i < S; i ++) r[rkc[i]] = q[p][rk[i]]; qr = ask (r);
	for (int i = 0; i < N; i ++) cnt1[i] = cnt2[i] = 0;
	for (int i = 0; i < N; i ++) cnt1[qq[p][i]] ++, cnt2[qr[i]] ++;
	f1.clear(), f2.clear();
	for (int i = 0; i < N; i ++) {
		while (cnt1[i] > cnt2[i]) f1.push_back(i), cnt1[i] --;
		while (cnt1[i] < cnt2[i]) f2.push_back(i), cnt1[i] ++;
	}
	if ((int) f1.size() != S || (int) f2.size() != S) return false;
	for (int i = 0; i < S; i ++) {
		int x1 = q[p][rkc[i]], x2 = r[rkc[i]];
		for (int i = 1; i <= N; i ++) vis1[i] = vis2[i] = 0;
		for (int j = 0; j < S; j ++) {
			if (x1 - f1[j] >= 1) vis1[x1 - f1[j]] = 1;
			if (x1 + f1[j] <= N) vis1[x1 + f1[j]] = 1;
			if (x2 - f2[j] >= 1) vis2[x2 - f2[j]] = 1;
			if (x2 + f2[j] <= N) vis2[x2 + f2[j]] = 1;
		}
		for (int j = 1; j <= N; j ++)
			if (! vis1[j] || ! vis2[j]) ext[rkc[i] + 1][j] = false;
	}
	build (); int flow = net::maxflow ();
	if (flow < N) return false;
	if (! net::check ()) return false;
	for (int i = 1; i <= N; i ++) ret[net::match[i] - N - 1] = i;
	return true;
}
vector<int> guess (int pn){
	N = pn;
	if (N <= 3) {
		for (int i = 1; i <= N; i ++) ret.push_back(i);
		while (query (ret).back()) next_permutation (ret.begin(), ret.end());
		return ret;
	}
	srand (time (NULL));
	S = sqrt (N) / 2; S = max (S, 2);
	for (int i = 1; i <= B; i ++) {
		for (int j = 1; j <= N; j ++) q[i].push_back(j);
		random_shuffle(q[i].begin(), q[i].end());
		qq[i] = ask (q[i]);
	}
	for (int i = 1; i <= N; i ++)
		for (int j = 1; j <= N; j ++)
			ext[i][j] = true;
	ret.resize(N); while (! work ());
	return ret;
}

// g++ grader.cpp perm.cpp -o perm -O2 -std=c++11

Problem C：塔