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

题面

题解

很有意思的一道题目。
直接容斥？怎么样都要一个平方复杂度了。
既然是恰好(k)对，那么我们直接来做：
首先枚举(k)对人出来(displaystyle {nchoose k})，然后枚(k)排座位出来(displaystyle {nchoose 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{nchoose k}^2k!(n-k)!f(n-k) ]

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

不过我还看到了一种很有意思的方法。
设(f[i][j])表示(i)对情侣中恰好有(j)对坐在一起的方案数,(g[i])表示(i)对情侣都不坐在一起的方案数。
那么(displaystyle f[n][k]={nchoose k} A_n^k2^k*g[n-k])
那么反过来(displaystyle g[n]=(2n)!-sum_{i=1}^n f[n][i])
这样子是(O(n^2))的，感觉很有意思的方法。

代码是前面那种方法

#include<iostream>
#include<cstdio>
using namespace std;
#define MAX 1010
#define MOD 998244353
inline 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<MAX;++i)f[i]=2ll*(i-1)*(f[i-1]+f[i-2])%MOD;
	for(int i=2;i<MAX;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;
	for(int i=1;i<MAX;++i)jc[i]=1ll*jc[i-1]*i%MOD;
	for(int i=1;i<MAX;++i)jv[i]=1ll*jv[i-1]*inv[i]%MOD;
	for(int i=1;i<MAX;++i)bin[i]=2ll*bin[i-1]%MOD;
	while(T--)
	{
		n=read();
		for(int i=0;i<=n;++i)
			printf("%lld
",1ll*bin[n]*C(n,i)%MOD*C(n,i)%MOD*jc[n-i]%MOD*jc[i]%MOD*f[n-i]%MOD);
	}
	return 0;
}