题目概述

ACL Beginner Contest F

解题报告

直接求不太可做，我们考虑容斥，用总方案数减去至少一组相同的方案数加上至少两组相同的方案数……

$2n$ 个元素两两组合的方案数为 $f_{2n}=\prod_{i=1}^{n}(2i-1)$ ，现在的问题是如何求出至少 $i$ 组相同的方案数。

假设有 $cnt_i$ 个高度为 $i$ 的，那么 $i$ 最多提供 $\lfloor{cnt_i\over 2}\rfloor$ 组相同的，提供 $x$ 组相同的方案数为 ${cnt_i\choose 2x}f_{2x}$ 。

然后就不难发现这是个背包（生成函数）问题了，可以利用分治NTT快速求解。

示例程序

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long LL;typedef vector<int> Poly;
const int maxn=100000,maxh=100000,maxt=1<<16,MOD=998244353;

int n,cnt[maxh+5],f[maxn+5],fac[maxn+5],INV[maxn+5],ans;
int rev[maxt+5],pw[2][maxt+5];
int m;Poly p[maxn+5],F;

#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
void Make(int n){
    INV[1]=1;for (int i=2;i<=n;i++) INV[i]=MUL(MOD-MOD/i,INV[MOD%i]);
    INV[0]=fac[0]=1;for (int i=1;i<=n;i++) INV[i]=MUL(INV[i-1],INV[i]),fac[i]=MUL(fac[i-1],i);
}
#define C(x,y) ((x)<(y)?0:MUL(fac[x],MUL(INV[y],INV[(x)-(y)])))
int Pow(int w,int b) {int s=1;while (b) {if (b&1) s=MUL(s,w);w=MUL(w,w);b>>=1;}return s;}
void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=MUL(g,gn))
                x=a[i+j],y=MUL(g,a[i+j+k]),a[i+j]=ADD(x,y),a[i+j+k]=ADD(x,MOD-y);
    }
    if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=MUL(a[i],INV);
}
inline Poly operator * (const Poly &a,const Poly &b){
    static int A[maxt+5],B[maxt+5],C[maxt+5];static Poly c;
    int n=a.size(),m=b.size(),t;for (t=1;t<n+m-1;t<<=1);
    for (int i=0;i<n;i++) A[i]=a[i];for (int i=0;i<m;i++) B[i]=b[i];
    for (int i=n;i<t;i++) A[i]=0;for (int i=m;i<t;i++) B[i]=0;
    Pre(t);NTT(A,t,1);NTT(B,t,1);
    for (int i=0;i<t;i++) C[i]=MUL(A[i],B[i]);NTT(C,t,-1);
    c.resize(n+m-1);for (int i=0;i<n+m-1;i++) c[i]=C[i];return c;
}
Poly Solve(int L,int R) {if (L==R) return p[L];int mid=L+(R-L>>1);return Solve(L,mid)*Solve(mid+1,R);}
int main(){
    freopen("F.in","r",stdin);freopen("F.out","w",stdout);
    scanf("%d",&n);n<<=1;for (int i=1,x;i<=n;i++) scanf("%d",&x),cnt[x]++;
    Make(n);f[0]=1;for (int i=2;i<=n;i+=2) f[i]=MUL(f[i-2],i-1);
    for (int i=1;i<=maxh;i++)
        if (cnt[i]>1){
            m++;p[m].push_back(1);
            for (int j=2;j<=cnt[i];j+=2)
                p[m].push_back(MUL(C(cnt[i],j),f[j]));
        }
    ans=f[n];if (m) F=Solve(1,m); else F.push_back(1);
    for (int i=1,si=F.size();i<si;i++)
        i&1?ans=ADD(ans,MOD-MUL(f[n-(i<<1)],F[i])):ans=ADD(ans,MUL(f[n-(i<<1)],F[i]));
    printf("%d\n",ans);return 0;
}