题解：CF1726E Almost Perfect

flower1 · 2025-12-04 11:07:01 · 题解

题解

给出一个容易理解的 dp 做法。

由于题目限制非常强，因此考虑推导合法排列的形态。

手玩发现合法的排列一定是由自环，二元环和四元环组成，且四元环对顶点相邻。

设 f(n) 表示长度为 n 的排列只考虑自环和二元环的方案数。

转移：f(n)=f(n-1)+(n-1) \times f(n-2)。

设 g(x) 表示长度为 4n 的排列只考虑四元环的方案数，每次加入一个相邻的二元组，并从前面 2n-1 个二元组选一个连边，且连边方式有两种。

转移：g(n)=2 \times (2n-1) \times g(n-1)。

计算答案时枚举四元环数量，可以使用插板法计算。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5,M=3e5,mo=998244353;
int T,n,fac[N],inv[N],f[N],g[N],ans;
int read(){
    int k=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')
        ch=getchar();
    while(ch>='0'&&ch<='9')
        k=k*10+ch-'0',ch=getchar();
    return k;
}
int qpow(int x,int y){
    int res=1;
    while(y){
        if(y&1)
            res=res*x%mo;
        x=x*x%mo;
        y=y>>1;
    }
    return res;
}
int C(int n,int m){
    if(n<0||n<m) return 0;
    return fac[n]*inv[m]%mo*inv[n-m]%mo;
}
signed main(){
    T=read();
    fac[0]=1,inv[0]=1;
    for(int i=1;i<=M;i++)
        fac[i]=fac[i-1]*i%mo;
    inv[M]=qpow(fac[M],mo-2);
    for(int i=M-1;i>=1;i--)
        inv[i]=inv[i+1]*(i+1)%mo;
    f[0]=1,f[1]=1;
    for(int i=2;i<=M;i++)
        f[i]=(f[i-1]+f[i-2]*(i-1))%mo;
    g[0]=1;
    for(int i=1;i<=M/4;i++)
        g[i]=(2*(2*i-1)*g[i-1])%mo;
    while(T--){
        n=read();
        ans=0;
        for(int i=0;i*4<=n;i++)
            ans=(ans+g[i]*f[n-4*i]%mo*C(n-2*i,2*i))%mo;
        printf("%lld\n",ans);
    }
    return 0;
}