洛谷 P1758 [NOI2009] 管道取珠（DP）

题目链接

https://www.luogu.com.cn/problem/P1758

思路

对于$\sum a_i^2$可以换一种理解方式：两个人在两个独立的管道中取球，输出序列相同的方案数。

因为对于每一种输出序列，第一个人有$a_i$种方案，第二个人有$a_i$种方案，那么两个人输出序列相同的方案总数就是​$\sum a_i^2$。

我们定义$f[k][i][j]$表示两个人都各取了$k$个球，第一个人在上管道取了$i$个球，第二个人在上管道取了$j$个球，两个人的输出序列相同的方案数。最后的答案就是$f[n+m][n][m]$。

因为两个人取的球的数目相同才能发生转移，所以讨论两个人当前从哪个管道中取的球，状态转移方程为：

• $f[k][i][j]+=f[k-1][i-1][j-1]\times (a[i]==a[j])$
• $f[k][i][j]+=f[k-1][i-1][j]\times (a[i]==b[k-j])$
• $f[k][i][j]+=f[k-1][i][j-1]\times (b[k-i]==a[j])$
• $f[k][i][j]+=f[k-1][i][j]\times (b[k-i]==b[k-j])$

时间复杂度：$O(n^3)$

代码

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>using namespace std;constexpr long double pi = static_cast<long double>(M_PI);#define int long long
#define double long double
#define endl "\n"typedef long long i64;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii;const int N = 2e3 + 5, M = 5e3 + 15;
const int mod = 1024523;
const i64 inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-8;std::mt19937 rnd(time(0));int n, m;
char a[N], b[N];
int f[2][N][N];
void solve(int test_case)
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= m; i++){cin >> b[i];}reverse(a + 1, a + 1 + n);reverse(b + 1, b + 1 + m);f[0][0][0] = 1;for (int k = 1; k <= n + m; k++){int idx = k & 1;for (int i = 0; i <= n; i++){for (int j = 0; j <= n; j++){f[idx][i][j] = 0;}}for (int i = max(0LL, k - m); i <= min(n, k); i++){for (int j = max(0LL, k - m); j <= min(n, k); j++){if (i && j && a[i] == a[j]){f[idx][i][j] += f[idx ^ 1][i - 1][j - 1];f[idx][i][j] %= mod;}if (i && k - j && a[i] == b[k - j]){f[idx][i][j] += f[idx ^ 1][i - 1][j];f[idx][i][j] %= mod;}if (k - i && j && b[k - i] == a[j]){f[idx][i][j] += f[idx ^ 1][i][j - 1];f[idx][i][j] %= mod;}if (k - i && k - j && b[k - i] == b[k - j]){f[idx][i][j] += f[idx ^ 1][i][j];f[idx][i][j] %= mod;}}}}cout << f[(n + m) & 1][n][n] << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;// cin >> test;for (int i = 1; i <= test; i++){solve(i);}return 0;
}