|
||||||||||
Buying SnacksTime Limit: 6000/3000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)Total Submission(s): 452 Accepted Submission(s): 173 Problem Description As a foodie, Diana loves eating snacks. One day, her snacks were all confiscated by Bella, so Diana decided to buy some more in a snack shop. There are totally $n$ different type of snacks in the snack shop, numbered from $1,2,\dots,n$. Each of snacks has two sizes of packages, $big$ ones and $small$ ones. Diana wants to taste different snacks as many as possible, so she will buy $at$ $most$ $1$ $package$ for each type of snacks. For any $two$ $adjacent$ kinds of snacks(no matter the size), Diana can choose to buy them as a bundle, so that she could have a discount compared to buying them respectively. To simplify this problem, we assume that any $small$ package of snacks costs $1$ coin, any $big$ one costs $2$ coins and any discount is $1$ coin. Now Diana wonders how many different ways to buy snacks with $just$ $k$ coins. Please output the answer module $998244353$ for each $k\in[1,m]$. Two ways are considered the $same$ if types of snacks, sizes of snacks and bundles are all the same. $Notice$: For $two$ $adjacent$ kinds of snacks, Diana could either buy them respectively without a discount or buy them as a bundle, and they are considered as different ways. $For$ $example$: when $n=2,k=2$, there are $5$ different ways: $(1b), (2b), (1s$&$2b), (1b$&$2s), (1s)(2s)$ (number means the type of snack, $s$ means its a small package, $b$ means its a big package, & means its a bundle) Input The first line contains an integer $T(T\leq 5)$ , denoting the number of test cases. Each test case contains two integers $n(1\leq n \leq 10^9)$, $m(1 \leq m \leq 20000)$ denoting the number of types of snacks and the maximum number of coins. It is guaranteed that for all test cases, $\sum m \leq 30000$ Output For each test case, output a line with $m$ integers, indicating the answer. Sample Input
Sample Output
Source | ||||||||||
|