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\)
打表观察：
发现明显规律且周期\(T=4\)
设\(a=\sqrt{ -2 }\)，则必有\(2^2\times a^p=a^{p+4}\)
进一步推广：
现在解决了\(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\)
则有：
这样就能不断地将系数向高次推推推，最终全部推成\(\{ 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
代码实现
#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();}
}