#1728. Wechat

    ID: 1728 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1082来源:qoj.ac数据:公开样例动态规划数学

Wechat

Wechat

题目描述

标题: Wechat - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

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

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

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

求 F0,F1,⋯,Fn−1。

答案对 998244353 取模。

输入格式

一行一个正整数 n。

输出格式

一行 n 个整数,表示 F0,F1,⋯,Fn−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≤n≤10

Subtask 2 (10 pts): 1≤n≤20

Subtask 3 (30 pts): 1≤n≤400

Subtask 4 (10 pts): 1≤n≤2000

Subtask 5 (40 pts): 1≤n≤100000

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3
166374059 665496236 166374059

样例 2

10
370705776 185074360 753392795 76402225 111791374 111791374 76402225 753392795 185074360 370705776