[gym102538H]Horrible Cycles

将右侧$n$个点逆序排列，并将左侧的第$i$个点插入到右侧的$a_{i}$之前（左侧的点顺序任意）

换言之，一个左侧的点恰与（排列中）其之后所有右侧的点有边

对于一个简单环，仅保留（排列中）前$i$个点的以及之间的边，那么总会得到若干条链或一个环，而其中所有链的两个端点必然都在左侧（否则这个右侧的点与$i$之后的点均没有边，显然无法成环）

考虑dp，令$f_{i,j}$表示前$i$个点中选出$j$条链（要求两个端点均在左侧，交换两个端点看作不同方案）的方案数，显然转移即
$$
f_{i,j}=\begin{cases}f_{i-1,j}+f_{i-1,j-1}&i在左侧\\f_{i-1,j}+j(j+1)\cdot f_{i-1,j+1}&i在右侧\end{cases}
$$
考虑答案，枚举环上的最后一个点$i$（显然在右侧），对应的方案数即是在之前选一条链，也即$f_{i-1,1}$

当然，这并不准确，还需要去掉对应链仅有一个点（即是一个二元环）和每一条链交换端点的不同方案（显然对应的环是相同的），另外由于前者并不被算两次，因此应该先减去前者再除以2

时间复杂度为$o(n^{2})$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 10005

 4 #define mod 998244353

 5 #define ll long long

 6 int n,ans,a[N],v[N],f[N][N];

 7 int main(){

 8     scanf("%d",&n);

 9     for(int i=1;i<=n;i++){

10         scanf("%d",&a[i]);

11         ans=(ans-a[i]+mod)%mod;

12     }

13     sort(a+1,a+n+1);

14     for(int i=n,j=n;i;i--){

15         while ((j)&&(a[j]==i)){

16             v[++v[0]]=0;

17             j--;

18         }

19         v[++v[0]]=1;

20     }

21     f[0][0]=1;

22     for(int i=1;i<=v[0];i++){

23         for(int j=0;j<=i;j++){

24             f[i][j]=f[i-1][j];

25             if ((!v[i])&&(j))f[i][j]=(f[i][j]+f[i-1][j-1])%mod;

26             if (v[i])f[i][j]=(f[i][j]+(ll)j*(j+1)%mod*f[i-1][j+1])%mod;

27         }

28         if (v[i])ans=(ans+f[i-1][1])%mod;

29     }

30     ans=(ll)ans*(mod+1>>1)%mod;

31     printf("%d\n",ans);

32     return 0;

33 }

巴特西

[gym102538H]Horrible Cycles

最新文章

热门文章