如果两个排列A = (A\(_1\),A\(_2\),A\(_3\)....A\(_N\)),B = (B\(_1\),B\(_2\),B\(_3\)....B\(_N\))满足: 填坑dp:考虑一个排列在第i位填第j小的数满足条件的数量为k [dp[i][j][k]] (需要注意的是这里的条件基本都是相邻两位满足什么条件,否则不能应用) 我们考虑每次填当前的最后一位,如果要产生贡献(即使得j+1),那么有两种可能: 如果不产生贡献则同样有两种可能: 所以我们可以得到转移方法: 此时我们可以看到实际上\(\sum\)\(\sum\)这一部分实际上就是二维前缀和,同时对于第i位的值只与第i-1位有关,所以可以用滚动数组优化,所以总的时间复杂度就是O(n\(^4\)) 滚动数组:f[2][N][N][N],f[cur]当前状态,f[cur^1]上一位的状态G - Similar Permutation
题目大意:
(A\(_i\)-A\(_{i+1}\))(B\(_i\)-B\(_{i+1}\))>0 (1<= i <= N-1)
则称排列A,B的相似度为满足条件的i的数量。
现在给定n,k,p求长度为n的排列A,B,相似度为k的排列数量(mod p);
解题思路:
dp[i][j][a][b]:在第i位,考虑满足条件的有j组,A填第a大的数,B填第b大的数;
B:第i为为b,第i-1位为[1~b-1]
此时(A\(_i\)-A\(_{i-1}\))>0 && (B\(_i\)-B\(_{i-1}\))>0
B:第i为为b,第i-1位为[b+1~n]
此时(A\(_i\)-A\(_{i-1}\))<0 && (B\(_i\)-B\(_{i-1}\))<0
B:第i为为b,第i-1位为[b+1~n]
此时(A\(_i\)-A\(_{i-1}\))>0 && (B\(_i\)-B\(_{i-1}\))<0
B:第i为为b,第i-1位为[1~b-1]
此时(A\(_i\)-A\(_{i-1}\))<0 && (B\(_i\)-B\(_{i-1}\))>0
代码实现:
#include<bits/stdc++.h>
using namespace std;
# define int long long
# define endl "\n"
const int N = 2e5 + 10, inf = 1e18;
int f[2][110][110][110];
void solve() {
int n, need, p;
cin >> n >> need >> p;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
f[0][0][i][j] = 1;
}
}
int cur = 0;
vector<vector<int>> pre(n + 2, vector<int>(n + 2));
for (int i = 2; i <= n; ++i) {
cur ^= 1;
memset(f[cur], 0, sizeof f[cur]);
for (int j = 0; j < i-1; ++j) {
for (int a = 1; a < i; ++a) {
for (int b = 1; b < i; ++b) {
(f[cur ^ 1][j][a][b] += f[cur ^ 1][j][a - 1][b] + f[cur ^ 1][j][a][b - 1] - f[cur ^ 1][j][a - 1][b - 1]) %= p;
}
}
for (int a = 1; a <= i; ++a) {
for (int b = 1; b <= i; ++b) {
(f[cur][j][a][b] += f[cur ^ 1][j][i - 1][b - 1] - f[cur ^ 1][j][a - 1][b - 1] + f[cur ^ 1][j][a - 1][i - 1] - f[cur ^ 1][j][a - 1][b - 1] + p) %= p;
}
}
for (int a = 1; a <= i; ++a) {
for (int b = 1; b <= i; ++b) {
(f[cur][j + 1][a][b] += f[cur ^ 1][j][a - 1][b - 1] + f[cur ^ 1][j][i - 1][i - 1] - f[cur ^ 1][j][a - 1][i - 1] - f[cur ^ 1][j][i - 1][b - 1] + f[cur ^ 1][j][a - 1][b - 1] + p) %= p;
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
(ans += f[cur][need][i][j] + p) %= p;
}
}
cout << ans << endl;
}
int tt;
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
tt = 1;
// cin >> tt;
while (tt--) solve();
return 0;
}