#1809. 童话

    ID: 1809 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1437来源:qoj.ac数据:公开样例前缀和递推

童话

童话

题目描述

标题: 童话 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

童话只美在真实却从不续写。

泠珞最近学习了前缀和算法,她写出了以下程序:

read(n),read(a);
for(int i=0;i<=n;i++)read(f[i]);
for(int t=1;t<=n;t++){
    for(int i=1;i<=n;i++)f[i]=f[i]+a*f[i-1];
    ans[t]=f[t];
}

她发现这个程序在 n 比较大的时候会运行超时,请你帮忙写一个程序帮她计算出 ans1,ans2,⋯,ansn,由于答案数值过大,你只需告诉她每个数除以 998244353 的余数。

输入格式

第一行两个正整数 n,a。

接下来一行 n+1 个非负整数,表示 f0,f1,⋯,fn。

输出格式

n 个非负整数,表示 ans1,ans2,⋯,ansn。

样例

样例 #1:

输入:

2 1
1 2 0

输出:

3 7

样例 #2:

输入:

10 10
5 9 7 8 0 6 3 2 4 10 1

输出:

59 1687 55618 1937320 69557006 549579657 621247830 250099579 483510144 968467040

数据范围与约定

对于 100% 的数据,保证 2⩽n⩽106,0⩽fi<998244353,1⩽a<998244353。

子任务编号n⩽特殊性质分值1200052105A53105BC54105BD105105C1065×1041071051082×1051595×105151010615

特殊性质 A:保证 fi≠0 的 i 数量不超过 100。

特殊性质 B:保证 a=1。

特殊性质 C:保证对于所有 i∈[0,n],都满足 fi=1。

特殊性质 D:保证对于所有 i∈[0,n],都满足 fi=(i+22)=(i+2)(i+1)2。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 1
1 2 0
3 7

样例 2

10 10
5 9 7 8 0 6 3 2 4 10 1
59 1687 55618 1937320 69557006 549579657 621247830 250099579 483510144 968467040