分析

我们发现，对于一个序列进行旋转操作，其实可以等同于只对一个序列进行操作。然后加上改变量所以题意其实就是要我们求 。 我们先把中间的式中拆开 。变成了这个式子。那么我们可以考虑枚举 。那么现在就只有 是没法很快求出来的了。可以令一个数组 ，保证 ，那么现在，就是要求 ，这个就是个标准的卷积形式了。我们把 破环成链。现在就只需要让 做一次多项式乘法就好了。那我们取那一部分的答案呢？ 考虑到我们是把 倍长了的。所以我们实际需要的答案应该在 到 这些项中去寻找。其实可以不用枚举 ，因为我们已经转换为一个二次函数了，那么我只需要考虑二次函数的对称轴。但是这个不是实数，所以要考虑 和 。两个可能的最优解。如果要枚举 ，那么我们的枚举范围也应该是 ，因为出了这个范围，答案一定会越变越大。最后时间复杂度为 。

小结

像 这类非卷积形式，可以考虑通过翻转序列，来达到构造卷积的形式。

代码

#include<bits/stdc++.h>
using namespace std;
const int p = 998244353,Gi = 3,N = 1e6 + 10;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
}
int A[N],B[N],C[N],L,limit = 1,R[N],n,m,res,resA,resB,ans = 0x3f3f3f3f;
int qpow(int x,int b) {
    int a = 1;for(;b;b>>=1,x = 1LL*x*x%p) {
        if(b&1) a = 1LL * a * x % p;
    }
    return a;
}
void ntt(int *a,int type) {
    for(int i = 0;i < limit;i++) if(i < R[i]) swap(a[i],a[R[i]]);
    for(int mid = 1;mid < limit;mid <<= 1) {
        int wn = qpow(Gi,(p-1)/(mid<<1));
        for(int i = 0;i < limit;i += (mid<<1)) {
            int w = 1;
            for(int j = 0;j < mid;j++,w = 1LL * w * wn % p) {
                int x = a[i + j],y = 1LL * w * a[i + j + mid] % p;
                a[i + j] = (x + y) % p;a[i + j + mid] = (x - y + p) % p;
            }
        }
    }
    if(type == -1) {
        int inv = qpow(limit,p - 2);
        reverse(a+1,a+limit);
        for(int i = 0;i < limit;i++) a[i] = 1LL * a[i] * inv % p;
    }
}
int main()
{
    n = read();m = read();
    for(int i = 1;i <= n;i++) A[i] = read();
    for(int i = 1;i <= n;i++) B[i] = read();
    for(int i = 1;i <= n;i++) {
        res += A[i] * A[i] + B[i] * B[i];
        resA += A[i];resB += B[i];
    }
    for(int i = 1;i <= n;i++) {
        C[i + n] = C[i] = A[i];
    }
    reverse(B+1,B+n+1);
    while(limit <= n+n+n) limit <<= 1,L++;
    for(int i = 0;i < limit;i++) R[i] = (R[i >> 1] >> 1)|((i & 1) << L - 1);
    ntt(C,1);ntt(B,1);
    for(int i = 0;i < limit;i++) C[i] = (1LL * C[i] * B[i]) % p;
    ntt(C,-1);
//    for(int i = 0;i < limit;i++) cout << C[i] << " ";cout << endl;
    for(int i = 1;i <= n;i++) {
        for(int j = -m;j <= m;j++) {
            ans = min(ans,res+j*j*n+2*j*(resA - resB)-2*(C[i+n]));
        }
    }
    cout << ans << endl;
    return 0;
}