CF1561

Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))

D - Up the Strip

题意

给出一个数字 $n$ 表示初始的数字，你可以对当前的数字（比如说是 $x$）做若干次变化，变化包含下列两种：

1. 选择一个数字 $y\in[1,x-1]$，将现在的数字 $x$ 变为 $y-x$。

2. 选择一个数字 $z\in[2,x]$，将现在的数字 $x$ 变为 $\left\lfloor\frac{x}{z}\right\rfloor$。

求将初始数字 $n$ 变为 $1$ 的不同的操作有多少种？

答案对 $m$ 取模，每次会给出 $m$。

数据范围：$2\leqslant n\leqslant 4\times 10^6, 10^8 < m < 10^9$。

思路

求不同操作的个数，可以用dp完成，令 $f(n)$ 为将数字 $n$ 转变为 $1$ 的不同操作个数，则转移为：

$$f(n)=\sum_{i=2}^nf(\left\lfloor\frac{n}{i}\right\rfloor)+\sum_{i=1}^{n-1}f(i)$$

右侧第一个式子可以使用数论分块在 $O(\sqrt n)$ 内完成，然后从1到n计算对应的 $f(x)$，右侧用前缀和即可 $O(1)$ 求出。

总复杂度：$O(N\sqrt N)$，于是 Up the Strip (simplified version) 就可以通过了。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
const int N = 2e5 + 10;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, sum = 0;
	cin >> n >> m;
	vi f(n+1);
	f[1] = 1;
	sum = 1;
	for (int i = 2; i <= n; i++) {
		for (int l = 2, r; l <= i; l = r + 1) {
			r = i / (i / l);
			f[i] = (f[i] + f[i/l] * (r - l + 1) % m) % m;
		}
		f[i] = (f[i] + sum) % m;
		sum = (sum + f[i]) % m;
	}
	cout << f[n] << '\n';
	return 0;
}

如果要通过 $n=4\times10^6$ 的数据，时间复杂度不能超过 $O(NlogN)$，空间复杂度不能超过 $O(N)$（128Mb）。

考虑 $f$ 中相邻两项之间的关系，下面列式观察：

$$\begin{aligned} f(n)&=\sum_{i=2}^nf(\left\lfloor\frac{n}{i}\right\rfloor)+\sum_{i=1}^{n-1}f(i)\\ &=\sum_{i=2}^{n-1}f(\left\lfloor\frac{n}{i}\right\rfloor)+\sum_{i=1}^{n-2}f(i)+f(1)+f(n-1)\\ f(n-1)&=\sum_{i=2}^{n-1}f(\left\lfloor\frac{n-1}{i}\right\rfloor)+\sum_{i=1}^{n-2}f(i) \end{aligned}$$

不难发现 $f(n)$ 和 $f(n-1)$ 中第一项只有分子发生了变化，从 $n-1$ 变为 $n$。

那么只需要考虑，分母在何时会发生变化即可。

当 $i=3$ 时，那么只有当 $n=3,6,9,\cdots,3k$ 时，$\left\lfloor\frac{n}{3}\right\rfloor$ 和 $\left\lfloor\frac{n-1}{3}\right\rfloor$ 才会发生变化
而且只是从 $\frac{n-1}{3}=\frac{n}{3}-1$ 变为 $\frac{n}{3}$。

所以 $f(n)$ 从 $f(n-1)$ 的转移可以写成：

$$f(n)=2f(n-1)+f(1)-\sum_{k|n,k\geqslant 2}f(\frac{n}{k}-1)+\sum_{k|n,k\geqslant 2}f(\frac{n}{k})$$

由于 $\frac{n}{2}+\frac{n}{3}+\frac{n}{4}+\cdots+\frac{n}{n}=O(n\log n)$，所以如果我们直接预处理能整除 $n$ 的 $k$ 时，在空间上会爆掉的。

所以正确的做法有如下两种：

他们时空间复杂度都一样为：时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。

法一：

对每个 $n$ 求它所有的因数（需要先用筛法求出素数表，然后求 $n$ 对应的素因数，最后暴力枚举每个素数的个数）。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
//#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 4e6 + 10;
int num[N];
bool vis[N];
vi fac, prims;
vp prim;
void Euler(int n) {
	for (int i = 2; i <= n; i++) {
		if (!vis[i]) prims.pb(i);
		for (auto j : prims) {
			int t = i * j;
			if (t > n) break;
			vis[t] = 1;
			if (i % j == 0) break;
		}
	}
}
void dfs(int now, int mul) {
	if (now == prim.size()) {
		fac.pb(mul);
		return;
	}
	dfs(now+1, mul);
	for (int i = 0; i < prim[now].second; i++) {
		mul *= prim[now].first;
		dfs(now+1, mul);
	}
}
void makefac(int n) {
	fac.clear();
	prim.clear();
	for (auto i : prims) {
		if (i * i > n) break;
		if (n % i == 0) {
			int cnt = 0;
			while (n % i == 0) {
				cnt++;
				n /= i;
			}
			prim.pb({i, cnt});
		}
	}
	if (n != 1) prim.pb({n, 1});
	dfs(0, 1);
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, P;
	cin >> n >> P;
	Euler(n);
	cout << prims.size() << '\n';
	num[n] = 1;
	for (int i = n; i >= 3; i--) {
		num[i-1] = (num[i-1] + 2 * num[i] % P) % P;
		num[1] = (num[1] + num[i]) % P;
		makefac(i);
		for (auto j : fac) {
			if (j == 1 || j == i) continue;
			num[i/j] = (num[i/j] + num[i]) % P;
			num[i/j-1] = (num[i/j-1] - num[i] + P) % P;
		}
	}
	cout << (num[2] * 2 % P + num[1]) % P << '\n';
	return 0;
}

