2020 Petrozavodsk Winter Camp Day 5 F | Nanako

2020 Petrozavodsk Winter Camp Day 5 F

Problem F. The Halfwitters

Statement

给定长度 $n$,给定 $a, b, c$,给 $d$ 次询问。每次询问是一个长度为 $n$ 的排列,你可以对这个票列做三种操作:

  1. 花费 $a$ 代价,交换相邻的两个数;

  2. 花费 $b$ 代价,翻转这个排列;

  3. 花费 $c$ 代价,shuffle 这个排列。

对于每次询问,你需要求出,在最优的操作策略下,把排列排成升序所需的最小期望代价。有 $z$ 组测试数据。

$2 \leq n \leq 16$, $1 \leq a, b, c \leq 1000$, $1 \leq d \leq 10000$

$\sum d \leq 10^5$

Solution

考虑只有第一种操作,我们不难发现,总代价只跟逆序对数 $inv$ 有关。

考虑加上第二种操作,我们不难发现,先翻转一下再只进行以上操作可能会更快!

考虑加上第三种操作,我们不难发现,先 shuffle 一下再只进行以上操作可能会更快!我们令 shuffle 后代价的期望是 $x$。

那么,怎么求 $x$ 呢?记逆序对数为 $inv$ 的排列有 $L_{inv}$ 个,如果我们只能进行一次 shuffle 操作,那么显然

但是实际上,有可能 shuffle 一次之后我们不满意,那就有可能继续 shuffle。所以我们只好列一个方程来计算 $x$。

我们知道,shuffle 后有一部分满意的情况(即 $ans_{12}(inv) \leq x + c$),其中每种情况的代价是 $ans_{12}(inv)$;也有一部分不满意的情况(即 $ans_{12}(inv) > x + c$),其中每种情况的代价是 $x + c$。于是我们可以把上面那个错误的式子改成这样一个正确的式子:

为了方便计算这个东西,我们变换一下下标。令 $id$ 是一个排列且满足 $ans_{12}(id_i)$ 关于 $i$ 单增(用排序就可以实现),那么显然会有一个分界点 $k$ 使得

把 $x$ 挪到一边

考虑到 $n! = \sum_{i=0}^{\frac{n(n-1)}{2}} L_i$,我们可以修改得好看一点

这个方程有两个未知量 $x$ 和 $k$,但是我们不难发现它们必定满足 $ans_{12}(k) \leq x + c \leq ans_{12}(k + 1)$。然后我们预处理一下前缀和,枚举 $k$ 找合法解就可以辣!

$L_i$ 不会求的话,可以参考 [HAOI2009] 逆序对数列

Code

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#define all(v) (v).begin(), (v).end()
#define unq(v) (v).erase(unique(all(v)), (v).end())
#define ii int, int
#define li int, int
#define ll2 ll, ll
#define vec vector
#define pii pair <int, int>
#define pli pair <ll, int>
#define pll2 pair <ll, ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define MULTI int T; cin >> T; while(T--)
#define sqr(x) ((x) * (x))
#define test cerr << '!' << endl;
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main0 ();
int main () {
#ifndef ONLINE_JUDGE
freopen("C:\\Users\\98497\\Desktop\\code\\file.in", "r", stdin);
#endif
ios::sync_with_stdio(false);
clock_t start, end;
// start = clock();
main0();
// end = clock();
// cout << (end - start) << endl;
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}

const int dx[8] = {0, 1, -1, 0, 1, 1, -1, -1};
const int dy[8] = {1, 0, 0, -1, 1, -1, -1, 1};
const int N = 20;
const int M = 200;
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
const double Pi = acos(-1.0);

ll L[N][M];
ll fac[N];

void init () {
L[1][0] = 1;
for (int i = 2;i <= 16;++i) {
ll pre = 0;
for (int j = 0;j <= 120;++j) {
pre += L[i - 1][j];
if (j - i >= 0) pre -= L[i - 1][j - i];
L[i][j] = pre;
//cout << i << ' ' << j << ':' << f[i][j] << endl;
}
}

fac[0] = 1;
for (int i = 1;i <= 16;++i) {
fac[i] = fac[i - 1] * i;
}
}

ll v[N];
ll t[M], id[M];
ll pre1[M], pre2[M];

bool cmp (int x, int y) {
return t[x] < t[y];
}

ll gcd (ll x, ll y) {
if (!y) return x;
return gcd(y, x % y);
}

int main0 () {
init();
MULTI {
ll n, a, b, c, d;
cin >> n >> a >> b >> c >> d;
ll lim = n * (n - 1) / 2;

for (int i = 0;i <= lim;++i) {
t[i] = min(i * a, b + (lim - i) * a);
id[i] = i;
}
sort(id, id + lim + 1, cmp);

pre1[0] = L[n][0];
pre2[0] = L[n][0] * t[0];
for (int i = 1;i <= lim;++i) {
pre1[i] = pre1[i - 1] + L[n][id[i]];
pre2[i] = pre2[i - 1] + L[n][id[i]] * t[id[i]];
}

ll k, p, q;
double x;
for (k = 0;k < lim;++k) {
p = pre2[k] + c * fac[n];
q = pre1[k];
ll gcdd = gcd(p, q);
p /= gcdd;
q /= gcdd;
x = 1.0 * p / q;
//cout<<k<<':'<<p<<'/'<<q<<'='<<x<<' '<<t[id[k]]<<'~'<<t[id[k+1]]<< endl;
if ((t[id[k]] <= x) && (x <= t[id[k+1]])) break;
}

for (int cur = 1;cur <= d;++cur) {
int inv = 0;
for (int i = 1;i <= n;++i) {
cin >> v[i];
for (int j = 1;j <= i - 1;++j) {
inv += (v[j] > v[i]);
}
}

if (t[inv] <= x) cout << t[inv] << '/' << 1 << endl;
else cout << p << '/' << q << endl;
}
}
}

欢迎关注我的其它发布渠道