CF506E Mr. Kitayuta's Gift 题解

Tag

动态规划，字符串。

Description

给定一个字符串 \(S\)，往 \(S\) 里面随便塞 \(n\) 个字符，求最后的字符串为回文串的方案数。

\(\texttt{data range:} n\leq 10^9, |S| \leq 200\).

Solution

神题。

假设此时 \(|S| + n\) 为偶数，方便我们进一步分析。

对于一个回文串而言，我们可以先对称构造出来，然后观察源字符串 \(S\) 是不是这个字符串的一个子串。

我们设 \(f_{i,l,r}\) 表示放第 \(i\) 个字符，\(S[l, r]\) 最多能匹配多少个，十分容易转移。

这样可以做到 \(O(n|S|^2)\)，显然是过不去的，然而我们可以用矩阵优化到 \(O(|S|^6\lg(n+|S|))\)，在这里引入了矩阵。

不过时间复杂度还是错误的，因为我们有 \(O(|S|^2)\) 个状态。对于一般动态规划问题，这个时候我们就需要找到一个压缩状态的方法了。

我们发现实际上其转移非常少，因为一个状态到另一个状态的转移只有可能有 \(O(1)\) 种。

但是对此我们还是没有很好的方法进行压缩转移，因为这实在是太困难了，还是要优化我们的状态。

这个时候引入一个非常玄学的概念，那就是状态中有两种点，一种是左右两边相同的点，一种是左右两边不同的点，特殊的，我们 \([i,i]\) 这样的点也是两个相同的点，我们定义前者为绿点，后者为红点，这里可以参考中给到的图进行理解。

如果一条链上有 \(k\) 个红点，那么这条链上一定有 \(\left\lceil\dfrac{|S|-k}{2}\right\rceil\) 个绿点。

证明：一个红点的时候我们一定只能消掉一个点，使其长度减一，那么剩下的长度一定是绿点消掉的，而且绿点一次消俩，不过要考虑 \([i,i]\) 的特殊情况，所以是向上取整。

我们容易分析，如果一条链上有 \(k\) 个红点，那么这两条链的转移状态是完全一致的，可以压缩起来。

分析到了这里，我们可以重新设计状态了，设 \(f_{i,l,r}\) 为从 \([1,|S|]\) 走到 \([l,r]\) 需要走过 \(i\) 个红点，这个过程可以用区间 dp 或者记忆化搜索完成，不多细说。

此时我们的复杂度来到一个比刚刚低很多的级别 \(O(|S|^4\lg(n + |S|))\)，有没有卡常大师可以试一下这个玩意过不过的去啊。

所以还是不够的，我们需要将这个状态压缩到 \(O(|S|)\) 级别。红点和绿点有分歧，那么可以将红点分别构造，绿点分别构造，然后连红点到绿点的边就可以了，不难想到红点最多只有 \(O(|S|)\) 个，绿点最多只有 \(O(|S|)\) 个，我们整体的状态数就来到了 \(O(|S|)\) 这个级别，实际上这个状态数大概是 \(\dfrac 32 |S|\) 个，所以可以过掉本题，时间复杂度 \(O(|S|^3\lg (|S|+n))\)。

\(|S|+n\) 为奇数的情况可以限定红点只能转移到形如 \([i,i]\) 的绿点上，然后用一开始的答案减去这部分就可以了。

本题考察了矩阵快速幂优化 dp 和状态压缩的种种技巧，虽然是出现在 CF 比赛中，但是非常有 OI 比赛的风格，希望这种题目多来点。

Code

const int N = 2e2 + 10;
const int M = 3e2 + 10;

int n, m, lim;
modint f[N][N][N], g[N];
char s[N];

struct Matrix {
    modint a[M][M];
    inline void init() { FOR(i, 0, M - 1) FOR(j, 0, M - 1) a[i][j] = 0; }
    modint *operator [] (const int x) {return a[x];}
    Matrix operator * (Matrix &tem) {
        Matrix ret;
        FOR(i, 0, lim) FOR(j, i, lim) FOR(k, i, j)
            ret[i][j] += a[i][k] * tem[k][j];
        return ret;
    }
    friend ostream &operator << (ostream &ou, const Matrix x) {
        FOR(i, 0, lim) FOR(j, 0, lim) ou << x.a[i][j] << " \n"[j == jj];
        return ou;
    }
    
} S, T;

void KSM(int y) {
    for(; y; y >>= 1, T = T * T)
        if(y & 1) S = S * T;
}

inline void solve() {
    cin >> (s + 1) >> m;
    n = strlen(s + 1);
    f[1][n][0] = 1;
    FOR(i, 1, n) ROF(j, n, i) {
        if(s[i] == s[j]) {
            FOR(k, 0, i + n - j - 1) {
                if(i + 1 < j) f[i + 1][j - 1][k] += f[i][j][k];
                else g[k] += f[i][j][k];
            }
        } else {
            FOR(k, 0, i + n - j - 1) {
                f[i + 1][j][k + 1] += f[i][j][k];
                f[i][j - 1][k + 1] += f[i][j][k];
            }
        }
    }
    lim = n + (n + 1) / 2 + 1;
    S.init(), T.init();
    S[0][1] = 1, S[0][lim - (n + 1) / 2] = g[0], T[lim][lim] = 26;
    FOR(i, 1, n) {
        T[i][i] = 24, T[i][lim - (n - i + 1) / 2] = g[i];
        if(i != n) T[i][i + 1] = 1;
    }
    FOR(i, n + 1, lim - 1) T[i][i + 1] = 1, T[i][i] = 25;
    KSM((n + m + 1) >> 1);
    modint ans = S[0][lim];
    if((n + m) & 1) {
        S.init(), T.init();
        FOR(i, 0, n) g[i] = 0;
        FOR(i, 0, n - 1) if(s[i] == s[i + 1]) FOR(k, 0, n)
            g[k] += f[i][i + 1][k];
        S[0][1] = 1, S[0][lim - (n + 1) / 2] = g[0];
        FOR(i, 1, n) {
            T[i][i] = 24, T[i][lim - (n - i + 1) / 2] = g[i];
            if(i != n) T[i][i + 1] = 1;
        }
        FOR(i, n + 1, lim - 1) T[i][i + 1] = 1, T[i][i] = 25;
        KSM((n + m + 1) >> 1);
        cout << ans - S[0][lim] << '\n';
    } else cout << ans << '\n';
    return ;
}

Final

卡常技巧：由于我们的转移矩阵是一个上三角矩阵，所以可以只枚举上半部分就可以了。