J.根号-2进制

#数学 #FFT

思路

赛后发现身边的同学都是通过借位来解决进位问题的，在此提供一种全程不出现减法的顺推做法

首先$A,B$可以理解为两个多项式：$A_0+A_1\sqrt{-2}+A_2(\sqrt{-2}{)}^2+\dots$，其中Ai={0,1}A_{i}=\{ 0,1 \}Ai​={0,1}，$B_i$同理

那么可以使用多项式乘法$FFT$先将$A,B$相乘后的结果表示为一个新的多项式$C$，此时该多项式的系数$C_i$不一定为{0,1}\{ 0,1 \}{0,1}

因此我们的任务变为了如何将一个多项式的系数在$\sqrt{-2}$进制下全部化为{0,1}\{ 0,1 \}{0,1}

为了方便观察，将$\sqrt{-2}$写为$2^{\frac{1}{2}}i$，则$(\sqrt{-2}{)}^k=2^{\frac{k}{2}}{i}^k$

打表观察：
$$\begin{array}{rl}& i=1:2^{\frac{1}{2}}i\\ & \\ & i=2:-2^{\frac{2}{2}}\\ & \\ & i=3:-2^{\frac{3}{2}}i\\ & \\ & i=4:2^{\frac{4}{2}}\\ & \\ & i=5:2^{\frac{5}{2}}i\\ & \\ & i=6:-2^{\frac{6}{2}}\end{array}$$
发现明显规律且周期$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}\{ 0,1 \}{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}\{ 0,1 \}{0,1}啦！

然而，聪明的$phaethon90$发现了问题：
如果原本的多项式在推导过程中包含形如$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

代码实现

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<numeric>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = (a); i <= (b); i ++)
#define per(i, a, b) for(ll i = (a); i >= (b); i --)
#define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n';
constexpr ll inf = 1e9 + 5;
#define int ll
#define double long double
constexpr ll  mod = 998244353;const double pi = acos(-1);const int N = 4e5 + 5;struct complex {double x, y;complex operator+(const complex& t)const {return{ x + t.x,y + t.y };}complex operator-(const complex& t)const {return{ x - t.x,y - t.y };}complex operator*(const complex& t)const {return{ x * t.x - y * t.y,x * t.y + y * t.x };}
}A[N], B[N];
int R[N];void FFT(complex A[], int n, int op) {rep(i, 0, n - 1)R[i] = R[i / 2] / 2 + ((i & 1) ? n / 2 : 0);rep(i, 0, n - 1)if (i < R[i])swap(A[i], A[R[i]]);for (int i = 2; i <= n; i <<= 1) {complex w1({ cos(2 * pi / i),sin(2 * pi / i) * op });for (int j = 0; j < n; j += i) {complex wk({ 1,0 });rep(k, j, j + i / 2 - 1) {complex x = A[k], y = A[k + i / 2] * wk;A[k] = x + y; A[k + i / 2] = x - y;wk = wk * w1;}}}
}
int n = 0, m = 0,pos=0;
int ans[N+10];
void eachT() {string s1, s2; cin >> s1 >> s2;int up=max(n,m);up=max(up,pos);rep(i, 0, up+5) {A[i] = B[i] = { 0,0 };R[i] =ans[i]=0;}n = s1.length() - 1, m = s2.length() - 1;rep(i, 0, n)A[i].x = s1[n - i] - '0', A[i].y = 0;rep(i, 0, m)B[i].x = s2[m - i] - '0', B[i].y = 0;for (m = n + m, n = 1; n <= m; n <<= 1);FFT(A, n, 1); FFT(B, n, 1);rep(i, 0, n - 1)A[i] = A[i] * B[i];FFT(A, n, -1);int highid = 0;bool all0 = 1;rep(i, 0, m) {ans[i] = (int)(A[i].x / n + 0.5);if (ans[i] != 0)all0 = 0;if (ans[i] > 0 && i > highid) {highid = i;}}if (all0) {cout << 0 << '\n';return;}pos = 0;while (1) {int k = ans[pos], cnt = 0;ans[pos] = (k & 1);k >>= 1;while (k) {cnt++;//2^cntif (k & 1) {if (cnt % 2 == 0) {//2^2kans[pos + 4 * cnt / 2];ans[pos + 4 * cnt / 2]++;highid=max(highid,pos + 4 * cnt / 2);}else {if (cnt / 2 == 0) {//2^1if (ans[pos + 2] % 2 == 0) {ans[pos + 4];ans[pos + 4] += 1;ans[pos + 2] += 1;highid=max(highid,pos + 4);}else {ans[pos + 2] -= 1;highid=max(highid,pos + 2);}}else {//2^2k+1ans[pos + cnt / 2 * 4];ans[pos + cnt / 2 * 4] += 2;highid=max(highid,pos + cnt / 2 * 4);}}}k >>= 1;}if (pos == highid)break;pos++;}int st = pos;per(i, pos, 0){if (ans[i] != 0){st = i;break;}}if(st==pos&&ans[pos]==0){cout<<0<<'\n';return;}per(i, st, 0)cout << ans[i];cout << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);ll t = 1;cin >> t;while (t--) {eachT();}
}