管道取珠【每日一题】5月29日

一.题目链接

$\quad$ 管道取珠

二.题目大意

$\quad$ 原生题目极佳.

图片说明

三.分析

$\quad$ 这道题上来一手转化很妙，学到了~~

$\quad$ 题目中设 a[i] 为最终序列的某种方案数，而让我们求解的却是 $a[i]^2$ ，很明显我们需要找出两者的关系.

$\quad$ 假设我们有两个完全相同且独立的系统，两个人同时进行操作，不难证明，对于某个最终序列 F，两个人操作完成后得到的序列都与 F 相同的方案数即为 $a[i]^2$

$\quad$ 经过这一步转化后，我们就可以愉快进行 dp 辣~~（然鹅并不是...）

$\quad$ 我们设 dp[i][j][k][l] 为第一个人从管道一取了 i 个球，第一个人从管道二取了 j 个球，第二个人从管道一取了 k 个球，第二个人从管道二取了 l 个球，且当前所构成序列相同的方案数.

$\quad$ But，这样的状态表示时空都会爆掉滴. 由于两个序列相同，那么 i + j == k + l，所以我们可以省略一维，除此之外对第一维进行滚动优化，这样就卡进 AC 的时空啦！

$\quad$ 状态转移方程为

if(s[i + 1] == s[k + 1]) f[p^1][j][k + 1] = (f[p^1][j][k + 1] + f[p][j][k]) % mod;
if(s[i + 1] == t[l + 1]) f[p^1][j][k] = (f[p^1][j][k] + f[p][j][k]) % mod;
if(t[j + 1] == s[k + 1]) f[p][j + 1][k + 1] = (f[p][j + 1][k + 1] + f[p][j][k]) % mod;
if(t[j + 1] == t[l + 1]) f[p][j + 1][k] = (f[p][j + 1][k] + f[p][j][k]) % mod;

除此之外呢，还可以加上一点小优化，就像下面这个样纸

if(!f[p][j][k])    continue;
if(s[i + 1] == s[k + 1]) f[p^1][j][k + 1] = (f[p^1][j][k + 1] + f[p][j][k]) % mod;
if(s[i + 1] == t[l + 1]) f[p^1][j][k] = (f[p^1][j][k] + f[p][j][k]) % mod;
if(t[j + 1] == s[k + 1]) f[p][j + 1][k + 1] = (f[p][j + 1][k + 1] + f[p][j][k]) % mod;
if(t[j + 1] == t[l + 1]) f[p][j + 1][k] = (f[p][j + 1][k] + f[p][j][k]) % mod;

$\quad$ 经测试，时限优化了好多好多！！！

四.代码实现

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int M = (int)5e2;
const ll mod = (ll)1024523;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;

int n, m;
char s[M + 5], t[M + 5];
int f[2][M + 5][M + 5];

int main()
{
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    scanf("%d %d", &n, &m);
    scanf("%s %s", s + 1, t + 1);
    reverse(s + 1, s + n + 1); reverse(t + 1, t + m + 1);
    f[0][0][0] = 1;
    for(int i = 0, p = 0; i <= n; ++i, p ^= 1)
    {
        for(int j = 0; j <= m; ++j)
        {
            for(int k = 0; k <= n; ++k)
            {
                int l = i + j - k;
                if(l < 0 || l > m) continue;
                if(!f[p][j][k])    continue;
                if(s[i + 1] == s[k + 1]) f[p^1][j][k + 1] = (f[p^1][j][k + 1] + f[p][j][k]) % mod;
                if(s[i + 1] == t[l + 1]) f[p^1][j][k] = (f[p^1][j][k] + f[p][j][k]) % mod;
                if(t[j + 1] == s[k + 1]) f[p][j + 1][k + 1] = (f[p][j + 1][k + 1] + f[p][j][k]) % mod;
                if(t[j + 1] == t[l + 1]) f[p][j + 1][k] = (f[p][j + 1][k] + f[p][j][k]) % mod;
                f[p][j][k] = 0;
            }
        }
    }
    printf("%d\n", f[(n + 1) & 1][m][n]);
    return 0;
}