[数学记录]P4921 烧情侣

· · 个人记录

题意:

------------ ~~无脑工业选手拿到计数只会反演硬刚……~~ 这个题叫我们计数去重。 无非就几种方法,要么把重复挖掉,要么反演掉。 ~~先给二项式反演推了半天还是跑不过简单版~~,我们来考虑下挖掉重复的方法。 设 $F[k]$ 恰好 $k$ 对CP坐在一起的方案数。 我们先 $\dbinom{n}{k}^2k!2^k$ ,这是 (选出CP $*$ 选出座位 $*$ CP之间排列 $*$ CP内部交换) 的方案数。 剩下的人必须坐不出一对CP来,也就是混着坐。 我们设 $D[n]$ 为 $n$ 对情侣坐两列座位,没有一对相邻的方案数。 显然最终答案为$F[k]=\dbinom{n}{k}^2k!2^kD[n-k]

现在问题就变成了求 D[0...n] ,考虑二项式反演(容斥)。

设G[n,k]为n对钦点k对,剩余随意的方案数。

易得$G[n,k]=\dbinom{n}{k}^2k!2^k(2(n-k))!

且G[n,k]=\sum\limits_{i=k}^n\dbinom{i}{k}P[n,i]

反演过来即P[n,k]=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom{i}{k}G[n,i]

D(n)=P[n,0]=\sum\limits_{i=0}^n(-1)^{i}G[n,i] =\sum\limits_{i=0}^n(-1)^{i}\dbinom{n}{i}^2i!2^i(2(n-i))!

推到这个式子,已经足够AC简单版了。

#include<algorithm>
#include<cstdio>
#define ll long long
#define mod 998244353
#define Maxn 2050
using namespace std;
ll ifac[Maxn],fac[Maxn],p2[Maxn];
ll C(ll n,ll m)
{return fac[n]*ifac[m]%mod*ifac[n-m]%mod;}
ll D[Maxn];
int main()
{
  fac[0]=fac[1]=ifac[0]=ifac[1]=1;
  for (int i=2;i<=2005;i++)
    ifac[i]=(ifac[mod%i]*(mod-mod/i))%mod;
  p2[0]=1;p2[1]=2;
  for (int i=2;i<=2005;i++){
    fac[i]=fac[i-1]*i%mod;
    ifac[i]=ifac[i]*ifac[i-1]%mod;
    p2[i]=(p2[i-1]<<1)%mod;
  }
  for (int i=0;i<=1005;i++){
    ll buf=1;
    for (int j=0;j<=i;j++){
      ll sav=C(i,j);
      D[i]=(D[i]+sav*sav%mod*buf%mod
                *fac[j]%mod*fac[(i-j)<<1])%mod;
      buf=buf*(mod-2)%mod;
    }
  }int T;scanf("%d",&T);
  while(T--){
    int n;
    scanf("%d",&n);
    for (int i=0;i<=n;i++){
      ll ans=C(n,i);
      ans=ans*ans%mod*fac[i]%mod*p2[i]%mod*D[n-i]%mod;
      printf("%lld\n",ans);
    }
  }
  return 0;
}

加强版可见 多项式计数杂谈