一个排列的权值就是所有环长的 \operatorname{lcm}，注意到 n=50 的整数拆分方案不多，那么不同的 \operatorname{lcm} 的数量更少，考虑将 \operatorname{lcm} 加入 dp 状态中。
但是这样子会算重，原因在于先取 $1$ 再取 $2$ 和先取 $2$ 再取 $1$ 是一样的。解决方法是每次钦定选出的 $k$ 个数中必须包含剩下的数的编号的最小值，所以正确的系数为 $\binom {n-i-1}{k-1}(k-1)!$。
该做法可以在 1s 内跑出 $n=110$ 的结果。
```cpp
#include <set>
#include <map>
#include <queue>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cassert>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define fi first
#define se second
#define ep emplace
#define MISAKA main
#define ll long long
#define eb emplace_back
#define pii pair<int,int>
#define rg(x) x.begin(),x.end()
#define pc(x) __builtin_popcount(x)
#define mems(a,x) memset(a,x,sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define _rep(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define FIO(FILE) freopen(FILE".in","r",stdin),freopen(FILE".out","w",stdout)
using namespace std;
bool __st;
inline int read(){
char c=getchar();int f=1,x=0;
for(;c<48||c>57;c=getchar())if(c=='-') f=-1;
for(;47<c&&c<58;c=getchar()) x=(x<<3)+(x<<1)+(c^48);
return x*f;
}
const int N=150,mod=998244353;
int n,K,ans,c[N][N],fac[N];
unordered_map<ll,int> f[N];
ll lcm(ll a,ll b){return a/__gcd(a,b)*b;}
void add(int &x,int y){((x+=y)>=mod)&&(x-=mod);}
ll qp(ll a,ll b){ll r=1;for(;b;b>>=1,a=a*a%mod)if(b&1)r=r*a%mod;return r;}
void misaka(){
n=read(),K=read();
rep(i,0,n){c[i][0]=1;rep(j,1,i)c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;}
f[0][1]=fac[0]=1;
rep(i,1,n) fac[i]=1ll*fac[i-1]*i%mod;
rep(i,0,n-1)for(auto [a,b]:f[i])
rep(j,1,n-i) add(f[i+j][lcm(a,j)],1ll*b*c[n-i-1][j-1]%mod*fac[j-1]%mod);
for(auto [a,b]:f[n]) add(ans,qp(a%mod,K)*b%mod);
printf("%d",ans);
}
bool __ed;
signed MISAKA(){
#ifdef LOCAL_MSK
atexit([](){
debug("\n%.3lfs ",(double)clock()/CLOCKS_PER_SEC);
debug("%.3lfMB\n",abs(&__st-&__ed)/1024./1024);});
#endif
int T=1;
while(T--) misaka();
return 0;
}
```