{"problem":{"name":"[集训队互测 2023] 童话","description":{"content":"泠珞最近学习了前缀和算法，她写出了以下程序： ```cpp 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$ 比较大的时候会运行超时，请你","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":2097152},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10007"},"statements":[{"statement_type":"Markdown","content":"泠珞最近学习了前缀和算法，她写出了以下程序：\n\n```cpp\nread(n),read(a);\nfor(int i=0;i<=n;i++)read(f[i]);\nfor(int t=1;t<=n;t++){\n    for(int i=1;i<=n;i++)f[i]=f[i]+a*f[i-1];\n    ans[t]=f[t];\n}\n```\n\n她发现这个程序在 $n$ 比较大的时候会运行超时，请你帮忙写一个程序帮她计算出 $\\text{ans}_1,\\text{ans}_2,\\cdots,\\text{ans}_n$，由于答案数值过大，你只需告诉她每个数除以 $998244353$ 的余数。\n\n## Input\n\n第一行两个正整数 $n,a$。\n\n接下来一行 $n+1$ 个非负整数，表示 $f_0,f_1,\\cdots,f_n$。\n\n## Output\n\n$n$ 个非负整数，表示 $\\text{ans}_1,\\text{ans}_2,\\cdots,\\text{ans}_n$。\n\n[samples]\n\n## Background\n\n~~童话只美在真实却从不续写。~~\n\n童话只美在温柔却从不续写。\n\n## Note\n\n数据范围：\n\n对于 $100\\%$ 的数据，保证 $2\\leqslant n\\leqslant 10^6,0\\leqslant f_i<998244353,1\\leqslant a<998244353$。\n\n| 子任务编号 |  $n\\leqslant$  | 特殊性质 | 分值 |\n| :--------: | :------------: | :------: | :--: |\n|    $1$     |     $2000$     |          | $5$  |\n|    $2$     |     $10^5$     |    A     | $5$  |\n|    $3$     |     $10^5$     |    BC    | $5$  |\n|    $4$     |     $10^5$     |    BD    | $10$ |\n|    $5$     |     $10^5$     |    C     | $10$ |\n|    $6$     | $5\\times10^4$  |          | $10$ |\n|    $7$     |     $10^5$     |          | $10$ |\n|    $8$     | $2\\times 10^5$ |          | $15$ |\n|    $9$     | $5\\times 10^5$ |          | $15$ |\n|    $10$    |     $10^6$     |          | $15$ |\n\n特殊性质 A：保证 $f_i\\ne 0$ 的 $i$ 数量不超过 $100$。\n\n特殊性质 B：保证 $a=1$。\n\n特殊性质 C：保证对于所有 $i\\in[0,n]$，都满足 $f_i=1$。\n\n特殊性质 D：保证对于所有 $i\\in[0,n]$，都满足 $f_i={i+2\\choose 2}=\\frac{(i+2)(i+1)}{2}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10007","tags":["集训队互测","2023","O2优化","生成函数","拉格朗日反演"],"sample_group":[["2 1\n1 2 0","3 7"],["10 10\n5 9 7 8 0 6 3 2 4 10 1","59 1687 55618 1937320 69557006 549579657 621247830 250099579 483510144 968467040"]],"created_at":"2026-03-03 11:09:25"}}