TouchStone
  请登录后使用
登录 注册
距离CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3215
  • 题目
  • P3215多项式除法
    限制 : 时间限制 : 30000 MS   空间限制 : 265536 KB
    问题描述

    给你两个整系数多项式A(x),B(x),设A(x)=D(x)*B(x)+R(x),且deg(R)<=deg(B-1),deg(A)=deg(D)+deg(B),求D(x)和R(x)。
    令P=998244353(=223*7*17+1,是素数)。如果deg(f)=deg(g),且对于任意的整数0<=n<=deg(f),都有fn≡gn(mod P),那么我们认为f(x)=g(x)。

    输入格式

    第一行两个数deg(A)和deg(B)。
    第二行deg(A)+1个整数,表示A0,A1,...,Adeg(A)
    第三行deg(B)+1个整数,表示B0,B1,...,Bdeg(B)

    输出格式

    第一行deg(A)-deg(B)+1个整数,表示D0,D1,...,Ddeg(A)-deg(B)
    第二行deg(B)个整数,表示R0,R1,...,Rdeg(B)-1。如果deg(R)<deg(B)-1,高次项补0。

    样例输入

    3 1
    2 3 3 1
    1 1

    样例输出

    1 2 1 

    提示

    1<=deg(B)<deg(A)<=100000
    系数都是0到P-1的正整数,除了R(x)外最高次项不为0。