#P5087. polycomp

    ID: 4174 传统题 3000ms 256MiB 尝试: 256 已通过: 43 难度: 7 上传者: 标签>CF2300提高+/省选-秦九韶算法多项式除法预计算转移位并行多项式运算

polycomp

10 0 0 1 0 0 1 0 1 1 1 1
10 1 0 1 0 0 1 1 0 1 1 1
10 0 0 1 1 1 0 0 1 1 1 1
9 0 0 1 1 1 1 0 0 1 1

多项式取模在干啥

你有一个“很长很长”的多项式 P(x)P(x),比如

P(x)=x5+x4+x2P(x)=x^5+x^4+x^2

你还有一个“规则多项式” h(x)h(x),比如

h(x)=x3+x+1h(x)=x^3+x+1

题目说:把 P(x)P(x) 按照规则 h(x)h(x) 变成一个“次数更小”的多项式,这就叫

P(x) mod h(x)P(x)\bmod h(x)

并且系数只要 0/10/1,加法等于“开关翻转”(异或)。


关键直觉:h(x)=0h(x)=0 是一条“替换规则”

因为我们在“模 h(x)h(x)”的世界里,等价于规定:

h(x)≡0h(x)\equiv 0

也就是

x3+x+1≡0x^3+x+1 \equiv 0

把它移项(在模 22 里加减一样):

x3≡x+1x^3 \equiv x+1

这就是替换规则:遇到 x3x^3,你可以把它换成 x+1x+1。

老奶奶记法: “x3x^3 这个大块头,可以拆成 xx 和 11 两个小块头。”


那“每次乘完都取模”到底怎么做?

乘完你会得到一些很高次的项,比如 x5x^5、x8x^8…… 你要做的就是:把所有次数 ≥3\ge 3 的项,反复用规则变成次数 <3<3 的项。

我们用刚才的例子来做一遍:

P(x)=x5+x4+x2,h(x)=x3+x+1P(x)=x^5+x^4+x^2,\quad h(x)=x^3+x+1

规则:x3≡x+1x^3\equiv x+1

第一步:处理 x5x^5

因为

x5=x2⋅x3x^5 = x^2\cdot x^3

把 x3x^3 换掉:

x5=x2⋅x3≡x2⋅(x+1)=x3+x2x^5 = x^2\cdot x^3 \equiv x^2\cdot (x+1)=x^3+x^2

所以 PP 里的 x5x^5 可以换成 x3+x2x^3+x^2。

代回去:

P≡(x3+x2)+x4+x2P \equiv (x^3+x^2)+x^4+x^2

注意:在模 22 里,x2+x2=0x^2+x^2=0(出现两次就抵消) 于是变成:

P≡x4+x3P \equiv x^4+x^3

第二步:处理 x4x^4

x4=x⋅x3≡x⋅(x+1)=x2+xx^4=x\cdot x^3 \equiv x\cdot (x+1)=x^2+x

所以

P≡(x2+x)+x3P \equiv (x^2+x)+x^3

第三步:处理 x3x^3

x3≡x+1x^3\equiv x+1

所以

P≡x2+x+(x+1)=x2+1P \equiv x^2+x+(x+1)=x^2+1

因为 x+x=0x+x=0。

现在次数是 2<32<3,结束。

最终

P(x) mod h(x)=x2+1P(x)\bmod h(x)=x^2+1

你可以把它当成“消掉最高次项”的机械步骤(不用想太多)

上面那套替换,其实等价于一个特别机械的动作:

  • 找到 PP 里最高次项,比如 x5x^5
  • 让 hh 乘上一个 x2x^2 变成也有 x5x^5:h(x)⋅x2=x5+x3+x2h(x)\cdot x^2 = x^5 + x^3 + x^2
  • 然后用“异或”把它从 PP 里消掉(同次项出现两次就没了)

这就是我之前说的

P←P⊕(h⋅xt)P \leftarrow P \oplus (h\cdot x^t)

但你现在只要记住一句:

对齐最高次,把 hh 乘上适当的 xtx^t,然后把对应项“翻转/抵消”。反复做,直到次数小于 deg⁡h\deg h。