题意
定义(F_i)为斐波那契数列第(i)项，(F_1=1, F_2=2, F_i=F_{i-1}+F_{i-2} (i≥3))
已知任意正整数(x)都拥有一个唯一的长度为(n)的(01)数列({b})，使得
(b_1*F_1+b_2*F_2+...+b_n*F_n=x)
(b_n=1)
(b_i∈{0,1})
(b_i*b_{i+1}=0)
以这样的表示法给出(A、B、C)三个数
已知数字(C)是由(A*B)的结果在这样的表示法下将某个原本是(1)的位置改成(0)得来的
问抹去的是哪个位置
数据范围
(1≤T≤10000)
(1≤|A|,|B|≤1000000)
(2≤|C|≤|A|+|B|+1)
(sum|A|,sum|B|≤5000000)
解
根据数据范围，至少要预处理出前(2000001)项的斐波那契数列
并通过(map/unordered\_map/gp\_hash\_table)将值映射回位置
然后根据题目所述，计算出(A)、(B)和(C)的值
其次只要通过(A*B-C)来计算出被抹去的数对应的数字是什么，将映射的位置输出即可
想法理解了之后就只剩处理方法的问题了
首先发现(Fibonacci)数列前(100)项便会超出(long long)的范围，所以需要对其进行取模
我们需要保证这个模数能让(Fibonacci)数列前(2000001)项在取模后没有冲突（唯一性）
所以需要一个比平时见到的模数更大的模数去尝试（类似(998244353、1000000007)这些均有冲突项数）
最后我取了(1111111111139)这个模数（若使用(unsigned long long)可以使用哈希的想法让数自然溢出，应该也是对的）
于是就能预处理+映射求出答案了，详见代码
需要注意的是，模数过大可能会导致计算(A*B)时超出(long long)的范围，所以需要使用快速乘
完整程序（各种优化情况）
由于组数关系及数据范围，所以我们需要考虑应当选取怎样的容器去映射
经（不完全）测试，得到结果如下
| 容器/读入方式 | 赛时测评(ms) | 题库测评(ms) |
|---|---|---|
| map + STDIO | / | TLE |
| unordered_map + STDIO | 2453 | / |
| gp_hash_table + STDIO | 2015 | / |
| unordered_map + FastIO | / | 2698 |
| gp_hash_table + FastIO | 375 | 1107 |
数据过大，快读这题在题库测评时应该是少不了的
其次稍微提一下，如果提交的是(G++)，且需要使用(unordered\_map)类时
如果空间充足，建议使用(gp\_hash\_table)来代替，时间复杂度可以降低(2)~(3)倍，但空间复杂度会提高(1.5)~(2)倍
在实际使用过程中，除了(gp\_hash\_table)无法使用(count)函数外，其余与(unordered\_map)相同
使用方法如下（两个头文件&一个namespace，添加后就能使用了）
下面展示的是(gp\_hash\_table + FastIO)组合的程序
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int bsz=1<<18;
char bf[bsz],*head,*tail;
inline char gc(){
if(head==tail){
int l=fread(bf,1,bsz,stdin);
tail=(head=bf)+l;
}
return *head++;
}
inline int read(){
int x=0,f=1;
char c=gc();
for(;!isdigit(c);c=gc())
if(c=='-')
f=-1;
for(;isdigit(c);c=gc())
x=x*10+c-'0';
return x*f;
}
inline void write(ll x){
if(x>=10)
write(x/10);
putchar(x%10+'0');
}
inline void putd(ll x)
{
write(x);
putchar('
');
}
const ll mod=1111111111139LL;
gp_hash_table<ll,int> mp;
ll fibo[2000050];
ll qmul(ll a,ll b){ //快速乘
ll r=0;
while(b){
if(b&1)
r=(r+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return r;
}
void solve()
{
int cnt1,cnt2,cnt3,d;
ll A=0,B=0,C=0;
cnt1=read();
for(int i=1;i<=cnt1;i++)
{
d=read();
if(d==1)
A=(A+fibo[i])%mod;
}
cnt2=read();
for(int i=1;i<=cnt2;i++)
{
d=read();
if(d==1)
B=(B+fibo[i])%mod;
}
cnt3=read();
for(int i=1;i<=cnt3;i++)
{
d=read();
if(d==1)
C=(C+fibo[i])%mod;
}
putd(mp[(qmul(A,B)-C+mod)%mod]);
}
int main()
{
fibo[0]=fibo[1]=1;
mp[1]=1;
for(int i=2;i<=2000010;i++)
{
fibo[i]=(fibo[i-1]+fibo[i-2])%mod;
mp[fibo[i]]=i;
}
int T=read();
while(T--)
solve();
return 0;
}