[数学记录]P4921 烧情侣

**题意:** $n$对CP随便坐**两列**座位,求**恰好**$k(0\leq k\leq n)$对CP坐在一起的方案数。 ------------ ~~无脑工业选手拿到计数只会反演硬刚……~~ 这个题叫我们计数去重。 无非就几种方法,要么把重复挖掉,要么反演掉。 ~~先给二项式反演推了半天还是跑不过简单版~~,我们来考虑下挖掉重复的方法。 设 $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$对,剩余随意的方案数。 $P[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简单版了。 ```cpp #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; } ``` 加强版可见 [多项式计数杂谈](https://www.luogu.com.cn/blog/command-block/sheng-cheng-han-shuo-za-tan)