题解：The 2026 ICPC China Zhejiang Province Programming Contest (23rd) PalindromemordnilaP

The 2026 ICPC China Zhejiang Province Programming Contest (23rd) PalindromemordnilaPhttps://qoj.ac/contest/3749/problem/18121

本质是推柿子题。

首先可以发现只需要考虑 $s_i$ 和 $s_{n - i + 1}$ 的关系，做出如下分类讨论：

$\begin{cases} s_i = s_{n - i + 1} \begin{cases} s_i = c \quad \text{Case 1.1} \\ s_i \neq c \quad \text{Case 1.2} \end{cases} \\ \\ s_i \neq s_{n - i + 1} \begin{cases} s_i \neq c \land s_{n - i + 1} \neq c \quad \text{Case 2.1} \\ s_i = c \lor s_{n - i + 1} = c \quad \text{Case 2.2} \\ \end{cases} \end{cases}$

$\textbf{Case 1.1}$ $s_i = s_{n - i + 1} = c$，无论是否修改，都满足回文的条件，因此若要产生贡献，需要在串变为回文前进行修改。

$\textbf{Case 1.2}$ $s_i = s_{n - i + 1} \neq c$，需要成对修改或者不修改。

$\textbf{Case 2.1}$ $s_i \neq s_{n - i + 1}$ 且 $s_i \neq c \land s_{n - i + 1} \neq c$，一定需要均修改才能满足回文的条件，因此一定会产生贡献。

$\textbf{Case 2.2}$ $s_i \neq s_{n - i + 1}$ 且 $s_i = c \lor s_{n - i + 1} = c$，其中不为 $c$ 的字符同情况 $\textbf{Case 2.1}$，而另一个字符同情况 $\textbf{Case 1.1}$。

设一定要修改的字符数量为 $a$，需要成对修改的对数为 $b$，那些本身为 $c$ 的字符的数量为 $c$。注意 $i = n - i + 1$ 的情况需要特殊处理。

设 $f_i$ 表示恰好修改完第 $i$ 对字符后满足回文条件的方案数，其中 $i \in [0, b]$。如果直接进行排列，方案数为 $(2i + a)!$，当然还需要进行容斥，因为一旦在修改完某个字符后变为回文串，则后续的修改就不再产生贡献，可以任意排列。则有

$f_i = (2i + a)! - \sum \limits_{j = 0}^{i - 1} f_j \cdot \binom{i}{j} [2(i - j)]!$

其中 $f_0 = a!$。当然，在计数的时候需要考虑是哪 $i$ 对字符被修改，以及后续不产生贡献的哪些字符，因此 $f_i \leftarrow f_i \cdot \binom{b}{i} \cdot [2(b - i)]!$。总共的方案数是 $(2b + a)!$，故这部分的期望为

$\sum \limits_{i = 0}^{b} \frac{f_i}{(2b + a)!} \cdot (2i)$

再来考虑那些本身为 $c$ 的字符的贡献，每个字符间相互独立，因此可以得到总期望贡献为 $p \cdot \mathbb{E}$。对于每个字符来说，相当于一共会有 $2b + a + 1$ 个位置可以放置，枚举 $i$ 表示是恰好在修改完第 $i$ 对字符后满足回文，则对应的期望为

$\mathbb{E} = \sum \limits_{i = 0}^b\frac{F_i}{(2b + a)!} \cdot \frac{2i + a + 1}{2b + a + 1}$

最后还需要加上肯定需要修改的字符，贡献为 $a$。

于是我们得到了一个 $O(n^2)$ 的解法，瓶颈在于计算 $f_i$，因此考虑优化这个式子。

$\begin{align*} f_i &= (2i + a)! - \sum \limits_{j = 0}^{i - 1} f_j \cdot \frac{i!}{j!(i - j)!} \cdot [2(i - j)]! \\ &= (2i + a)! - \sum \limits_{j = 0}^{i - 1} \frac{f_j}{j!} \cdot \frac{[2(i - j)]!}{(i - j)!} \cdot i! \\ \implies \frac{f_i}{i!} &= \frac{(2i + a)!}{i!} - \sum \limits_{j = 0}^{i - 1} \frac{f_j}{j!} \cdot \frac{[2(i - j)]!}{(i - j)!} \end{align*}$

令 $F_i = \frac{f_i}{i!}$，$G_i = \frac{(2i)!}{i!}$，$H_i = \frac{(2i + a)!}{i!}$，则有

$F_i = H_i - \sum \limits_{j = 0}^{i - 1} F_j \cdot G_{i - j}$

