题目描述
简要题意：给定一个 $n\times n$ 的矩阵 $a$，$a$ 中每个位置上有一个数。你要从左上角 $(1,1)$ 走到右下角 $(n,n)$，每次只能向下或者向右走。将沿途的格子上的数组依次记录下来，可以得到一个长度为 $2n-1$ 的序列，选择的路线不同，可能会得到不同的序列，要求对于每一个序列 $Q$，计算有多少条路线对应这个序列 $Q$，路线的个数记为 $f(Q)$。求 $\sum f^2(Q)$
$n\le 300$
Solution
首先我们尝试将平方给干掉，假设 $f(Q)$ 为 $x$，那么它的贡献为 $x^2$
我们将其认为对于每条在 $x$ 中的路线，它与其它属于 $x$ 的路线都记一次贡献，那么一共还是 $x^2$ 次
那么我们现在得到了另一种计算贡献的方式，相当于两个人从 $(1,1)$ 走到 $(n,n)$，得到序列相同的走法
这个东西显然可以 $O(n^2)$ $dp$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
#include <cstdio>
#define maxn 310
using namespace std;
int n, a[maxn][maxn];
int dx[] = { 0, 1 };
int dy[] = { 1, 0 };
const int p = 1000000007;
inline int add(int x, int y) { return x + y >= p ? x + y - p : x + y; }
int f[2 * maxn][maxn][maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j) cin >> a[i][j];
f[1][1][1] = 1;
for (int k = 1; k <= 2 * n - 2; ++k)
for (int x1 = 1, y1 = k - x1 + 1; x1 <= min(n, k); ++x1, --y1)
for (int x2 = 1, y2 = k - x2 + 1; x2 <= min(n, k); ++x2, --y2)
for (int i = 0; i < 2; ++i) {
if (y1 < 0 || y1 > n || y2 < 0 || y2 > n) continue;
int X1 = x1 + dx[i], Y1 = y1 + dy[i];
if (X1 > n || Y1 > n) continue ;
for (int j = 0; j < 2; ++j) {
int X2 = x2 + dx[j], Y2 = y2 + dy[j];
if (X2 > n || Y2 > n) continue ;
if (a[X1][Y1] ^ a[X2][Y2]) continue ;
f[k + 1][X1][X2] = add(f[k + 1][X1][X2], f[k][x1][x2]);
}
}
cout << f[2 * n - 1][n][n] << endl;
return 0;
}
|