TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3226
  • 题目
  • P3226周伯通的多项式求逆元
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 3s,256MB
    问题描述

    周伯通空明拳很厉害:

    • $1$ 拳 $1$ 个小朋友
    • $2$ 拳 $1/2$ 个小朋友
    • \(-1\)\(-1\) 个小朋友
    • $1-x$ 拳 $1+x+x^2+x^3+\cdots$ 个小朋友
    • $1-x^3$ 拳 $1+x^3+x^6+x^9+\cdots$ 个小朋友
    • $1-x-x^2$ 拳 $1+x+2x^2+3x^3+5x^4+8x^5+13x^6+21x^7+34x^8+\cdots$ 个小朋友
    • \(x\) 拳无法打小朋友

    求给定 \(n\) 次多项式 \(A(x)\) ,周伯通打了 \(A(x)\) 拳有多少个小朋友。

    答案可能是有无穷多项,你只需要输出答案 \(\bmod{x^{m+1}}\) 后的多项式 \(B(x)\) ,且所有数值运算都对 \(P=998244353\) 取模。

    输入格式

    多组测试数据。

    每组数据第一行一个整数 \(n,m\) ,表示 \(A(x),B(x)\) 的次数。

    每组数据第二行 \(n+1\) 个整数系数 \(a_0,\cdots,a_n\) ,表示 \(A(x)\) 每项的系数,设 \(P=998244353\) ,所有都在 \([0,P-1]\) 范围内。

    \(n=m=-1\) 表示结束。

    输出格式

    每组数据,如果有解输出一行用空格间隔的 \(m+1\) 个整数系数 \(b_0,\cdots,b_m\) ;如果无解输出一行 “stQ nodgd Orz”。

    样例输入

    0 5
    1

    0 5
    2

    0 5
    998244352

    1 5
    1 998244352

    3 10
    1 0 0 998244352

    2 10
    1 998244352 998244352

    1 100000
    0 1

    -1 -1

    样例输出

    1 0 0 0 0 0
    499122177 0 0 0 0 0
    998244352 0 0 0 0 0
    1 1 1 1 1 1
    1 0 0 1 0 0 1 0 0 1 0
    1 1 2 3 5 8 13 21 34 55 89
    stQ nodgd Orz

    提示

    \(n,m\leq 10^5\)
    \(\sum n\leq 5\times 10^5\)
    \(\sum m\leq 5\times 10^5\)
    只有一组测试数据,时限是nodgd标程的3倍。


    来源  感谢nodgd坑