0%

4.9杂题

T1 Inverter SwapSort

题意

给定一个排列,求出所有逆序对的一个排列,使得依次交换每一对数最终能使得整个数组有序。

题解

考虑每次找到关于一个位置的所有逆序对。

将最后一个位置拿出来,观察前面的所有数与它形成的逆序对。假设最后一个数为$x$,那么可以发现依次交换$x+1,x+2,\cdots$不会对前面的数的相对顺序造成影响,且可以将最大的数挪到结尾。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int A[N], pos[N], buk[N];

int main() {
int n; scanf("%d", &n); vector<int> v;
for (int i = 1; i <= n; i++) scanf("%d", &A[i]), v.push_back(A[i]);
sort(v.begin(), v.end()), v.resize(unique(v.begin(), v.end()) - v.begin());
for (int i = 1; i <= n; i++) {
A[i] = lower_bound(v.begin(), v.end(), A[i]) - v.begin() + 1;
buk[A[i]]++;
}
for (int i = 1; i <= n; i++) buk[i] += buk[i - 1];
for (int i = n; i >= 1; i--) A[i] = buk[A[i]]--;
vector<pair<int, int>> res;
for (int i = n; i >= 1; i--) {
for (int j = 1; j <= n; j++) pos[j] = 0;
for (int j = 1; j < i; j++) if (A[j] > A[i])
pos[A[j]] = j;
int lst = A[i];
for (int j = lst + 1; j <= n; j++) if (pos[j])
swap(A[pos[j]], A[i]), res.push_back(make_pair(pos[j], i));
}
printf("%d\n", res.size());
for (auto t : res) printf("%d %d\n", t.first, t.second);
}

T2 Blog Post Rating

题意

有一个一开始为空的序列,每次你会给序列插入一个元素,然后将整个序列从小到大排序。

现在你手里有一个值$x$,它一开始为$0$,你从小到大查看序列中的每个元素,如果当前元素比$x$大,那么让$x+1$,如果比$x$小,那么让$x-1$,否则保持不变。你需要回答每次插入之后这个值最终会变成多少。

题解

考虑给定一个序列,如何计算$x$最终的值。

假设现在这个序列已经排好序了,且第$i$个位置的数是$a_i$。

如果$x$在第$i$个位置恰好等于$a_i$,那么显然最终的$x$不能超过$a_i+n-i$。并且容易发现最终的$x$就是$a_i+n-i$的最小值。

加入了修改操作之后,考虑建一棵值域线段树,那么每次修改相当于给一段后缀的排名加上$1$,同时我们需要维护$a_i+n-i$的最小值。

$x$从$0$开始比较恶心,观察到$x$的变化必然是一开始一直减,直到小于或等于当前的数,然后再要么不变,要么$+1$。

二分这个拐点,那么这个拐点必须满足$-i\leq a_i$,即查询$a_i+i\geq 0$的第一个位置,并且可以得出,$x$在这个位置的值为$\max(-i,a_i)$。

假设拐点的位置为$j$,那么我们只需查询$j$之后的数的$a_i+n-i$的最小值,并对此时的$x+n-j$取$\min$即可。

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;

struct node {
int l, r, tag, x, y;
} T[N << 2];

void pushup(int rt) {
T[rt].x = min(T[rt << 1].x, T[rt << 1 | 1].x);
T[rt].y = max(T[rt << 1].y, T[rt << 1 | 1].y);
}

void pushdown(int rt) {
if (!T[rt].tag) return;
T[rt << 1].x -= T[rt].tag, T[rt << 1 | 1].x -= T[rt].tag;
T[rt << 1].y += T[rt].tag, T[rt << 1 | 1].y += T[rt].tag;
T[rt << 1].tag += T[rt].tag, T[rt << 1 | 1].tag += T[rt].tag;
T[rt].tag = 0;
}

void build(int rt, int l, int r) {
T[rt].l = l, T[rt].r = r;
if (l == r) return T[rt].x = T[rt].y = l, void();
int mid = (l + r) >> 1;
build(rt << 1, l, mid), build(rt << 1 | 1, mid + 1, r), pushup(rt);
}

void update(int rt, int start, int end) {
int l = T[rt].l, r = T[rt].r, mid = (l + r) >> 1;
if (start <= l && r <= end) return T[rt].tag++, T[rt].x--, T[rt].y++, void();
pushdown(rt);
if (start <= mid) update(rt << 1, start, end);
if (end > mid) update(rt << 1 | 1, start, end);
pushup(rt);
}

