[luogu4484]最长上升子序列

标算是状压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 }

巴特西

[luogu4484]最长上升子序列

最新文章

热门文章