自动搬运

查看原文

来自洛谷，原作者为

	ModestCoder_ 这个家伙不懒，但还是什么也没有留下

搬运于2025-08-24 21:28:44，当前版本为作者最后更新于2019-09-08 15:52:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先转化问题

$\sum a_i^2$可以换一种理解方式

两个人在两个独立的装置里取球，输出队列相同的方案数

因为对于每一种输出队列，第一个人有$a_i$种方案，第二个人有$a_i$种方案

那么两个人输出队列相同的方案总数就是$a_i^2$

然后就是一个很简单的dp题目了

$dp_{k,i,j}$表示两个人到目前为止都各取了$k$个球，第一个人在第一根管道取了$i$个球，第二个人在第一根管道取了$j$个球，两个人的输出队列相同的方案数 然后已知答案就是$dp_{n+m,n,n}$

然后思考如何转状态转移，根据dp状态的定义，当目前两个人取的球的个数相同才可能发生转移，然后讨论两个人当前从那根管道取的球

• $a_i=a_j:dp_{k,i,j}<-dp_{k-1,i-1,j-1}$
• $a_i=b_{k-j}:dp_{k,i,j}<-dp_{k-1,i-1,j}$
• $b_{k-i}=a_j:dp_{k,i,j}<-dp_{k-1,i,j-1}$
• $b_{k-i}=b_{k-j}:dp_{k,i,j}<-dp_{k-1,i,j}$

注意一下细节就行了

最后考虑时空间的复杂度，时间上$O(n^3)$没毛病

空间上有那么一点问题，但是看到第一维可以滚动掉，放心了

Code：

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define maxn 510
using namespace std;
const int qy = 1024523;
int n, m, a[maxn], b[maxn], dp[2][maxn][maxn];

int get(){
	char c = getchar();
	for (; c != 'A' && c != 'B'; c = getchar());
	return c == 'A';
}

void upd(int &x, int y){ if ((x += y) >= qy) x -= qy; }

int main(){
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) a[i] = get();
	for (int i = 1; i <= m; ++i) b[i] = get();
	reverse(a + 1, a + 1 + n);
	reverse(b + 1, b + 1 + m);
	dp[0][0][0] = 1;
	for (int k = 1; k <= n + m; ++k){
		int now = k & 1, pre = now ^ 1;
		for (int i = 0; i <= n; ++i)
			for (int j = 0; j <= n; ++j) dp[now][i][j] = 0;
		for (int i = max(0, k - m); i <= min(n, k); ++i)
			for (int j = max(0, k - m); j <= min(n, k); ++j){
				if (i && j && a[i] == a[j]) upd(dp[now][i][j], dp[pre][i - 1][j - 1]);
				if (i && k - j && a[i] == b[k - j]) upd(dp[now][i][j], dp[pre][i - 1][j]);
				if (j && k - i && b[k - i] == a[j]) upd(dp[now][i][j], dp[pre][i][j - 1]);
				if (k - i && k - j && b[k - i] == b[k - j]) upd(dp[now][i][j], dp[pre][i][j]);
			}
	}
	printf("%d\n", dp[(n + m) & 1][n][n]);
	return 0;
}