标算是状压dp+打表,前者时间复杂度为$o(n^{2}2^{n})$,并通过打表做到$o(1)$
参考loj2265中关于杨表的相关知识,不难发现答案即$\frac{\sum_{a\vdash n}a_{1}f_{a}^{2}}{n!}$
记$P(n)$为$a\vdash n$的方案数,后者$f_{a}$可以$o(n)$计算,总复杂度即$o(nP(n))$
不难发现$P(n)$即为A000041,有$P(28)=3718$(甚至$P(60)\le 10^{6}$),显然可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 30 4 #define mod 998244353 5 #define ll long long 6 vector<int>v; 7 int n,ans,inv[N]; 8 void calc(int k,int lst){ 9 if (!k){ 10 int s=1; 11 for(int i=0;i<v.size();i++) 12 for(int j=1;j<=v[i];j++){ 13 int tot=v[i]-j; 14 for(int k=i;k<v.size();k++) 15 if (j<=v[k])tot++; 16 s=(ll)s*inv[tot]%mod; 17 } 18 for(int i=1;i<=n;i++)s=(ll)s*i%mod; 19 s=(ll)v[0]*s%mod*s%mod; 20 ans=(ans+s)%mod; 21 return; 22 } 23 for(int i=min(k,lst);i;i--){ 24 v.push_back(i); 25 calc(k-i,i); 26 v.pop_back(); 27 } 28 } 29 int main(){ 30 inv[0]=inv[1]=1; 31 for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod; 32 scanf("%d",&n); 33 calc(n,n); 34 for(int i=1;i<=n;i++)ans=(ll)ans*inv[i]%mod; 35 printf("%d\n",ans); 36 return 0; 37 }