QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100 Hackable ✓

# 5360. Wechat

统计

小 $W$ 正在和妹子语音对话,但是他的妹子不想理他。于是妹子每次会独立地在 $[0,10]$ 中等概率随机实数 $l$,并发送一段 $l$ 秒的语音给他。但是屏幕另一端的小 $W$ 并不知道这件事,所以当妹子的语音长度越来越短时,小 $W$ 会觉得自己没有找到妹子喜欢的话题并感到焦虑。而当某一段语音的时间比上一段长时,小 $W$ 会感到欣喜万分,因为他觉得他又找到话题了。

更具体的说,我们假定小 $W$ 和他的妹子进行了 $n$ 轮对话。我们可以用一个长度为$n$的序列 $a_1,a_2,\dots,a_n$ 表示妹子发送的 $n$ 段语音时长,其中 $a_i$ 表示第 $i$ 段语音的时长,它在 $[0,10]$ 中等概率随机并与其他元素独立。如果某个 $i(1\leq i < n)$ 满足 $a_i < a_{i+1}$,那么小 $W$ 就会欣喜一次。在这 $n$ 轮对话中小 $W$ 会感到欣喜的总次数就是满足 $a_i < a_{i+1}$($1\leq i < n$)的 $i$ 的个数。

令 $F_k$ 表示当语音段数为 $n$ 时小 $W$ 会欣喜 $k$ 次的概率。

求 $F_0,F_1,\cdots,F_{n-1}$。

答案对 $998244353$ 取模。

输入格式

一行一个正整数 $n$。

输出格式

一行 $n$ 个整数,表示 $F_0,F_1,\cdots,F_{n-1}$。

样例数据

样例 1 输入

3

样例 1 输出

166374059 665496236 166374059

样例 2 输入

10

样例 2 输出

370705776 185074360 753392795 76402225 111791374 111791374 76402225 753392795 185074360 370705776

子任务

Subtask 1 (10 pts): $1\leq n \leq 10$

Subtask 2 (10 pts): $1\leq n \leq 20$

Subtask 3 (30 pts): $1\leq n \leq 400$

Subtask 4 (10 pts): $1\leq n \leq 2000$

Subtask 5 (40 pts): $1\leq n \leq 100000$