2025牛客多校第八场 根号-2进制 个人题解

J.根号-2进制

数学 #FFT

思路

赛后发现身边的同学都是通过借位来解决进位问题的，在此提供一种全程不出现减法的顺推做法
首先\(A,B\)可以理解为两个多项式：\(A_{0}+A_{1}\sqrt{ -2 }+A_{2}(\sqrt{ -2 })^2+\dots\)，其中\(A_{i}=\{ 0,1 \}\)，\(B_{i}\)同理
那么可以使用多项式乘法\(FFT\)先将\(A,B\)相乘后的结果表示为一个新的多项式\(C\)，此时该多项式的系数\(C_{i}\)不一定为\(\{ 0,1 \}\)
因此我们的任务变为了如何将一个多项式的系数在\(\sqrt{ -2 }\)进制下全部化为\(\{ 0,1 \}\)
为了方便观察，将\(\sqrt{ -2 }\)写为\(2^{\frac{1}{2}}i\)，则\((\sqrt{ -2 })^k=2^{\frac{k}{2}}i^k\)
打表观察：

\[\begin{align}&i=1:\quad 2^{\frac{1}{2}}i\\ \\&i=2:\quad -2^{\frac{2}{2}}\\  \\&i=3:\quad -2^{\frac{3}{2}}i \\ \\&i=4:\quad 2^{\frac{4}{2}}\\ \\&i=5:\quad 2^{\frac{5}{2}}i\\ \\&i=6:\quad -2^{\frac{6}{2}}\end{align}\]
发现明显规律且周期\(T=4\)
设\(a=\sqrt{ -2 }\)，则必有\(2^2\times a^p=a^{p+4}\)
进一步推广：

\[2^{2k}\times a^p=a^{p+4k}\]
现在解决了\(2\)的偶数次幂与\(a\)的任意次幂相乘的递推，如果能够解决\(2\)的奇数次幂与\(a\)任意次幂相乘的递推，那么就可以通过对多项式系数\(C_{i}\)二进制分解不断递推，将所有系数化为\(\{ 0,1 \}\)
由于\(2^{2k+1}=2^{2k}\times 2\)，因此解决\(2\times a^p\)的递推即可
观察表格可知\(2\times a^p=-a^{p+2}\)，即\(2\times a^p+a^{p+2}=0\)
因此有\(2\times a^p+a^{p+2}=2\times a^{p+2}+a^{p+4}=0\)
则有：

\[2\times a^p=a^{p+2}+a^{p+4}\]
这样就能不断地将系数向高次推推推，最终全部推成\(\{ 0,1 \}\)啦！
然而，聪明的\(phaethon 90\)发现了问题：
如果原本的多项式在推导过程中包含形如\(2\times a^p+a^{p+2}+\dots\)的部分，那么对\(2\times a^p\)套用上述递推将导致无限循环，因为\(2\times a^p+a^{p+2}=0\)
因此，在使用第二个递推前，先判断\(a^{p+2}\)项的系数是否为奇数：

• 如果为奇数，那么就可以利用\(2\times a^p+a^{p+2}=0\)将这个奇数消去，避免在处理到\(p+2\)位时仍然是个奇数
  
• 如果为偶数，那么可以利用递推二\(2\times a^p=a^{p+2}+a^{p+4}\)往高位推
  

当更新过的最高位已经与当前位重合了，那么就退出循环
fun fact：这个代码在赛事实际上早就写好了，但是因为不知道如何给FFT清空，以及没有发现最后输出的多项式的项数size远大于size(A)+size(B)，导致没有清空完全，一直在WAAAAA
代码实现

[code]#include#include#include#include#include#include#include#includeusing namespace std;using ll = long long;#define rep(i, a, b) for(ll i = (a); i = (b); i --)#define see(stl) for(auto&ele:stl)cout