题解：CF1726E Almost Perfect

· · 题解

考虑对一个排列 p 取逆的实质：

故 p_i 与 p^{-1}_i 为某 p 中置换环 C 里距离为 2 的点。

对于某个环 C，若每个元素有两个距其距离为 2 的点，则环中极值一定不合法。据此分讨， p 中置换环 C 只能为一元、二元、四元环，且四元环需满足对顶点值相邻。

预处理 f_i 表示 i 个元素划分一、二元环的方案，枚举最后一个元素所处环，有转移：f_i=f_{i-1}+(i-1)f_{i-2}。

对于给定 n，不妨枚举四元环个数 t。注意到一个四元环可以看作两对相邻元素拼接，故总方案可看作先选取 2t 对相邻元素，再两两组合，且别忘记四元环正反定向不同，故有贡献系数 2。综上，可得：

Ans=\sum_{t}{{{n -2t} \choose {2t}}2^tf(n-4t){\prod_{j=0}^{2j+1 < 2t}{(2j+1)}}}

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=3e5+10,mod=998244353;
int T,n,f[N],pw[N],inv[N],fct[N],ofct[N],finv[N];
inline int C(int x,int y){return 1ll*fct[x]*finv[y]%mod*finv[x-y]%mod;}

inline void init()
{
    f[0]=pw[0]=fct[0]=inv[0]=finv[0]=1;
    f[1]=fct[1]=inv[1]=finv[1]=ofct[1]=1;pw[1]=2;
    for(int i=2;i<N;i++) 
    {
        pw[i]=pw[i-1]*2%mod;
        f[i]=(f[i-1]+1ll*(i-1)*f[i-2])%mod;
        fct[i]=1ll*fct[i-1]*i%mod;
        inv[i]=(mod-1ll*mod/i*inv[mod%i]%mod)%mod;
        finv[i]=1ll*finv[i-1]*inv[i]%mod;
        if(i&1) ofct[i]=1ll*ofct[i-2]*i%mod;
    }
}
inline int calc(int x){return x>0?ofct[x]:1;}
inline void solve()
{
    scanf("%d",&n);
    int ans=0;
    for(int t=0;t<=n/4;t++) ans=(ans+1ll*C(n-t*2,t*2)*calc(t*2-1)%mod*pw[t]%mod*f[n-t*4])%mod;
    printf("%d\n",ans);
}
int main()
{
    init();
    scanf("%d",&T);
    while(T--) solve();
    return 0;
}