[luogu4484]最长上升子序列

标算是状压dp+打表，前者时间复杂度为$o(n^{2}2^{n})$，并通过打表做到$o(1)$

参考loj2265中关于杨表的相关知识，不难发现答案即$frac{sum_{avdash n}a_{1}f_{a}^{2}}{n!}$

记$P(n)$为$avdash n$的方案数，后者$f_{a}$可以$o(n)$计算，总复杂度即$o(nP(n))$

不难发现$P(n)$即为A000041，有$P(28)=3718$（甚至$P(60)le 10^{6}$），显然可以通过

#include<bits/stdc++.h>
using namespace std;
#define N 30
#define mod 998244353
#define ll long long
vector<int>v;
int n,ans,inv[N];
void calc(int k,int lst){
    if (!k){
        int s=1;
        for(int i=0;i<v.size();i++)
            for(int j=1;j<=v[i];j++){
                int tot=v[i]-j;
                for(int k=i;k<v.size();k++)
                    if (j<=v[k])tot++;
                s=(ll)s*inv[tot]%mod;
            }
        for(int i=1;i<=n;i++)s=(ll)s*i%mod;
        s=(ll)v[0]*s%mod*s%mod;
        ans=(ans+s)%mod;
        return;
    }
    for(int i=min(k,lst);i;i--){
        v.push_back(i);
        calc(k-i,i);
        v.pop_back();
    }
}
int main(){
    inv[0]=inv[1]=1;
    for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
    scanf("%d",&n);
    calc(n,n);
    for(int i=1;i<=n;i++)ans=(ll)ans*inv[i]%mod;
    printf("%d
",ans);
    return 0;
}