P3711 仓鼠的数学题

    • 16通过
    • 41提交
  • 题目提供者 fjzzq2002
  • 评测方式 云端评测
  • 标签 生成函数 逆元 洛谷原创 O2优化 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    请注意本题时限1s,开启O2优化,你可能需要输入输出优化

    题目描述

    仓鼠在某oj上看到了一个问题,设$S_k(x)=\sum_{i=0}^x i^k$ ,这个题输入$a_0,a_1...a_n$ ,假设$0^0=1$ ,要求计算$\sum_{k=0}^{n}S_k(x)a_k$ 。

    仓鼠想了两秒就秒了这个题,他发现数据范围居然只有1000,就顺手加了两个0。

    但是仓鼠懒得造数据了,就把这道题丢给了你。

    输入输出格式

    输入格式:

    第一行输入一个整数$n$ 。

    第一行输入$n+1$ 个空格分隔的非负整数。分别是$a_0 \cdots a_n$ 。

    输出格式:

    输出$n+2$ 个空格分隔的整数,表示答案多项式的各项系数$c_0...c_{n+1}$ ,表示答案多项式为$\sum_{i=0}^{n+1}c_ix^i$ 。多项式的系数对998244353取模。

    可以证明多项式的次数$\leq n+1$ 。

    输入输出样例

    输入样例#1: 复制
    2
    3 3 3
    输出样例#1: 复制
    3 5 3 1

    说明

    对于10%的数据,$n \leq 500$ 。

    对于30%的数据,$n \leq 3000$ 。

    对于70%的数据,$n \leq 100000$ 。

    对于100%的数据,$1 \leq n \leq 250000$ 。

    输入和输出多项式系数均为模998244353意义下,为$[0,998244352]$ 的非负整数。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。