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;
}