TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3226
  • Problem
  • P3226周伯通的多项式求逆元
    Limits : Time Limit : - MS   Memory Limit : 262144 KB
    Judgment Tips : 3s,256MB
    Description

    周伯通空明拳很厉害:

    • $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\) 取模。

    Input Format

    多组测试数据。

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

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

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

    Output Format

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

    Sample Input

    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

    Sample Output

    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

    Hint

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


    Source  感谢nodgd坑