题目描述

一天 sx 经过一家商店，他看中 $n$ 个物品，在某些强大的力量的帮助下，sx 获得了如下优惠：每个物品价格均为 $1$ ，如果选择两个相邻的物品，会优惠 $1$ 元，但同一个物品不能被同时选择两次。由于 sx 手头上的钱只有 $m$ 块钱，因此对于某些物品，sx 可能不买。现在 sx 想知道对于所有的 $k∈[0,m]$，购买的价格恰好为 $k$ 的方案数，答案对 $998244353$ 取模。

不同方案的定义：设用方式1购买的单个物品的集合为 $S1$，方式2的 物品对 集合为 $S2$，在价格为 $k$ 的情况下，两种方案对应的集合 $S1$ 或 $S2$ 至少有一者不同。

输入格式

第一行一个正整数 $Q$，表示数据的组数。 接下来 $Q$ 行两个正整数 $n$, $m$。
注意：测试点包含多组数据

输出格式

一共 $Q$ 行，每行 $m+1$ 个整数，第 $k$ 个整数表示当购买的价钱恰好为 $k$ 时的方案数。

数据范围

$2\le n\le 10^9,\sum m\le10^3$

#include<bits/stdc++.h>
#define int long long
using namespace std;
int q,n,m,ans;
const int mod=998244353;
int qpow(int x,int y){
	int res=1;
	while(y){
		if(y&1) res=res*x%mod;
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
int C(int x,int y){
	int fac=1;
	for(int i=1;i<=y;i++) fac=fac*i%mod;
	int res=qpow(fac,mod-2);
	for(int i=x-y+1;i<=x;i++) res=res*i%mod;
	return res;
}
signed main(){
	cin>>q;
	while(q--){
		cin>>n>>m;
		for(int i=0;i<=m;i++){
			ans=0;
			for(int j=0;j<=min(i,n-i);j++)
				ans=(C(n-j,i)*C(i,j)+ans)%mod;
			cout<<ans<<" ";
		}
		cout<<"\n";
	}
    return 0; 
}