题解：P6297 替换

前置知识

1. 对数基本性质。
2. 中心扩展算法。（好像是这么叫的）
3. 回文串的基本处理方法。

   分析

   一看 n \leq 1000 就知道可以暴力水过去。

由于奇偶串很麻烦，所以我进行一个简单的变化，将所有偶串变为奇串。就是在原数组所有的相邻元素之间放一个 1。既不改变答案，又能将所有偶串变为奇串。举个例子：

图中偶串“3，4，4，3”被转换成了奇串“3，1，4，1，4，1，3”。这样方便很多。

但是 “最大值” 这个条件有点棘手，高精度碾过去貌似会超时，所以需要取对数。\log(a \times b) = \log(a) + \log(b)。因此在乘的时候可以很方便的记录一下对数，根据对数的大小比较就可以了。最后再取模。

因此，第一步需要枚举中心。 然后中心扩展，如果两边不一样，增加一次更改次数，如果超过了 k 就剪枝掉。在中心扩展的过程中，同时记录乘积取模、乘积取对数。 最后根据对数值比较大小，更新答案。

代码

// Author: chenly8128
// Created: 2024-11-14 22:13:46

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
inline int read(void) {
    int res = 0;bool flag = true;char c = getchar();
    while (c < '0' || c > '9') {flag ^= (c == '-');c = getchar();}
    while (c >= '0' && c <= '9') {res = (res << 3) + (res << 1) + (c ^ 48);c = getchar();}
    return flag ? res : -res;
}
int n,k,a[2002];
int main (void) {
    n = read();k = read();
    for (int i = 0;i < n;i++) {
        a[(i<<1)+1] = read();
        a[(i<<1)+2] = 1;
    }
    n = (n<<1)-1;
    ll ans = 1;long double rr = 0;
    for (int i = 1;i <= n;i++) {
        ll sum = 0,res = a[i];
        long double res2 = log(a[i]);
        for (int j = 1;j <= min(i-1,n-i);j++) {
            if (a[i-j] != a[i+j] && ++sum > k) break;
            res = res * a[i-j] % mod * a[i+j] % mod;
            res2 += log(a[i-j]) + log(a[i+j]);
        }
        if (res2 > rr) {
            rr = res2;
            ans = res;
        }
    }
    printf ("%lld\n",ans);
    return 0;
}