HDU 6768 The Oculus

Problem Description

Let’s define the Fibonacci Sequence $f_1,f_2,\cdots$ as $f_1=1,f_2=2,f_i=f_{i−1}+$$f_{i−2} (i\geqslant3)$.
It’s well known that every positive integer $x$ has its unique Fibonacci representation $b_1,b_2,\cdots,b_n$ such that: $b_1×f_1+b_2×f_2+⋯+b_n×f_n=x$; $b_n=1$, and for each $1\leqslant i<n$, $b_i∈\{0,1\}$ always holds; for each $1\leqslant i<n$, $b_i×b_{i+1}=0$ always holds.
For example, $4=(1,0,1)$, $5=(0,0,0,1)$, and $20=(0,1,0,1,0,1)$ because $20=f_2+f_4+f_6=2+5+13$.
There are two positive integers $A$ and $B$ written in Fibonacci representation, Skywalkert calculated the product of $A$ and $B$ and written the result $C$ in Fibonacci representation. Assume the Fibonacci representation of $C$ is $b_1,b_2,\cdots,b_n$, Little Q then selected a bit $k$ $(1\leqslant k<n)$ such that $b_k=1$ and modified $b_k$ to $0$.
It is so slow for Skywalkert to calculate the correct result again using Fast Fourier Transform and tedious reduction. Please help Skywalkert to find which bit k was modified.

Input

The first line of the input contains a single integer $T$ $(1\leqslant T\leqslant10000)$, the number of test cases.
For each case, the first line of the input contains the Fibonacci representation of $A$, the second line contains the Fibonacci representation of $B$, and the third line contains the Fibonacci representation of modified $C$.
Each line starts with an integer $n$, denoting the length of the Fibonacci representation, followed by $n$ integers $b_1,b_2,\cdots,b_n$, denoting the value of each bit.
It is guaranteed that: $1\leqslant |A|,|B|\leqslant 1000000$, $2\leqslant|C|\leqslant|A|+|B|+1$, $∑|A|,∑|B|\leqslant 5000000$.

Output

For each test case, output a single line containing an integer, the value of k.

Sample Input

1
3 1 0 1
4 0 0 0 1
6 0 1 0 0 0 1

Sample Output

4

Idea

斐波那契数列自第 $20$ 项开始就会变得非常大，可以可以考虑计算 $A,B,C$ 时，可以考虑对大数取模。不妨直接定义 $f,A,B,C$ 为 unsigned long long，通过自然溢出，可自动对 $2^{64}$ 取模。
令修改的那一位为 $k$，则要找到这个 $k$ 满足 $A×B \equiv C+f_k\pmod {2^{64}}$ ，其中 $k ≤ 2000001$，遍历 $2000001$ 项斐波那契数列即可找到答案。

Code

/******************************************************************
Copyright: 11D_Beyonder All Rights Reserved
Author: 11D_Beyonder
Problem ID: HDU 6768
Date: 8/10/2020
Description: Hash
*******************************************************************/
#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned long long ull;
const int N=2000003;
ull f[N];
int main()
{
	int i;
	f[1]=1;f[2]=2;
	for(i=3;i<N;i++) f[i]=f[i-1]+f[i-2];
	int _;
	for(cin>>_;_;_--)
	{
		int n;
		short x;
		ull A=0,B=0,C=0;
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%hd",&x);
			A+=x*f[i];
		}
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%hd",&x);
			B+=x*f[i];
		}
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%hd",&x);
			C+=x*f[i];
		}
		for(i=1;i<N;i++)
		{
			if(A*B==C+f[i])
			{
				printf("%d\n",i);
				break;
			}
		}
	}
	return 0;
}