记录编号	549878	评测结果	A
题目名称	情侣？给我烧了	最终得分	100
用户昵称	沉迷学习的假的Keller	是否通过	通过
代码语言	C++	运行时间	0.079 s
提交时间	2020-02-25 21:41:16	内存使用	29.25 MiB

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=1000+10;
const long long mod=998244353;
long long c[maxn][maxn],fac[maxn],er[maxn],la[maxn],dp[maxn][maxn];

void dpk(){    //dp[i][j] 前i对情侣 j个座位只坐一个人时 合理的配对数(先不考虑座位) 
    dp[1][2]=1;
    la[0]=1;
	long long i,j;
    for(i=2;i<=1000;i++){
        for(j=0;j<=1000;j++){
         	if((i*2-j)&1){
			 	continue;
			}
         	dp[i][j]=(dp[i][j]+dp[i-1][j+2]*(j+2)*(j+1))%mod;   // 从j+2个单人座选两个坐 *C(j+2 2)
         	dp[i][j]=(dp[i][j]+dp[i-1][j]*j*2)%mod;             // 一个人做到单人座，另一个人新开一排 
         	if(j>=2)
			 	dp[i][j]=(dp[i][j]+dp[i-1][j-2])%mod;           //新开两排 
         	if(!j)
			 	la[i]=dp[i][j]*(fac[i])%mod*er[i]%mod; 
    	}
    }	
}
void pre(){
	fac[0]=1;er[0]=1;c[1][0]=1;c[1][1]=1;
	long long i,j;
	for(i=1;i<=1000;i++){
		fac[i]=fac[i-1]*i%mod;
	}
    for(i=1;i<=1000;i++){
		er[i]=er[i-1]*2%mod;
	}
	for(i=2;i<=1000;i++){
        c[i][0]=1;
        for(j=1;j<=i;j++){
			c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod;
		}
    }
    dpk();
	return ;
}

void keller(long long n){
	long long i;
	for(i=0;i<=n;i++){
		long long ans;
		ans=c[n][i]*c[n][i]%mod;
		ans=ans*fac[i]%mod;
    	ans=ans*er[i]%mod;
    	ans=ans*la[n-i]%mod;
    	printf("%lld\n",ans);
	}
	return ;
}

int main(){
	freopen("FFFqinglv.in","r",stdin);
	freopen("FFFqinglv.out","w",stdout);
	int T;
	scanf("%d",&T);
	pre();
	while(T--){
		long long x;scanf("%lld",&x);
		keller(x);
	}
	return 0;
}