ACL Beginner Contest F - Heights and Pairs

有2n个人，身高分别为$h_i$​，求将他们两两配对，且每对人身高均不同的方案数(mod 998244353)$n\leq 5\times 10^4,h_i \leq 10^5$

设恰好有i对人身高不同的方案数为$g_i$​，至少有i对人身高不同的方案数为$f_i$恰好不好求，先求至少$f_i = \sum \limits_{j=i}^n \binom{j}{i}g_j$利用二项式反演$g_i = \sum \limits_{j=i}^n(-1)^{j-i}\binom{j}{i}f_j$答案即为$g_0$​单独考虑每种身高，若身高为h的有x个人，则将他们配成身高相同的i组人的方案数是$\dfrac{\sum\limits_{j=1}^i \binom{x-2*j+2}{2}}{i!}$这样对每种身高就可以写出一个OGF，全部乘起来后$x^i$的系数就是i组人配对的方案数，再考虑剩余的$2n-2i$个人，任意配对的方案数为$\dfrac{(2n-2i)!}{(n-i)!2^{(n-i)}}$​，两项相乘就是$f_i$​，再用上述式子即可得到$g_0$​其中n个OGF相乘利用分治NTT即可

在reverse一个空数组时会re，要注意

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5;
int n, h[N], cnt[N], d[N], sd[N];
int *f[N], buf[N<<5], *np(buf);
int fac[N], ifac[N], g[N];
const int mod = 998244353, G = 3;
int up, w[N], rev[N], inv[N];
int fpw(int a, int b)
{
  int ans = 1;
  while(b)
  {
    if(b&1) ans = 1ll*ans*a%mod;
    a = 1ll*a*a%mod;
    b >>= 1;
  }
  return ans;
}
void myassert(bool x)
{
  if(!x) while(true);
}
namespace poly
{
  void init(int n)
  {
    inv[0] = inv[1] = 1;
    for(int i=2; i<=n; i++) inv[i] = 1ll*(mod-mod/i)*inv[mod%i]%mod;
    up = 1; int l = 0;
    while(up<=n) up <<= 1, l++;
    for(int i=0; i<up; i++) rev[i] = (rev[i>>1]>>1)|((i&1)<<(l-1));
    int wn = fpw(G, mod>>l); w[up>>1] = 1;
    for(int i=(up>>1)+1; i<up; i++) w[i] = 1ll*w[i-1]*wn%mod;
    for(int i=(up>>1)-1; i>=1; i--) w[i] = w[i<<1];
  }
  void clear(int *a, int n) { memset(a, 0, n<<2); }
  int getlen(int n) { return 1<<(32-__builtin_clz(n)); }
  inline void mul(int *a, int n, int x, int *b) { while(n--) *b++ = 1ll**a++*x%mod; }
  inline void dot(int *a, int *b, int n, int *c) { while(n--) *c++ = 1ll**a++**b++%mod; }
  void DFT(int *a, int l)
  {
    static unsigned long long tmp[N];
    int u = __builtin_ctz(up/l), t;
    for(int i=0; i<l; i++) tmp[i] = a[rev[i]>>u];
    for(int i=1; i^l; i<<=1)
      for(int j=0, d=i<<1; j^l; j+=d)
        for(int k=0; k<i; k++)
          t = tmp[i|j|k]*w[i|k]%mod, tmp[i|j|k] = tmp[j|k]+mod-t, tmp[j|k] += t;
    for(int i=0; i<l; i++) a[i] = tmp[i]%mod;
  }
  void IDFT(int *a, int l)
  {
    reverse(a+1, a+l); DFT(a, l);
    mul(a, l, mod-mod/l, a);
  }
  inline void conv(int *a, int *b, int l) { DFT(a, l); DFT(b, l); dot(a, b, l, a); IDFT(a, l); }
  void mul(int *a, int n, int *b, int m, int *c)
  {
    static int l, ta[N], tb[N];
    if(n+m==0) //此时l=1，IDFT会re！！
    {
      c[0] = 1ll*a[0]*b[0]%mod;
      return;
    }
    l = getlen(n+m);
    for(int i=0; i<=n; i++) ta[i] = a[i];
    for(int i=0; i<=m; i++) tb[i] = b[i];
    conv(ta, tb, l);
    for(int i=0; i<=n+m; i++) c[i] = ta[i];
    clear(ta, l), clear(tb, l);
  }
}
void init(int n)
{
  fac[0] = 1;
  for(int i=1; i<=n; i++) fac[i] = 1ll*fac[i-1]*i%mod;
  ifac[n] = fpw(fac[n], mod-2);
  for(int i=n-1; i>=0; i--) ifac[i] = 1ll*ifac[i+1]*(i+1)%mod;
}
int comb(int a, int b)
{
  if(a<b||b<0||a<0) return 0;
  return 1ll*fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}
void solve(int p, int l, int r)
{
  f[p] = np, np += sd[r] - sd[l-1] + 1;
  if(l==r)
  {
    int cur = 1;
    for(int i=0; i<=d[l]; i++)
    {
      f[p][i] = cur;
      cur = 1ll*cur*comb(cnt[l]-2*i, 2)%mod*inv[i+1]%mod;
    }
    return;
  }
  int mid = (l+r)>>1;
  solve(p<<1, l, mid); solve(p<<1|1, mid+1, r);
  poly::mul(f[p<<1], sd[mid]-sd[l-1], f[p<<1|1], sd[r]-sd[mid], f[p]);
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n;
  int mx = 0;
  init(2*n);
  poly::init(n);
  for(int i=1; i<=2*n; i++)
  {
    cin >> h[i];
    cnt[h[i]]++;
    mx = max(mx, h[i]);
  }
  for(int i=1; i<=mx; i++)
  {
    d[i] = cnt[i]/2;
    sd[i] = sd[i-1] + d[i];
  }
  solve(1, 1, mx);
  for(int i=0; i<=sd[mx]; i++) g[i] = 1ll*f[1][i]*fac[2*n-2*i]%mod*ifac[n-i]%mod*fpw(fpw(2, n-i), mod-2)%mod;
  int ans = 0;
  for(int i=0; i<=sd[mx]; i++)
  {
    if(i&1) ans = (ans - g[i] + mod)%mod;
    else ans = (ans + g[i])%mod;
  }
  cout << ans << '\n';
  return 0;
}