具体思路

我们通过观察样例发现，$(1,2,3),(4,5),(6)$ 这几个数分别构成了循环，那么要想重新回到 $1,2 \dots n$ 这个排列，就需要这些循环的 $\operatorname{lcm}$ 次。

那么问题应该是选若干个和为 $n$ 的数，不同的 $\operatorname{lcm}$ 有多少个。

由于我们可以补 $1$，因此问题转化为选若干个和 $\le n$ 的数，不同的 $\operatorname{lcm}$ 有多少个。

我们考虑 $\operatorname{lcm}$ 如何得到的，显然是我们选出来的数的质因子的最高次幂。

于是我们线性筛出所有质数。

然后问题转化为背包问题。

设 $f_{i,j}$ 表示前 $i$ 个质数总和为 $j$ 的方案数。

滚动数组优化一下即可。

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e3+5;
int v[N],prime[N],pr;
LL f[N];
void init(int n){
	memset(v,0,sizeof(v));pr=0;
	for(int i=2;i<=n;i++){
		if(!v[i])prime[++pr]=i;
		for(int j=1;j<=pr&&i*prime[j]<=n;j++){
			v[i*prime[j]]=1;
			if(i%prime[j]==0){
				break;
			}
		}
	}
}
int main(){
	int n;scanf("%d",&n);
	init(n);
	f[0]=1;
	for(int i=1;i<=pr;i++){
		for(int j=n;j>=prime[i];j--){
			int tmp=prime[i];
			while(tmp<=j){
				f[j]+=f[j-tmp];
				tmp*=prime[i];
			}
		}
	}
	LL ans=0;
	for(int i=1;i<=n;i++){
		ans=ans+f[i];
	}
	printf("%lld",ans+1);
	return 0;
}