法二(更优美的做法）：

就是考虑倒序求解，从 $1\sim n$ 求解，考虑每个数 $f(k)$ 对 $2k, 3k, 4k, \ldots$ 的贡献。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 4e6 + 10;
int f[N];
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, P;
	cin >> n >> P;
	f[1] = 1;
	for (int i = 2; i <= n; i++ ) {
		f[i] = (f[i] + 2 * f[i-1] % P + (i != 2 ? f[1] : 0)) % P;
		for (int j = 2; j * i <= n; j++) {
			f[j*i] = ((f[j*i] + f[i]) % P - f[i-1] + P) % P;
		}
	}
	cout << f[n] << '\n';
	return 0;
}

E - Bottom-Tier Reversals

题意

给出 $1$ 到 $n$ 的排列， $a = [a_1, a_2, \ldots, a_n]$，其中 $n$ 为奇数。

你可以进行一次操作，每次操作可以选择当前序列的前 $k$ 项，$k$必须为任意的奇数，然后反转他们，也就是将 $a_i$ 和 $a_{k-i+1}$ 交换位置。

如果你可以在不超过 $\frac{5n}{2}$ 次操作后完成当前序列的排序，先输出反转的次数，再输出每次反转的长度。

如果不能则输出 $-1$。

数据范围：$3\leqslant n\leqslant 2021$。

思路

性质：如果每次反转的区间长度为奇数，那么反转元素的下标的奇偶性不发生变化，如 $[1, 4, 3, 2, 5]\rightarrow [5, 2, 3, 4, 1]$，奇偶性不变。

那么由于每次反转只能反转奇数长度，所以一定有 $a_i$ 与 $i$ 的奇偶性相同，也就是 $a_i\equiv i\pmod 2$。

下面用具体操作证明这是一个充要条件。

由于又限制了每次反转只能在开头，开头位置无法改变，但末尾位置如果已经对应好了，则可以改变，所以考虑当前的末尾元素是否满足条件：

• 若 $a_n=n, a_{n-1}=n-1$，则不需要交换，继续考虑 $n-2$。

• 若 $a_n\neq n$ 或 $a_{n-1}\neq n-1$，则考虑下面5次交换，使得 $a_n=n, a_{n-1}=n-1$：

1. 设 $a_k=n$（注：$k$ 为奇数），反转 $[1,\ldots, k]$。

2. 设 $a_t = n-1$（注：$t$ 为偶数），反转 $[1,\ldots, t-1]$。

3. 设 $a_t=n-1$，反转 $[1, \ldots, t+1]$。

4. 反转 $[1, 2, 3]$。

5. 反转 $[1,\ldots, n]$。

上面步骤可以在草稿纸上模拟完成，便于理解。

于是总操作步骤一定不会超过 $\frac{5(n-1)}{2}$ 步。

只需模拟上述操作即可，时间复杂度 $O(n^2)$。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 998244353;
void solve() {
	int n;
	cin >> n;
	vi a(n+1), ans;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++) {
		if (a[i-1] % 2 == 0 && i % 2 == 1) {
			cout << -1 << '\n';
			return;
		}
	}
	for (int i = n; i >= 2; i -= 2) {
		if (a[i-1] == i && a[i-2] == i-1) continue;
		int tmp = find(a.begin(), a.end(), i) - a.begin() + 1;
		ans.pb(tmp);
		reverse(a.begin(), a.begin() + tmp);
		tmp = find(a.begin(), a.end(), i-1) - a.begin();
		ans.pb(tmp);
		reverse(a.begin(), a.begin() + tmp);
		ans.pb(tmp + 2);
		reverse(a.begin(), a.begin() + tmp + 2);
		ans.pb(3);
		reverse(a.begin(), a.begin() + 3);
		ans.pb(i);
		reverse(a.begin(), a.begin() + i);
	}
	cout << ans.size() << '\n';
	for (auto i : ans) cout << i << ' ';
	cout << '\n';
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}