套路题题意
求有多少个 \(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 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";}