Luogu

分析

显然一个置换的步数就是它所有环长的 $\operatorname{lcm}$。于是问题变为求有多少个数 $n$ 的某个拆分中所有数的 $\operatorname{lcm}$。

考虑 DP。设 $dp_{i,j}$ 表示 $i$ 拆成若干个最大质因子 $\leq p_j$ 且不为 $1$ 的数时的答案，不难得到转移
$$
dp_{i,j}=dp_{i,j-1}+\sum_{p_j\!^k\leq i}dp_{i-p_j\!^k,j-1}
$$
答案即为 $1+\sum_{i=1}^n dp_{n,|\mathrm{P}|}$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=10000+10,M=1250;

int n,mod;

int p[M],v[N],cnt=0;
void sieve(int n) {
    for (int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i;
        for (int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }
}

int dp[N][M];

int main() {
    n=read(),mod=read(); sieve(n);
    for (int i=0;i<=cnt;++i) dp[0][i]=1;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=cnt;++j) {
            dp[i][j]=dp[i][j-1];
            for (ll k=p[j];k<=i;k*=p[j])
                dp[i][j]=(dp[i][j]+dp[i-k][j-1]*k)%mod;
        }
    int ans=1;
    for (int i=1;i<=n;++i) ans=(ans+dp[i][cnt])%mod;
    printf("%d\n",ans);
    return 0;
}