F题解

对于n个数进行哈希那么题目等价于hash(1,n-2k)+hash(2k+1,n)=2hash(k+1,n-k)

通过o(n)枚举k就可以得出结果

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef unsigned long long ULL;
const int N = 1e6 + 5, P = 131;
ULL p[N], h[N];
ULL find(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<int>a(n);
    p[0] = 1;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        p[i + 1] = p[i] * P;
        h[i + 1] = h[i] * P + a[i];
    }
    for (int k = 1; k <= n; k++) {
        if (find(1, n - 2 * k) + find(2 * k + 1, n) == 2 * find(k + 1, n - k)) {
            cout << k << "\n";
            return 0;
        }
    }
}