又因为 $G_0 = 0$，所以 $F_i + \sum \limits_{j = 0}^{i - 1} F_j \cdot G_{i - j} = \sum \limits_{j = 0}^{i} F_j \cdot G_{i - j} = H_i$，则有 $F= H \cdot G^{-1}$。因此我们优化到了 $O(n \log n)$ 的时间复杂度。

当然，这种半在线卷积的形式，可以直接用分治 NTT 来计算 $F$。具体的核心代码如下，时间复杂度 $O(n \log^2 n)$。

vector <int> G(b + 1), F(b + 1);
for (int i = 0; i <= b; ++i) G[i] = 1ll * frac[2 * i] * inv[i] % MOD, F[i] = 1ll * frac[2 * i + a] * inv[i] % MOD;
auto cdq = [&] (auto self, int l, int r) -> void
{
    if (l == r) return;
    int mid = (l + r) >> 1;
    self(self, l, mid);
    vector <int> A(mid - l + 1), B(r - l + 1);
    for (int i = 0; i < mid - l + 1; ++i) A[i] = F[l + i];
    for (int i = 0; i < r - l + 1; ++i) B[i] = G[i];
    auto C = calc.Conv(A, B);
    for (int i = mid + 1; i <= r; ++i) F[i] = (F[i] - C[i - l] + MOD) % MOD;
    self(self, mid + 1, r);
};
cdq(cdq, 0, b);

单只 $\log$ 做法的核心代码如下：

NTT calc;
char s[MAX], ch[2];
void solve()
{
    scanf("%s%s", s + 1, ch + 1);
    int n = strlen(s + 1), a = 0, b = 0, p = 0;
    // a must change    b (pairs) change should be pair   p careless
    for (int i = 1; i <= (n + 1) / 2; ++i)
    {
        if (i == n - i + 1) {++p; continue;}
        if (s[i] == s[n - i + 1])
        {
            if (s[i] == ch[1]) p += 2;
            else ++b;
        }
        else
        {
            if (s[i] == ch[1] || s[n - i + 1] == ch[1]) ++p, ++a;
            else a += 2;
        }
    }
    if (!a) {puts("0"); return;}
    vector <int> frac(n + 1, 1), inv(n + 1, 1);
    int ans = 0, tot = 0;
    auto qpow = [&] (int x, int y) -> int
    {
        int res = 1;
        while (y)
        {
            if (y & 1) res = 1ll * res * x % MOD;
            x = 1ll * x * x % MOD;
            y >>= 1;
        }
        return res;
    };
    auto comb = [&] (int x, int y) -> int {return x < y ? 0 : 1ll * frac[x] * inv[y] % MOD * inv[x - y] % MOD;};
    for (int i = 1; i <= n; ++i) frac[i] = 1ll * frac[i - 1] * i % MOD;
    inv[n] = qpow(frac[n], MOD - 2);
    for (int i = n - 1; i >= 1; --i) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
    // for (int i = 0; i <= b; ++i)
    // {
    //     F[i] = frac[2 * i + a]; 
    //     for (int j = 0; j < i; ++j) F[i] = (1ll * F[i] - 1ll * comb(i, j) * F[j] % MOD * frac[2 * (i - j)] % MOD + MOD) % MOD;
    // }
    vector <int> A(b + 1), B(b + 1);
    for (int i = 0; i <= b; ++i) A[i] = 1ll * frac[2 * i] * inv[i] % MOD, B[i] = 1ll * frac[2 * i + a] * inv[i] % MOD;
    auto C = calc.Inv(A, b + 1);
    auto F = calc.Conv(B, C);
    for (int i = 0; i <= b; ++i) F[i] = 1ll * F[i] * frac[i] % MOD;
    for (int i = 0; i <= b; ++i) F[i] = 1ll * F[i] * comb(b, i) % MOD * frac[2 * (b - i)] % MOD, tot = (tot + F[i]) % MOD;
    assert (tot == frac[2 * b + a]);
    for (int i = 0; i <= b; ++i) ans = (ans + 2ll * i * F[i] % MOD * inv[2 * b + a] % MOD) % MOD;
    for (int i = 0; i <= b; ++i)
        ans = (ans + 1ll * F[i] * p % MOD * (a + 2 * i) % MOD * qpow(a + 2 * b + 1, MOD - 2) % MOD * inv[2 * b + a] % MOD) % MOD;
    ans = (ans + a) % MOD;
    printf("%d\n", ans);
}
int main()
{
    int t = 1;
    while (t--) solve();
    return 0;
}