Problem Statement

You are given a sequence of $N−1$ integers $S=(S_1,S_2,…,S_{N−1})$, and $M$ distinct integers $X_1,X_2,…,X_M$, which are called lucky numbers.

A sequence of $N$ integers $A=(A_1,A_2,…,A_N)$ satisfying the following condition is called a good sequence.

$A_i+A_{i+1}=S_i$ holds for every $i=1,2,…,N−1$.

Find the maximum possible number of terms that are lucky numbers in a good sequence $A$, that is, the maximum possible number of integers $i$ between $1$ and $N$ such that $A_i∈{X_1,X_2,…,X_M}$.

Constraints

$2≤N≤10^5$
$1≤M≤10$
$−10^9≤S_i≤10^9$
$−10^9≤X^i≤10^9$
$X_1<X_2<⋯<X_M$
All values in input are integers.

$只要确定A_1，后面的数都会被确定，设A_1=Z，有$
$A_i=S_{i-1}-A_{i-1}=(-1)^{i+1}Z+B_i$
$其中B=(B_1,B_2,…,B_N)，B_i=\begin{cases}S_{i-1}-B_{i-1},& i\geqslant 2 \\\0, & i=1\end{cases}$
$如果枚举每个可能的A_1，计算出对应的答案的时间复杂度为10^9，不太可能完成$
$这里又要用到最经典的逆向思维，正向不能求出答案，反向考虑当每个位置i是幸运数字X_j的时候，它$
$对哪个Z会有贡献，令A_1=Z时，幸运数字+1，最后枚举所有贡献不为0的A_1，取最大值就是答案$
$当A_i=X_j，有A_i=(-1)^{i+1}Z+B_i=X_j，Z=(-1)^{i+1}(X_j-B_i)$

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;

const int N = 2e5 + 10, INF = 1e8;
const int mod = 998244353;

int n, m;
int s[N], x[N];
ll b[N];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i < n; i ++ ) scanf("%d", &s[i]);
    for (int i = 1; i <= m; i ++ ) scanf("%d", &x[i]);

    for (int i = 2; i <= n; i ++ ) b[i] = s[i - 1] - b[i - 1];

    unordered_map<ll, ll> mp;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
        {
            ll c = x[j] - b[i];
            if (i % 2 == 0) c *= -1;
            mp[c] ++ ;
        }

    ll ans = 0;
    for (auto it: mp) ans = max(ans, it.second);
    printf("%lld\n", ans);
    return 0;
}