P16600 [SYSUCPC 2025] Perfect Life 题解

有点 /bb 啊。

设 。首先容易想到 DP，即设 表示 的后缀是 ， 的前缀是 ，是否存在 。注意到 ，因此猜测正解可能是在暴力 DP 的基础上压位去掉一维。

这东西具体怎么实现呢？因为 与 是相对独立的，只需要用 和 判断一下是否有 ，记作 ，剩下的就是 和 独立的转移了。两者本质相同，这里讨论 的转移。

定义 时有 。讨论一下合法的 ：

• ：即当前位置不被覆盖，有 。
• ：因为当前位置是 的开头，所以可以覆盖之前的 ，有 。把 DP 值的或和处理出来，令 ，那么有 。
• ：除了 的情况，还有可能上个位置被之后的 覆盖了，因此 。

把 这一维压掉，考虑怎么转移。 的情况可以直接移位，其它情况都可以特判掉。记 表示 。具体地：

• ，临时令 ，即 （说人话就是 dp[i][j] |= (dp[i - 1][j'] ^ (dp[i - 1][j'] & 1)) << 1）。
• 若 ，那么 ，即 。
• 若 ，那么 ，即 。
• 若 ，那么 ，即 。

上面的 DP 只用做到 。设 ，定义左侧表示 ，右侧表示 。考虑答案是怎么求，有以下几种情况：

• 左侧的最后一次操作与右侧的最后一次操作是同一个操作，即 。
• 左侧先于右侧操作，那么右侧的最后一次操作不能影响左侧，即 。
• 右侧先于左侧操作，那么左侧的最后一次操作不能影响右侧，即 。
• 注意上面的情况都钦定了有操作影响 或 ，因此还要特判一下 的情况。

做完了，时间复杂度 ，准确来说是 ，写出来其实也并没有那么 /bb。

void trans(int i, int j, int k) {
	if((dp[i & 1 ^ 1][k] >> m) & 1) dp[i & 1][j] |= u[t[j]];
	if(dp[i & 1 ^ 1][k] & 1) dp[i & 1][j] |= 1;
	if(dp[i & 1 ^ 1][k]) dp[i & 1][j] |= 2;
	dp[i & 1][j] |= (dp[i & 1 ^ 1][k] ^ (dp[i & 1 ^ 1][k] & 1)) << 1;
}

void solve() {
	cin >> s >> t;
	n = s.size(), m = t.size();
	s = " " + s, t = " " + t + " ";
	dp[0][0] = dp[0][m + 1] = 1ll << (m + 1) | 1;
	rep(i, 1, n >> 1) {
		t[0] = s[i], t[m + 1] = s[n + 1 - i];
		rep(c, 'A', 'Z') u[c] = 0;
		rep(c, 'a', 'z') u[c] = 0;
		rep(k, 0, m) u[t[m + 1 - k]] |= 1ll << k;
		rep(j, 0, m) {
			if(j == 1) trans(i, j, m + 1);
			else trans(i, j, m), trans(i, j, max(j - 1, 0));
			dp[i & 1][j] &= u[t[j]];
			if(dp[i & 1][j]) dp[i & 1][j] |= 1ll << (m + 1);
			dp[i & 1][m + 1] |= dp[i & 1][j];
		}
		rep(j, 0, m + 1) dp[i & 1 ^ 1][j] = 0;
	}
	ans = dp[(n >> 1) & 1][0] & 1;
	rep(j, 0, m) rep(k, 0, m) {
		if(m - j <= (n & 1) or m - k <= (n & 1) or j + k + 1 == m) {
			ans |= (dp[(n >> 1) & 1][j] >> k) & 1;
		}
	}
	if(ans) puts("Yes");
	else puts("No");
	rep(j, 0, m + 1) dp[0][j] = dp[1][j] = 0;
	return;
}