Alien 的排列题解

Description

求出有多少 \(2\sim n+1\) 的排列 \(\{P_{n}\}\)，使得对于所有 \(1\leq i\leq n\) 有 \(i|P_{i}\)。

对于 \(30\%\) 的数据 \(n\leq 10\)。

对于 \(90\%\) 的数据 \(n\leq 3000\)。

对于 \(100\%\) 的数据 \(n\leq 10^9\)。

Solution

如果把 \(n+1\) 固定在第 \(1\) 个位置的话，只有一种排列，证明显然。

考虑将 \(n+1\) 与其他数交换。设把它与 \(k\) 交换，那么需要满足 \(k|n\land k\neq n\)。我们发现，交换后 \(k\) 跑到第一个位置了，而 \(k\) 显然不可能与 \(\geq k\) 的数交换，那么问题就转换成了一个 \(2\sim k\) 的排列的问题了。

设 \(f_{n}\) 为 \(2\sim n\) 的合法排列方案数，则由上文得 \(f_{n}=\sum\limits_{d|n\land d\neq n}f_{d}\)，边界是 \(f_{1}=1\)。

使用朴素 dp 可以做到 \(\mathcal{O}(n^2)\) 或 \(\mathcal{O}(n\sqrt{n})\)。可以使用记忆化搜索，由于搜索树像杜教筛，所以时间复杂度应该是 \(\mathcal{O}(n^{\frac{3}{4}})\)。

Code

#include <bits/stdc++.h>
using namespace std;
namespace Milkcat {
	typedef long long LL;
	const int N = 1e6 + 5;
	LL n;
	unordered_map<LL, LL> f;
	LL dfs(LL n) {
		if (f[n]) return f[n];
		for (int i = 1; i * i <= n; i ++) {
			if (n % i) continue;
			f[n] += dfs(i);
			if (i * i != n && i != 1) f[n] += dfs(n / i);
		}
		return f[n];
	}
	int main() {
		cin >> n, n ++, f[1] = 1;
		cout << dfs(n) << '\n';
		return 0;
	}
}
int main() {
    int T = 1;
    while (T --) Milkcat::main();
    return 0;
}