Codeforces Round #729 (Div. 2) - E1


题目大意:

你需要计算有多少对满足长度为n的排列$p$和$q$,满足$p$字典序>$q$ 且 $inv(p)<inv(q)$,答案取模

$inv$ 为逆序对个数

做法:

设$f(i,j)$为长度为$i$、逆序对个数为$j$的排列的个数 , 考虑第一个数字为$t$

$f(i,j) = \sum_{t \in [1,i]} f(i-1,j-t+1)$

一个填$u$,另一个填$v$ $u<v$

$$
\begin{aligned}
ans[i] \&= i * ans[i-1] + \sum_{1<=u<v<=i, x+u>y+v} f(i-1,x)\cdot f(i-1,y)
\&= i * ans[i-1] + \sum_{x-y>v-u, 1<=u<v<=i} f(i-1,x)\cdot f(i-1,y)
\&= i * ans[i-1] + \sum_{x-y>d, 1<=d<i} (i-d)*f(i-1,x)\cdot f(i-1,y)
\&= i * ans[i-1] + \sum_{x,y} f(i-1,x)\cdot f(i-1,y) \cdot \sum_{x-y>d, 1<=d<i} (i-d)
\end{aligned}
$$

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<iostream>

using namespace std;

/**
* 题目大意:
* http://codeforces.com/contest/1542/problem/E1
* 你需要计算有多少对满足长度为n的排列p和q,满足p字典序>q 且 inv(p)<inv(q),答案取模
* inv 为逆序对个数
*
* 做法:
* 设f(i,j)为长度为i、逆序对个数为j的排列的个数 , 考虑第一个数字为t
* f(i,j) = sum_{t \in [1,i]} f(i-1,j-t+1)
*
* 一个填u,另一个填v u<v
* ans[i] = i * ans[i-1] + sum_{1<=u<v<=i, x+u>y+v} f(i-1,x)*f(i-1,y)
* = i * ans[i-1] + sum_{x-y>v-u, 1<=u<v<=i} f(i-1,x)*f(i-1,y)
* = i * ans[i-1] + sum_{x-y>d, 1<=d<i} (i-d)*f(i-1,x)*f(i-1,y)
* = i * ans[i-1] + sum_{x,y} f(i-1,x)*f(i-1,y) * sum_{x-y>d, 1<=d<i} (i-d)
*
* 4 403458273
* 17
*/
const int maxn = 50 + 5;
int f[maxn][maxn * maxn];


int main() {
int n, mod;
cin >> n >> mod;

// O(n^4)
f[1][0] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= n * n; j++) {
f[i][j] = 0;
for (int t = 1; t <= i; t++) {
f[i][j] = (f[i][j] + f[i - 1][j - t + 1]) % mod;
}
}
}

// O(n^5)
int ans = 0;
for (int i = 1; i <= n; i++) {
int add = 0;
int upi = (0 + i - 1) * i / 2;
for (int x = 0; x <= upi; x++) {
for (int y = 0; y < x; y++) {
int tmp = min(i - 1, x - y - 1);
int sd = (i - 1 + i - tmp) * tmp / 2;
// printf("x=%d y=%d %d\n", x, y, sd);
add = (add + 1ll * sd * f[i - 1][x] % mod * f[i - 1][y]) % mod;
}
}
// cout << "i=" << i << " add=" << add << endl;
ans = (1ll * i * ans + add) % mod;
}
cout << ans << endl;


for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n * n; j++) {
// printf("%d%c", f[i][j], j == n * n ? '\n' : ' ');
}
}

}

/**
*
*
* 123 0
* 132 1
* 213 1
* 231 2
* 312 2
* 321 3
*
*
*/


文章作者: fightinggg
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 fightinggg !
  目录