解析
设
x
,
y
∈
B
,
x
<
y
x,y\in B,x<y
x,y∈B,x<y,那么也有
x
−
y
∈
B
x-y\in B
x−y∈B。
递归下去,根据辗转相减求
gcd
\gcd
gcd 的方法可知,最终会得到
gcd
(
x
,
y
)
\gcd(x,y)
gcd(x,y)。
那么对于整个集合
B
B
B ,它也就等价于所有元素的
gcd
\gcd
gcd,设为
g
g
g。
这样,我们就把多个元素转化为了单一元素的问题。
构造一个数列
b
1...
n
b_{1...n}
b1...n,如果最后
a
i
a_i
ai 乘了
−
1
-1
−1,
b
i
=
1
b_i=1
bi=1,反之为
0
0
0。
设
f
x
=
⊕
i
%
g
=
x
b
i
,
x
∈
[
0
,
g
−
1
]
f_{x}=\oplus_{i\%g=x}b_i,x\in[0,g-1]
fx=⊕i%g=xbi,x∈[0,g−1]。那么初始的
f
f
f 均为
0
0
0,每次操作,所有的
f
f
f 都会异或
1
1
1,所以无论如何变换,所有的
f
x
f_x
fx 都是相等的。
同时,我们也可以通过变换得到任意一个
f
x
f_x
fx 相等的局面,所以
f
x
f_x
fx 均为 0/1 是一个序列合法的等价条件。
利用这个性质简单 dp 即可。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read(){
ll x(0),f(1);char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
const int N=2e6+100;
const int M=1e6+100;
int n,m;
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
int g;
int a[N];
ll dp[N][2];
void work(){
n=read();m=read();g=0;
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<=m;i++) g=gcd(g,(int)read());
for(int i=1;i<=g;i++){
dp[i][0]=a[i];dp[i][1]=-a[i];
}
for(int i=g+1;i<=n;i++){
dp[i][0]=max(dp[i-g][0]+a[i],dp[i-g][1]-a[i]);
dp[i][1]=max(dp[i-g][1]+a[i],dp[i-g][0]-a[i]);
}
ll x(0),y(0);
for(int i=n-g+1;i<=n;i++){
x+=dp[i][0];y+=dp[i][1];
}
printf("%lld\n",max(x,y));
}
signed main(){
#ifndef ONLINE_JUDGE
//freopen("a.in","r",stdin);
//freopen("a.out","w",stdout);
#endif
int T=read();
while(T--) work();
return 0;
}
/*
*/
/*
*/