【Luogu4921】情侣？给我烧了！（组合计数）

题面

题解

很有意思的一道题目。

直接容斥？怎么样都要一个平方复杂度了。

既然是恰好\(k\)对，那么我们直接来做：

首先枚举\(k\)对人出来\(\displaystyle {n\choose k}\)，然后枚\(k\)排座位出来\(\displaystyle {n\choose k}\)，这些人间的顺序关系\(k!\)，然后这些人可以左右交换\(2^{k}\)。

好的，现在的问题转化为了剩下\(n-k\)对人，两两之间不能坐在一排，求方案数。

首先这\(n-k\)对人的顺序提前算好\((n-k)!\)，然后左右顺序忽视掉\(2^{n-k}\)。

假装\(n\)对人完全错开的方案数是\(f(n)\)。

类似错排问题，然而并不是错排问题。类似错排问题的递推公式的想法，每次加入最新的一组。

那么当前这一组随便和前面哪一排找个人互换就好了，一共有两种交换方法。所以这一部分的贡献是\((n-1)*2*2*2*f(n-1)\)。

还有特殊情况就是原本换的那组两个人在一排，现在和这一排强制交换，有两种交换方法。那么这部分的贡献就是\((n-1)*2*f(n-2)\)。

那么转移凑合一下就是\(f(n)=2(n-1)(f(n-1)+f(n-2))\)。

再把答案式写一下：

\[Ans_k=2^n{n\choose k}^2k!(n-k)!f(n-k)\]

这样子预处理\(f\)之后单次的复杂度为\(O(n)\)。

不过我还看到了一种很有意思的方法。

设\(f[i][j]\)表示\(i\)对情侣中恰好有\(j\)对坐在一起的方案数,\(g[i]\)表示\(i\)对情侣都不坐在一起的方案数。

那么\(\displaystyle f[n][k]={n\choose k} A_n^k2^k*g[n-k]\)

那么反过来\(\displaystyle g[n]=(2n)!-\sum_{i=1}^n f[n][i]\)

这样子是\(O(n^2)\)的，感觉很有意思的方法。

代码是前面那种方法

#include
    
     #include
     
      using namespace std;#define MAX 1010#define MOD 998244353inline int read(){    int x=0;bool t=false;char ch=getchar();    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();    if(ch=='-')t=true,ch=getchar();    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();    return t?-x:x;}int n,f[MAX],jc[MAX],jv[MAX],inv[MAX],bin[MAX];int C(int n,int m){return 1ll*jc[n]*jv[m]%MOD*jv[n-m]%MOD;}int main(){    int T=read();jc[0]=jv[0]=inv[0]=inv[1]=f[0]=bin[0]=1;    for(int i=1;i
     
    

```