int find(int rt) {
int l = T[rt].l, r = T[rt].r, mid = (l + r) >> 1;
if (T[rt].y < 0) return -1e9;
if (l == r) return l;
pushdown(rt);
if (T[rt << 1].y >= 0) return find(rt << 1);
return find(rt << 1 | 1);
}

int query(int rt, int start) {
int l = T[rt].l, r = T[rt].r, mid = (l + r) >> 1;
if (start <= l) return T[rt].x;
pushdown(rt);
if (start > mid) return query(rt << 1 | 1, start);
return min(T[rt << 1 | 1].x, query(rt << 1, start));
}

int tree[N], mn, mx;

void upd(int x) {
for (x -= mn - 1; x <= mx - mn + 1; x += x & -x) tree[x]++;
}

int que(int x) {
int res = 0;
for (x -= mn - 1; x; x -= x & -x) res += tree[x];
return res;
}

int main() {
int n; scanf("%d", &n), mn = 0, mx = 0;
vector<int> v;
for (int i = 1, a; i <= n; i++)
scanf("%d", &a), v.push_back(a), mn = min(mn, a), mx = max(mx, a);
build(1, mn, mx);
for (int i = 1; i <= n; i++) {
int a = v[i - 1]; update(1, a, 1e9), upd(a);
int pos = find(1);
if (pos == -1e9) printf("%d\n", -i);
else {
int t = que(pos), tmp = max(pos, -t) + i - t, res = query(1, pos) + i;
printf("%d\n", min(tmp, res));
}
}
}

T3 咕

题意

来源:auoj471

一个随机排列,你从第一个位置走到第$n$个位置,每走一步你可以得知当前数是否是前缀最小值,你可以选择是否拿走这个数,问在最优策略下你拿走$1$的概率。多组数据。

题解

最优策略必然是:你选择一个位置$x$,然后扔掉$x$及之前的所有数,在$x$之后取走第一个为前缀最小值的位置。

写成$dp$的形式就是,记$f_i$表示已经扔掉了前$i-1$个数,此时在第$i$个数时开始决策,最后拿走$1$的概率。

第$i$个位置为前缀最小值的概率为$\frac 1i$,在是前缀最小值的条件下为$1$的概率为$\frac in$。

因此我们可以得出转移:

转移里的$\max$非常讨厌,尝试去掉这个东西。

如果$f_{i+1}>\frac in$,那么有$f_i=\frac 1i f_{i+1}+\frac{i-1}if_{i+1}=f_{i+1}$。因此我们只需找到第一个$\frac in>f_{i+1}$的位置,容易发现满足这个条件的必然是一段后缀。

当$\frac in$取到最大值时,有

记$g_i=nf_i$,那么$g_i=1+\frac {i-1}ig_{i+1}$,显然有$g_{n+1}=0$,那么有

后面是一个调和级数,可以预处理调和级数的后缀和,每次二分出第一个$\frac in>f_{i+1}$的位置即可。

另外,这个位置约等于$\frac ne$,也可以用一些奇妙的方法求出这个断点。

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
#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
const int N = 1000010;

typedef long long LL;

int frac[N], inv[N];

const double e = exp(1);

double wkr[N];

int main() {
int T; scanf("%d", &T), inv[1] = frac[1] = 1;
for (int i = 2; i <= N - 10; i++) inv[i] = (LL)(mod - mod / i) * inv[mod % i] % mod;
for (int i = 1; i <= N - 10; i++) wkr[i] = wkr[i - 1] + 1. / i;
for (int i = 2; i <= N - 10; i++) inv[i] = (inv[i - 1] + inv[i]) % mod, frac[i] = (LL)frac[i - 1] * i % mod;
while (T--) {
int n; scanf("%d", &n);
if (n == 1) { puts("1"); continue; }
int pos = round(n / e + 1 - 0.5 / e), res;
if (wkr[n - 1] - wkr[pos - 2] < 1) pos--;
res = (LL)(pos - 1) * (inv[n - 1] - inv[pos - 2] + mod) % mod;
printf("%d\n", (LL)res * (inv[n] - inv[n - 1] + mod) % mod);
}
}

T4 function

题意

定义$P(x)$表示满足$1<y<x,y^3\equiv 1\pmod x$的$y$的数量,求在$n$以内有多少正整数满足$P(x)=m$。

