CSP模拟3

白简の博客 / 2023-07-23 / 原文

A. 回文

\(20\) 多分的纯暴力搜索，\(A_{i,j} = A_{i-1,j+1}\) 可以判完回文直接递推出路径数，共 \(42 \text{pts}\)。

正解 \(DP\)。

回文可以转化一下思路，两个人分别从 \((1,1),(n,m)\) 出发，走的路径相同的方案数。

设计 \(dp[i][j][s][t]\) 为第一个人在 \((i,j)\) 位置，第二个人在 \((s,t)\) 位置的方案数。

转移要注意步数相同，即 \(i + j - 2 = n + m - s - t\)。

因为我们每走一步会使你的坐标 \(x + y\) 加上 \(1\)，又因为我们坐标都是从 \(1\) 开始的，所以第一个人路径长度就是 \(x + y - 2\)。

第二个人由于是从 \(n + m\) 开始，不太一样。

所以就可以压掉一维，\(t = n + m + 2 - s - i - j\)（好长）。

最后要考虑一下回文有两种情况，一种是长度为奇数，即最后两个人走到同一个位置；另一种长度为偶数，即二者相邻的状态，这种要考虑两种相邻的情况（上下和左右）。

这个思路来自sandom学长的博客，稍微解释地详细了一下。

这道题最坑的就是模数 \(993244853\)！！！！！！

注意，全开 \(long \ long\) 会 \(\text{MLE}\)，要中途计算时用 \(long \ long\) 的临时变量。

Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>

using namespace std;

const int N = 505;
const int Mod = 993244853;

int n,m;

char a[N][N];

int dp[N][N][N];
long long ans;

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= m; j++)
            cin >> a[i][j];
    if(a[1][1] == a[n][m])
        dp[1][1][n] = 1;
    else {
        cout << "0";
        return 0;
    }
    for(int i = 1;i <= n; i++) {
        for(int j = 1;j <= m; j++) {
            for(int s = n;s >= 1; s--) {
                int t = n + m + 2 - i - j - s;

                if(t < 1 || t > m)
                    continue;
                
                ans = dp[i][j][s];
                if(a[i][j] == a[s][t])
                    ans = ans + dp[i - 1][j][s + 1] + dp[i - 1][j][s] + dp[i][j - 1][s + 1] + dp[i][j - 1][s];
                dp[i][j][s] = ans % Mod;
            }
        }
    }

    ans = 0;

    for(int i = 1;i <= n; i++) {
        for(int j = 1;j <= m; j++) {
            int s,t;

            s = i,t = j;
            if(i + j + s + t == n + m + 2)
                ans += dp[i][j][s];

            s = i + 1,t = j;
            if(i + j + s + t == n + m + 2)
                ans += dp[i][j][s];
            
            s = i,t = j + 1;
            if(i + j + s + t == n + m + 2)    
                ans += dp[i][j][s];

            ans %= Mod;
        }
    }

    cout << ans;
    return 0;
}