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)=x^5+x^4+x^2$$

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

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

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

$$P(x)\bmod h(x)$$

并且系数只要 $0/1$，加法等于“开关翻转”（异或）。

---

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

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

$$h(x)\equiv 0$$

也就是

$$x^3+x+1 \equiv 0$$

把它移项（在模 $2$ 里加减一样）：

$$x^3 \equiv x+1$$

这就是替换规则：遇到 $x^3$，你可以把它换成 $x+1$。

老奶奶记法： “$x^3$ 这个大块头，可以拆成 $x$ 和 $1$ 两个小块头。”

---

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

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

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

$$P(x)=x^5+x^4+x^2,\quad h(x)=x^3+x+1$$

规则：$x^3\equiv x+1$

第一步：处理 $x^5$

因为

$$x^5 = x^2\cdot x^3$$

把 $x^3$ 换掉：

$$x^5 = x^2\cdot x^3 \equiv x^2\cdot (x+1)=x^3+x^2$$

所以 $P$ 里的 $x^5$ 可以换成 $x^3+x^2$。

代回去：

$$P \equiv (x^3+x^2)+x^4+x^2$$

注意：在模 $2$ 里，$x^2+x^2=0$（出现两次就抵消） 于是变成：

$$P \equiv x^4+x^3$$

第二步：处理 $x^4$

$$x^4=x\cdot x^3 \equiv x\cdot (x+1)=x^2+x$$

所以

$$P \equiv (x^2+x)+x^3$$

第三步：处理 $x^3$

$$x^3\equiv x+1$$

所以

$$P \equiv x^2+x+(x+1)=x^2+1$$

因为 $x+x=0$。

现在次数是 $2<3$，结束。

最终

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

---

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

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

• 找到 $P$ 里最高次项，比如 $x^5$
• 让 $h$ 乘上一个 $x^2$ 变成也有 $x^5$：$$h(x)\cdot x^2 = x^5 + x^3 + x^2$$
• 然后用“异或”把它从 $P$ 里消掉（同次项出现两次就没了）

这就是我之前说的

$$P \leftarrow P \oplus (h\cdot x^t)$$

但你现在只要记住一句：

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

---