题解：P12837 [蓝桥杯 2025 国 B] 近似回文字符串

· · 题解

思路

令 S_1 表示满足条件 2 的字符串集合，令 S_2 表示满足条件 2 但是不满足条件 1 的字符串集合。

于是答案即为 S_1-S_2。

而 S_2 中的字符串，满足自身是回文串，并且存在一个字符使得删除它后，仍然是回文串。容易验证，所有回文串都满足该条件。于是 |S_2| = 26^{\lceil \frac{n}{2} \rceil}。

考虑如何计算 |S_1|。每次只允许在其两侧加入新的字母。

构造 1：如果字符串 s\in S_1，那么在两边加入相同字母仍然满足条件。

构造 2：如果 s 是一个回文串，那么在左侧或者右侧加入字母也能使它满足条件。

但是两个构造中会出现重复统计的情况。

例如 \texttt{abccba}，左侧添加字母 \texttt{a} 变成 \texttt{aabccbaa}，同时这也可以由 \texttt{abccb} \in S_1 两侧添加 \texttt{a} 得到。可以得出，构造 2 中如果添加的字母与另一侧相同，那么都可以用构造 1 构造出来。所以去掉这种情况，每次只能添加其余 25 种字母。

再考虑到构造 2 中，如果左侧和右侧加入字母都能满足条件，那么便重复统计了，再减去即可。可以发现，这样的字符串只能是 \texttt{aaaaa} 或者 \texttt{ababab} 类型。而对于前者，由于构造 2 中没有这种情况（它的两侧字母相同，在构造 1 中被统计了），所以不需要减去它。

于是递推得到 dp_i = 26\cdot dp_{i-2} +2\cdot25 \cdot26^{\frac{i}{2}} - [i\bmod 2=0]25\cdot 26，答案即为 dp_n - 26^{\lceil\frac{n}{2}\rceil}。其中 dp_0 = 1，dp_1 = 26。

优化

可以化为 O(1) 的式子。

对于奇数项，dp_{2k+1} = dp_{2k-1}\cdot 26 + 50 \cdot 26^{k}，可以得到 \frac{dp_{2k+1}}{26^k} = 26 + 50\cdot k，于是 dp_{2k+1} = 26^k(50k + 26)，答案即为 26^{\lfloor \frac{n}2\rfloor} (50 \lfloor \frac{n}2\rfloor + 26) - 26^{\lceil \frac{n}{2} \rceil}=50\cdot 26^{\lfloor \frac{n}2\rfloor} \cdot \lfloor \frac{n}2\rfloor。

对于偶数项，dp_{2k} = dp_{2k-2}\cdot 26 + 50\cdot 26^{k}- 650，这是一个线性非齐次递推，不难得出 dp_{n} = 25(n-1)26^{\frac{n}{2}} + 26，答案即为 (25n-26) 26^{\frac n2} + 26。

AC 代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long 
#define endl '\n'

const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
int pw[N];
void Prework(const int n = N - 10) {
    pw[0] = 1;
    for (int i = 1;i <= n;i++) pw[i] = pw[i - 1] * 26 % MOD;
}
int baoli(int n) {
    string s;
    vector<string> a;
    auto dfs = [&](auto&& dfs, int u) {
        if (u == n + 1) {
            string t = s;
            reverse(t.begin(), t.end());
            if (t == s) a.push_back(s);
            // a.push_back(s);
            return;
        }
        for (char i = 'a';i <= 'z';i++) {
            s += i;
            dfs(dfs, u + 1);
            s.pop_back();
        }
        };
    dfs(dfs, 1);
    set<string> st;
    int res = 0;
    for (auto i : a) {
        for (int j = 0;j < n;j++) {
            string t = i.substr(0, j) + i.substr(j + 1);
            string tt = t;
            reverse(tt.begin(), tt.end());
            if (tt == t) {
                res += 1;
                break;
            }
        }
    }
    return res;
}
void Solve() {
    int n;cin >> n;
    // cout << baoli(n) << endl;
    vector<int> dp(n + 1);
    dp[0] = 1;
    dp[1] = 26;
    for (int i = 2;i <= n;i++) {
        int ans1 = dp[i - 2] * 26 % MOD;
        int ans2 = pw[i / 2] * 25 * 2 % MOD;
        int ans3 = i % 2 ? 0 : 25 * 26;
        dp[i] = (ans1 + ans2 - ans3 + MOD) % MOD;
    }
    cout << (dp[n] - pw[(n + 1) / 2] + MOD) % MOD << endl;
    // if (n & 1) {
    //     cout << pw[n / 2] * 50 * (n / 2) % MOD << endl;
    // }
    // else {
    //     cout << ((25 * n - 26) * pw[n / 2] % MOD + 26) % MOD;
    // }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T = 1;
    // cin >> T;
    Prework();
    while (T--) Solve();
}