分析

简单分析可知
将置换关系转换为DAG
那么，我们关心的只是这个这个DAG中哪些环
并且最终的答案为
我们将每个环大小质因数分解

那么我们最终的答案为

因为
质数非常的少
这里我们想到了唯一分解定理
可知，对于多个幂（）的和如果不相等，那么他们的积一定不相等
所以我们可以考虑直接枚举质数以及质数的选取个数
那么
DP[j]+=DP[j-Prime[i]]
背包直接转移即可

代码

//P4161
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define Cl(X,Y) memset((X),(Y),sizeof(X))
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
#define Lowbit(X) (X & (-X))
#define INF 0x3f3f3f3f3f3f3f3f
#define Rson (X<<1|1)
#define Lson (X<<1)
using namespace std;
const LL MaxN=1e3+10;

LL Prime[MaxN],Cnt,Total;
bool Jud[MaxN];
LL DP[MaxN],Ans;

inline void File() {
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
}

inline void Init() {
    Jud[0]=Jud[1]=true;
    FOR(i,2,Total) {
        if(!Jud[i]) Prime[++Cnt]=i;
        for(LL j=1;j<=Cnt && Prime[j]*i<=Total;j++) {
            Jud[Prime[j]*i]=true;
            if(!(i%Prime[j])) break;
        }
    }
}

inline void Solve() {
    DP[0]=1;
    FOR(i,1,Cnt) 
        BOR(j,Total,Prime[i]) {
            LL Temp=Prime[i];
            while(Temp<=j) {
                DP[j]+=DP[j-Temp];
                Temp*=Prime[i];
            }
        }
}

signed main() {
    // File();
    ios::sync_with_stdio(false);
    cin>>Total;
    Init();
    Solve();
    FOR(i,1,Total) Ans+=DP[i];
    cout<<Ans+1<<endl;
    // fclose(stdin);
    // fclose(stdout);
    system("pause");
    return 0;
}