洛谷4921

Description

有 对情侣来到电影院观看电影。在电影院，恰好留有 排座位，每排包含 个座位，共 个座位。 现在，每个人将会随机坐在某一个位置上，且恰好将这 个座位坐满。 如果一对情侣坐在了同一排的座位上，那么我们称这对情侣是和睦的。 你的任务是求出当 时，共有多少种不同的就坐方案满足恰好有 k 对情侣是和睦的。 两种就坐方案不同当且仅当存在一个人在两种方案中坐在了不同的位置。不难发现，一共会有 种不同的就坐方案。

Input

输入包含多组数据。 输入的第一行包含一个正整数 ，表示数据的组数。 接下来 行，每行包含一个正整数 。

Output

对于每组输入数据，输出共 行，每行包含 个整数，分别表示 时满足恰好有 对情侣是和睦的就坐方案数。由于结果可能较大，因此输出对 取模的结果。

Sample Input

2
1
2

Sample Output

0
2
16
0
8

Hint

本题只有一个 的数据点。。。暴力还是算了吧！

Solution

看到第一眼我会 然而没分（毒瘤）

并没有怎么做过错排于是就直接看题解了

记为我们要求的恰对情侣和睦的方案数

首先我们从对CP中选这对CP有种方案数，给这对CP找排座位有种方案，每一对人对应每一排座位共有种对应方法，这对CP每一对的两个人在同一排有两种坐法(男左女右or男右女左) 在这对CP就共种

然后呢？考虑剩下的被拆散的对CP怎么搞，而且这对CP的坐法好像和无关，Emmm...有点错排的味道了

记表示对CP坐排座位并且都被拆散的方案数

所以可以得到

类似错排考虑最后一个放哪里的方法，我们考虑最后一排的两个人的情况 现在这两个人有三种情况

• 两男 这两个人有种选法，考虑他们的两个配偶
  1. 钦定这两个女生不坐一起，所以把她俩看作一对CP防止配对(橘里橘气) 方案数为
  2. 钦定这两个女生坐一起，共有排位置可坐，两人可以交换位置，剩下对CP还是要被拆散，即方案数为
• 两女 同两男即可
• 一男一女（并不是CP）还是一样的考虑他们的两个配偶，转移类似，不过注意的是这一男一女的选择方案数是 而不是 (男A女B和男B女A两种)

所以得到递推式 边界然后就成水题了

Code

#include<bits/stdc++.h>
#define FIO "P4921"
#define INF 0x3f3f3f
#define DBUG(...) fprintf(stderr,__VA_ARGS__)
typedef long long ll;
const int MOD=998244353,MAXN=1e3;
using namespace std;
char buf[1<<20];int bufl,bufr;
#define getch ((bufl^bufr||(bufl=0,bufr=fread(buf,1,1<<20,stdin)))?buf[bufl++]:EOF)
template <class T>inline void read(T &x){T f=1;x=0;char ch=getchar();for(;!isdigit(ch)&&ch!='-';ch=getchar());if(ch=='-')f=-1,ch=getchar();for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';x*=f;}
int N,T,f[MAXN+5],inv[MAXN+5],fac[MAXN+5],bin[MAXN+5];
inline int mul(int a,int b){return (ll)a*b%MOD;}
inline int add(int a,int b){a+=b;if(a>=MOD)a-=MOD;return a;}
inline int CC(int a,int b){
	int t=mul(fac[a],mul(inv[b],inv[a-b]));
	return mul(t,t);
}
int main(){
	freopen(FIO".in","r",stdin);
	freopen(FIO".out","w",stdout);	
	fac[0]=inv[0]=fac[1]=inv[1]=bin[0]=1;bin[1]=2;
	for (int i=2;i<=MAXN;i++)	fac[i]=mul(fac[i-1],i),inv[i]=mul(MOD/i,add(MOD,-inv[MOD%i])),bin[i]=add(bin[i-1],bin[i-1]);
	for (int i=2;i<=MAXN;i++)	inv[i]=mul(inv[i],inv[i-1]);
	f[0]=1;
	for (int i=1;i<=MAXN;i++)
		f[i]=mul(mul(i<<1,2*i-2),add(f[i-1],mul(2*i-2,f[i-2])));
	read(T);
	while (T--){
		read(N);
		for (int i=0;i<=N;i++)
			printf("%d\n",mul(mul(mul(CC(N,i),bin[i]),fac[i]),f[N-i]));
	}

	return 0;
}