题意：求$n$个数组成的排列变为升序有多少种不同的步数
步数就是循环长度的$lcm$.....
那么就是求$n$划分成一些数几种不同的$lcm$咯
然后我太弱了这种$DP$都想不出来....
通过枚举每个质因子的指数来求$lcm$
$d[i][j]$表示前$i$个质因子当前和为$j$的方案数
转移枚举质因子的指数
但这样我们忽略了可以划分出$1$，所以统计答案时枚举$j$
或者我们直接初始化$d[0][i]=1$
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n;
int p[N];
bool notp[N];
void sieve(int n){
for(int i=;i<=n;i++){
if(!notp[i]) p[++p[]]=i;
for(int j=;j<=p[]&&i*p[j]<=n;j++){
notp[i*p[j]]=;
if(i%p[j]==) break;
}
}
}
ll f[N][N];
void dp(){
f[][]=;
for(int i=;i<=p[];i++)
for(int j=;j<=n;j++){
f[i][j]=f[i-][j];
for(int k=p[i];k<=j;k*=p[i])
f[i][j]+=f[i-][j-k];
}
ll ans=;
for(int i=;i<=n;i++) ans+=f[p[]][i];
printf("%lld",ans);
}
int main(){
freopen("in","r",stdin);
n=read();
sieve(n);
dp();
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return x*f;
}
int n;
int p[N];
bool notp[N];
void sieve(int n){
for(int i=;i<=n;i++){
if(!notp[i]) p[++p[]]=i;
for(int j=;j<=p[]&&i*p[j]<=n;j++){
notp[i*p[j]]=;
if(i%p[j]==) break;
}
}
}
ll f[N][N];
void dp(){
f[][]=;
for(int i=;i<=n;i++) f[][i]=;
for(int i=;i<=p[];i++)
for(int j=;j<=n;j++){
f[i][j]=f[i-][j];
for(int k=p[i];k<=j;k*=p[i])
f[i][j]+=f[i-][j-k];
}
printf("%lld",f[p[]][n]);
}
int main(){
freopen("in","r",stdin);
n=read();
sieve(n);
dp();
}