【洛谷P4161】游戏

题目

题目链接：https://www.luogu.com.cn/problem/P4161
给出 \(n\)，令 \(nxt_x\) 表示 \(x\) 对应的数字。一开始有一个 \(1\sim n\) 的递增排列，每次数字 \(x\) 会变成 \(nxt_x\)。如此反复直到该序列再次变回 \(1\sim n\) 的递增排列。设循环了 \(k\) 次，你需要求出在 \(nxt\) 各不相同的情况下，\(k\) 有多少种取值。也就是说 \(nxt\) 有 \(n!\) 种方案，对于每一种方案都能求得一个 \(k\)。
\(n\leq 1000\)。

思路

我们把每一个数字看做一个点，点 \(x\) 向 \(nxt_x\) 连一条有向边。显然我们得到了若干个环，假设有 \(m\) 个环。
设环的大小（边的数量）分别为 \(a_1,a_2,...,a_m\)，那么显然对于这一组 \(nxt\)，循环 \(\operatorname{lcm}(a_1,a_2,...,a_m)\) 次就回到了初始状态。
也就是说，我们要求

\[\sum^{+\infty}_{i=1}[\exists(\operatorname{lcm}(a_1,a_2,...a_m)=i\texttt{ 且 }\sum^{m}_{j=1}a_j=n)] \]

考虑一个数 \(p\) 能否被表达出来。将 \(p\) 分解质因数得 \(p=k_1^{c_1}·k_2^{c_2}·...·k_m^{c_m}\)，如果 \(\sum^{m}_{i=1}k_i^{c_i}\leq n\)，那么 \(p\) 就可以被表达出来。因为这样的话，我们就可以从 \(n\) 个点中分别选出 \(k_1^{c_1},k_2^{c_2}...k_m^{c_m}\) 个点来围成环，剩余的点全部自环即可。
考虑到 \(n\) 较小，所以我们可以枚举 \(n\)，假设有 \(n\) 个点拿出来连成环，剩余的点自环，对于每一个 \(n\) 分别计算即可。因为枚举的质数两两互质，所以 \(\operatorname{lcm}\) 就是这些质数的乘积。
所以答案就是

\[\sum^{n}_{i=0}(\texttt{选出若干质数的任意次幂和为 i 的方案数}) \]

这就是一个背包。
时间复杂度 \(O(n^2)\)。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N=1010; 
int n,m;
ll ans,f[N];

int main()
{
	scanf("%d",&n);
	f[0]=1;
	for (int i=2;i<=n;i++)
	{
		bool flag=1;
		for (int j=2;j*j<=i;j++)
			if (i%j==0) flag=0;
		if (!flag) continue;
		for (int k=n;k>=1;k--)
			for (int j=i;j<=k;j*=i)
				f[k]+=f[k-j];
	}
	for (int i=0;i<=n;i++)
		ans+=f[i];
	printf("%lld",ans);
	return 0;
}