题解 P4921 【情侣？给我烧了！】

这题加强版能有黑我把电脑吃了

写一篇题解来纪念一下我的首黑（？）。

记得在首蓝和首紫的时候我也确实是写了一篇题解作为纪念。

其实我也不知道我咋 A 掉这玩意的。。我就把它原题的代码复制粘贴过来，改了个数据范围和输入，然后就 A 了它的加强版（？）。

说实话，真不觉得这题有黑，感觉顶多蓝吧。。不就是个高中数学排列组合……（虽然我自己在错排那块卡了挺久的）

题目链接

P4921 [MtOI2018]情侣？给我烧了！

加强版

思路分析

这里就写原题的分析了，加强版和原题实际上差不多。

参考资料：题解 P4921 【情侣？给我烧了！】 – Shone 的博客 – 洛谷博客

看到这道题目，我们可以把问题拆成两部分来做。

我们可以知道，电影院中的人实际上是有两部分构成的：一是”和睦“的情侣，二是其它“无所谓“的人。（虽然这样描述可能有点不太恰当，但是全当理解题意就这么说吧。）

对于“和睦”情侣：首先从 /(n/) 对情侣中选出 /(k/) 对作为“和睦”的情侣，即 /(/mathrm C_n^k/)。（千万别忘了这个，我当时就是忘了这个）。然后对于 /(k/) 对情侣，我们要将他们安放在 /(k/) 排座位上，所以我们要从 /(n/) 排座位中选出 /(k/) 对，也就是 /(/mathrm A_n^k/)。接下来还没完，我们还要确定，对于每一对情侣要坐的这一排座位，哪个坐在”左边”哪个坐在”右边“（感性理解一下），对于每一排座位，每对情侣有两种坐法，那么总共 /(k/) 对情侣，有 /(2^k/) 种做法。根据乘法原理，对于 /(k/) 对和睦情侣坐的位置的总方案数就为 /(/mathrm C_n^k /times /mathrm A_n^k /times 2^k/)。

对于其它“无所谓”的人：首先，其它无所谓的人肯定是不能随便坐的，因为我们要求恰好 /(k/) 对情侣，而如果其它人随便坐可能会产生新的“和睦”的情侣，这就不符合恰好 /(k/) 对情侣的要求了。所以我们要把这些剩下的人安排到剩下的 /(2n-2k/) 个座位上，让他们满足：不能存在任何一对“和睦”的情侣。那么实际上，我们要求的就是剩下的 /(n-k/) 对情侣都错开的方案数。

那么我们定义 /(g(x)/) 为让 /(x/) 对情侣都错开的方案数。

我们从第一排开始考虑：

一共有三种情况：两男两女或者一男一女（不“和睦”）；

• 两男：首先选出两男的方案数是 /(x(x-1)/)，那么我们还必须考虑原本和他们应该“和睦”的配偶在他们被选过之后的情况：

  1. 如果他们的配偶坐在一排，那么要在剩下的 /(x-1/) 排中选择一排匹配给他们，那么方案数：/(2(x-1) /times g(x-2)/)；

  2. 如果他们不坐在一块，就强制把他们看做一对情侣来保证以后不坐在一块，方案数：/(g(x-1)/)。

• 两女：和两男的情况相同。

• 一男一女：枚举一男一女，可以交换顺序的方案数为 /(x(x−1)/)。

  所以，/(g(x)=4x(x-1) /times [g(x-1)+2(x-1)/times g(x-2)]/)

  注意：这里要分清楚加法原理和乘法原理，不要把符号给搞错了。

  时间复杂度：预处理 1-2000（加强版是 1-5e6） 的阶乘，逆元，g(x)。那么单次询问时间复杂度 /(O(n)/)，总时间复杂度 /(O(Tn)/)。

易错点

1. 那么多数相乘肯定会爆 int，所以请开 long long。另外防止爆 long long，请每次乘完都模一遍 /(mod/)。

2. 一定要在想之前把这道题的逻辑搞清楚，很容易乱（比如我在刚开始就漏了第一个 /(/mathrm C_n^k/)，然后弄清楚乘法原理和加法原理。

代码实现

//luoguP4921
#include<iostream>
#include<cstdio>
#define int long long//记得开 long long
using namespace std;
const int maxn=5e6+10;
const int mod=998244353;
int jc[maxn],inv[maxn],in[maxn],jcc[maxn];

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

void init()
{
	jc[0]=jc[1]=inv[0]=inv[1]=in[0]=in[1]=1;//预处理，一定要注意把 inv[0] 设成 1。
	for(int i=2;i<=2000;i++)//预处理 i 的阶乘，阶乘逆元
	{
		jc[i]=jc[i-1]*i%mod;
		inv[i]=(mod-mod/i)%mod*inv[mod%i]%mod;
		in[i]=in[i-1]*inv[i]%mod;
	}
	jcc[0]=1;jcc[1]=0;//预处理 g(x)
	for(int i=2;i<=1000;i++)jcc[i]=4*(i-1)*i%mod*(jcc[i-1]+2*(i-1)*jcc[i-2]%mod)%mod;
}

int A(int n,int m){return jc[n]*in[n-m]%mod;}

int C(int n,int m){return jc[n]*in[n-m]%mod*in[m]%mod;} //记得要多 % 几次。

int qpow(int a,int T)
{
	int ret=1;
	while(T)
	{
		if(T&1) (ret*=a)%=mod;
		(a*=a)%=mod;T>>=1;
	}
	return ret;
}

signed main()
{
	int T;
	T=read();
	init();
	//for(int i=1;i<=2000;i++)cout<<jc[i]<<" "<<inv[i]<<" "<<in[i]<<endl;
	while(T--)
	{
		int n;
		n=read();
		for(int i=0;i<=n;i++)
		{
			cout<<C(n,i)*qpow(2,i)%mod*A(n,i)%mod*jcc[n-i]%mod<<endl;
		}
	}
	return 0;
}