Codeforces Round #729 (Div. 2) - E1

ACM › 刷题实战 › CodeForces
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial

题目大意：

你需要计算有多少对满足长度为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
 *
 *
*/