题解

把条件放宽为$1\leq y<x$,先考虑给定一个$x$,如何快速地求出$P(x)$。

显然$x$的每个质因子都可以分开考虑,最后用中国剩余定理合并就可以还原,因此条件等价于:将$x$分解为$\prod p_i^{c_i}$,只需对每个$p_i$都满足$y^3\equiv 1\pmod {p^{c_i}}$。

如果条件满足,那么显然$y$与$p$互质,因此有

容易得出当$3\nmid \varphi(p^c)$时满足条件的$y$只有$1$。

我们有$\varphi(p^c)=(p-1)p^{c-1}$,只需考虑$p=3$或者$3\mid p-1$,且当$p=3,c=1$时是不行的。

设原根为$g$,则阶为$\varphi(p^c)$。不妨设$y=g^k$,由于$y\bot p$,因此这样的$k$一定存在。

故条件转化为

即$3k\equiv 0\pmod {\varphi(p^c)}$。

同时除以$3$,有$k\equiv 0\pmod{\frac {\varphi(p^c)}3}$

因此满足条件的$k$只有$3$个,即$y^3\equiv 1\pmod {p^c}$的解只有$3$个。

因此有

注意到需要求出$\bmod 3=1$的质数的个数,定义$f(x)=\begin{cases}0&3|x\\1&3|x-1\-1&3|x-2\end{cases}$,筛出$f$以及$n$以内的质数个数就可以解出$\bmod 3=1$的质数个数,而这两个东西都是完全积性的。

使用min25筛的变种即可。

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
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 200010;

int flag[N], prime[N], tot, sum[N], wkr[N];

void sieve(int n) {
for (int i = 2; i <= n; i++) {
if (!flag[i]) {
prime[++tot] = i, sum[tot] = sum[tot - 1], wkr[tot] = wkr[tot - 1];
if (i % 3 == 1) sum[tot]++, wkr[tot]++;
else if (i % 3 == 2) sum[tot]--;
}
for (int j = 1; j <= tot && i * prime[j] <= n; j++) {
flag[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
}

LL val[2 * N], g[2 * N], p[2 * N], n; // g[i][j]: 1 ~ i, s(n) > p_j
int id1[N], id2[N], lim;

int get(LL x) {
return x <= lim ? id1[x] : id2[n / x];
}

array<LL, 10> S(LL n, int m) {
// cout << n << ' ' << m << endl;
array<LL, 10> nw; nw.fill(0);
if (n < prime[m]) return nw;
// if (((g[get(n)] + p[get(n)]) % 2 + 2) % 2 != 1) cout << "FUCK: " << n << endl;
LL A = (g[get(n)] + p[get(n)] - 1) / 2 - wkr[m - 1];
nw[1] = A, nw[0] = p[get(n)] - (m - 1) - A;
for (int i = m; i <= tot && (LL)prime[i] * prime[i] <= n; i++) {
for (LL j = prime[i], c = 1; j * prime[i] <= n; j *= prime[i], c++) {
int t = (prime[i] == 3 && c > 1) || prime[i] % 3 == 1;
nw[prime[i] % 3 != 2]++; auto tmp = S(n / j, i + 1);
if (t) rotate(tmp.begin(), tmp.end() - 1, tmp.end());
for (int k = 0; k < 10; k++) nw[k] += tmp[k];
}
}
return nw;
}

int main() {
LL m; scanf("%lld%lld", &n, &m), m++;
int ct = 0;
while (m != 1) {
if (m % 3) return puts("0"), 0;
m /= 3, ct++;
}
lim = ceil(sqrt(n)), sieve(lim); int blk = 0;
for (LL l = 1; l <= n; l = n / (n / l) + 1) {
LL t = n / l;
blk++, val[blk] = t;
if (t <= lim) id1[t] = blk; else id2[n / t] = blk;
g[blk] = (t % 3 == 1) - 1, p[blk] = t - 1;
}
for (int i = 1; i <= tot; i++)
for (int j = 1; j <= blk && (LL)prime[i] * prime[i] <= val[j]; j++) {
int pos = get(val[j] / prime[i]);
if (prime[i] % 3) {
int t = prime[i] % 3 == 1 ? 1 : -1;
g[j] -= t * (g[pos] - sum[i - 1]);
}
p[j] -= p[pos] - (i - 1);
}
auto res = S(n, 1); res[0]++;
printf("%lld\n", res[ct]);
}