套路题
题意
求有多少个 \(1\) 到 \(n\) 的排列满足恰有 \(k\) 对在排列中相邻的数满足前小于后
\(2 \leq n \leq 500, 0 \leq k \leq (n - 1)\)
思路
f[i][j][k] 表示已经放置了前 i 个数， 放置的第 i 个数是前 i 个数中第 j 大的($ 1\leq \(`j`\) \leq$ i )，已放置的前 i 个数形成的所有排列满足恰有 k 对在排列中相邻的数满足前小于后的排列数量。
放置第 i+1 个数时，第 i+1 个数是前 i+1 个数中第 j 大的，第 i 个数是严格小于前 i 个数中第 j 大的，会为排列增加一对相邻的数满足前小于后，第 i 个数是大于等于前 i 个数中第 j 大的，不会为排列增加一对相邻的数满足前小于后，转移方程为：
\[f_{(i + 1) j k} = \sum_{x = 1}^{j - 1}f_{i x (k-1)} + \sum_{x=j}^{i}f_{ixk} \]
显然，后面的和式可以通过前缀和优化的。
时间复杂度为 \(O(n^2k)\) 。
G - Similar Permutation
传送门
题意
求 \(1\) 到 \(n\) 的排列 \(A\) 和 \(B\) 的相似度为 \(k\) 的数量。
相似度计算： \(k = \sum_{i = 2}^{n}[(A_i - A_{i-1})(B_i - B_{i-1}) > 0]\) ( \([X] = 1, X 为真，[X] = 0, X为假\) )。
\(2 \leq n \leq 100, 0 \leq k \leq (n - 1)\) 。
思路
与前一道题相比，这一题只是增加了一维状态。
f[i][a][b][k] 表示排列 \(A\) , \(B\) 已经放置了前 i 个数, 排列 \(A\) 放置的第 i 个数在排列 \(A\) 中是第 a 大的，排列 \(B\) 放置的第 i 个数在排列 \(B\) 中是第 b 大的，此时相似度为 \(k\) 的排列数量。
转移方程为：
\[f_{(i+1)abk} = \sum_{x = 1}^{a - 1}\sum_{y = 1}^{b - 1} f_{ixy(k-1)} + \sum_{x = a}^{i}\sum_{y = b}^{i} f_{ixy(k-1)} + \sum_{x = 1}^{a - 1}\sum_{y = b}^{i} f_{ixyk} + \sum_{x = a}^{i}\sum_{y = 1}^{b - 1} f_{ixyk} \]
和式同样可以使用前缀和来优化。
时间复杂度为 \(O(n^4)\) 。
代码
int pre[107][107][107], f[107][107][107];
void solve_problem() {
int n, m, P;
std::cin >> n >> m >> P;
auto add = [&](int a, int b) -> int {
a += b;
if ( a >= P ) a -= P;
return a;
};
auto sub = [&](int a, int b) -> int {
a -= b;
if ( a < 0 ) a += P;
return a;
};
auto sum = [&](int n, int x1, int y1, int x2, int y2) -> int {
if (n < 0) return 0;
return add(sub(sub(pre[n][x2][y2], pre[n][x2][y1 - 1]), pre[n][x1 - 1][y2]), pre[n][x1 - 1][y1 - 1]);
};
for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
for (int h = 0; h <= n; h++)
pre[i][j][h] = f[i][j][h] = 0;
f[0][1][1] = 1;
for (int i = 1; i <= n; i++) {
for (int k = 0; k <= i + 1; k++) {
for (int a = 1; a <= i; a++) {
for (int b = 1; b <= i; b++) {
pre[k][a][b] = add(pre[k][a][b - 1], f[k][a][b]);
}
}
for (int b = 1; b <= i; b++) {
for (int a = 1; a <= i; a++) {
pre[k][a][b] = add(pre[k][a][b], pre[k][a - 1][b]);
}
}
}
for (int k = 0; k <= i + 1; k++) {
for (int a = 1; a <= i + 1; a++) {
for (int b = 1; b <= i + 1; b++) {
f[k][a][b] = add(
add(sum(k - 1, 1, 1, a - 1, b - 1), sum(k - 1, a, b, i, i)),
add(sum(k, 1, b, a - 1, i), sum(k, a, 1, i, b - 1))
);
}
}
}
}
std::cout << sum(m, 1, 1, n, n) << "\n";
}
查看更多关于AtCoder Beginner Contest 282 G - Similar Permutati的详细内容...