20231116题解
又双叒叕打脸了。一场感冒很通人性地帮我赶走了期中考,于是我又去机房了。
mex
mex 这种东西好像比较典,建议大家区学习学习一些模板题,类似区间求 mex 之类的。
不过这个题跟上面说的没啥关系。定义 \(f_i\) 表示强制第一个数取 \(a_i\),从 \(i\) 开始向后匹配,保证能匹配的最长长度。比如对于 \(a\) 数组 1 2 3 4 5 6 7 8 9 1
,对应的 \(f\) 数组是 2 1 1 1 1 1 1 1 1 1
。
这个东西暴力 \(\mathcal{O}(n^2)\) 转移就好了。关键是怎么构造。
我们来考虑第一位:我们肯定是希望构造出的长度越短越好,所以应该选 \(f\) 最小的数字。如果 \(f\) 相同,就再选最小的数字。之后是可以递归的。
细节看代码吧,讲不清楚。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
using namespace std;
const int maxn = 2e2 + 5;
int n;
char a[maxn];
namespace AC { //美好的希冀
int b[15], c[15], dp[maxn];
void solve() {
if (![&]() {
for (int i = 1; i <= n; i++) if (a[i] == '0') return true;
return false;
}()) {
printf("0\n");
return;
}
for (int i = n; i >= 1; i--) {
memset(b, 0, sizeof b);
for (int j = i + 1; j <= n; j++) {
b[a[j] - '0'] = max(b[a[j] - '0'], dp[j]);
}
dp[i] = 0x3f3f3f3f;
for (int j = 0; j < 10; j++) dp[i] = min(dp[i], b[j] + 1);
}
int id = 0;
while (true) {
memset(b, 0, sizeof b); memset(c, 0x3f, sizeof c);
for (int i = id + 1; i <= n; i++) {
b[a[i] - '0'] = max(b[a[i] - '0'], dp[i]);
c[a[i] - '0'] = min(c[a[i] - '0'], i);
}
int v = -1;
for (int i = 0; i < 10; i++) {
if (id == 0 && i == 0) continue;
if (v == -1 || (b[i] < b[v])) v = i;
}
putchar('0' + v);
if (!b[v]) {
putchar('\n');
break;
}
else id = c[v];
}
}
}
int main() {
freopen("mex.in", "r", stdin);
freopen("mex.out", "w", stdout);
scanf("%d", &n);
scanf("%s", a + 1);
AC::solve();
// test::work();
return 0;
}
permutation
一开始毫无思路,先打一个暴力: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
31namespace brute_force {
int a[maxn], cnt;
bool check() {
int sum = 0, tot = 0;
for (int i = 1; i <= n; i++) {
sum += a[i];
if (i < n && sum == i * (i + 1) / 2) return false;
for (int j = i + 1; j <= n; j++) {
tot += (a[i] > a[j]);
}
}
return tot == n - 1;
}
void solve() {
for (int i = 1; i <= n; i++) a[i] = i;
do {
if (check()) {
cnt++;
for (int i = 1; i <= n; i++) {
//if (a[i] < 8) continue;
cerr << a[i] << " ";
}
cerr << endl;
if (cnt == k) {
for (int i = 1; i <= n; i++) printf("%d%c", a[i], " \n"[i == n]);
break;
}
}
} while (next_permutation(a + 1, a + n + 1));
}
}
把 \(n=9\) 的所有合法序列都打出来看一看:
1 | 2 3 4 5 6 7 8 9 1 |
好像很乱啊。但是注意看 1:
1 | - - - - - - - - 1 |
很有规律!
这启发我们考虑每个数的位置。但如果你看看另一些数,比如 4:
1 | - - 4 - - - - - - |
右半段还是有规律的,但是左半段不容易看出。我们不妨换个视角:我们把 1、2、3 出现位置全部删掉,再看一看:
1 | 4 - - - - - |
现在就有统一的规律了。修一修写出代码: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
int a[maxn];
int get_pos(int x) {
//共 1<<(n-2) 次
//循环节长度为 1<<(n-x)
//特别的,1没有潜伏期,n直接返回1
if (x == n) return 1;
if (x == 1) {
if (__builtin_popcountll(k) > 1) return n - (64 - __builtin_clzll(k) + 1) + 1;
else return n - (64 - __builtin_clzll(k)) + 1;
}
else {
long long tk = (k - 1) % (1LL << (n - x)) + 1;
if (tk <= (1LL << (n - x - 1))) return 1;
else {
tk -= (1LL << (n - x - 1));
if (__builtin_popcountll(tk) > 1) return (n - x + 1) - (64 - __builtin_clzll(tk) + 1) + 1;
else return (n - x + 1) - (64 - __builtin_clzll(tk)) + 1;
}
}
}
void solve() {
for (int i = 1; i <= n; i++) {
int p = get_pos(i);
// cerr << p << endl;
for (int j = 1; j <= n; j++) {
if (!a[j]) {
p--;
if (!p) a[j] = i;
}
}
}
for (int i = 1; i <= n; i++) {
printf("%d%c", a[i], " \n"[i == n]);
}
}
}
这样有 40 pts。
剩下的是讨厌的高精度。但我们发现实际上对 \(k\) 进行的都是位运算,所以考虑 bitset 高精度。1
2
3
4
5
6
7
8
9typedef bitset<maxn> bint;
bint operator + (bint a, bint b) {
bool c = false; bint res;
for (int i = 0; i < maxn; i++) {
res[i] = (a[i] ^ b[i] ^ c);
c = ((a[i] + b[i] + c) > 1);
}
return res;
}
只要实现加法能输入就好了。
AC 代码: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
using namespace std;
template <class T>
void read(T &r) {
r = 0; int ch = getchar(), f = 0;
while (!isdigit(ch)) f ^= (ch == 45), ch = getchar();
while (isdigit(ch)) (r *= 10) += ch - 48, ch = getchar();
if (f) r = -r;
}
const int maxn = 5e3 + 5;
typedef bitset<maxn> bint;
bint operator + (bint a, bint b) {
bool c = false; bint res;
for (int i = 0; i < maxn; i++) {
res[i] = (a[i] ^ b[i] ^ c);
c = ((a[i] + b[i] + c) > 1);
}
return res;
}
void read(bint &r) {
r.reset(); int ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)) {
r = (r << 1) + (r << 3) + bint(ch - 48);
ch = getchar();
}
}
long long n;
bint k;
namespace AC { //打表打出来的
int a[maxn];
int get_pos(int x) {
//共 1<<(n-2) 次
//循环节长度为 1<<(n-x)
//特别的,1没有潜伏期,n直接返回1
if (x == n) return 1;
if (x == 1) {
int p = 0;
for (int i = 0; i < maxn; i++) if (k[i]) p = i + 1;
if (k.count() > 1) return n - (p + 1) + 1;
else return n - p + 1;
}
else {
bint tk = k;
for (int i = n - x; i < maxn; i++) tk.reset(i);
if (!tk.count()) return 2;
else if ((!tk[(n - x - 1)]) || tk.count() == 1) return 1;
else {
tk.reset(n - x - 1);
int p = 0;
for (int i = 0; i < maxn; i++) if (tk[i]) p = i + 1;
if (tk.count() > 1) return (n - x + 1) - (p + 1) + 1;
else return (n - x + 1) - p + 1;
}
}
}
void solve() {
for (int i = 1; i <= n; i++) {
int p = get_pos(i);
// cerr << p << endl;
for (int j = 1; j <= n; j++) {
if (!a[j]) {
p--;
if (!p) a[j] = i;
}
}
}
for (int i = 1; i <= n; i++) {
printf("%d%c", a[i], " \n"[i == n]);
}
}
}
int main() {
freopen("permutation.in", "r", stdin);
freopen("permutation.out", "w", stdout);
read(n); read(k);
// brute_force::solve();
AC::solve();
return 0;
}
lovelorn
lovelorn
威廉怎么会失恋呢?
容易发现,可以把一个数拆成连续的它的本质不同的质因数(比如 30 拆成 2、3、5)。这样一来,询问就变成了区间去重,即所有出现过的数的乘积。
这个东西基本等价于HH的项链。用离线树状数组。右端点从小到大排序之后,每一个数肯定是由最靠右的那一个来提供贡献。用树状数组维护贡献即可。
另外注意质因数分解:用欧拉筛筛质数的时候,我们其实会得到每个数的最小质因子,用这个东西来分解最快。
细节看代码。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
using namespace std;
char st;
namespace io {...};
using namespace io;
const int maxn = 1e6 + 5, maxv = 1e7 + 5;
const long long mod = 998244353;
int n, a[maxn], t;
long long quick_pow(long long x, long long p) {
long long res = 1; while (p) {
if (p & 1LL) (res *= x) %= mod;
(x *= x) %= mod, p >>= 1;
} return res;
}
namespace HH {
struct node {
int l, r, id;
} q[maxn];
int l[maxn], r[maxn];
int b[maxn * 10];
int from[maxv], vis[maxv];
long long inv[maxv], ans[maxn], c[maxn * 10];
bitset<maxv> np;
vector<int> primes;
void init() {
np[1] = true;
for (int i = 2; i <= 1e7; i++) {
if (!np[i]) {
primes.emplace_back(i);
from[i] = i;
}
for (int j : primes) {
if (i * j > 1e7) break;
np[i * j] = true;
from[i * j] = j;
if (i % j == 0) break;
}
}
int bcnt = 0;
for (int i = 1; i <= n; i++) {
int v = a[i]; l[i] = 0x3f3f3f3f;
if (v == 1) l[i] = r[i] = bcnt;
while (v > 1) {
int tmp = from[v];
while (v % tmp == 0) v /= tmp;
b[++bcnt] = tmp;
l[i] = min(l[i], bcnt);
r[i] = max(r[i], bcnt);
}
}
n = bcnt;
for (int p : primes) inv[p] = quick_pow(p, mod - 2);
for (int i = 1; i <= n; i++) c[i] = 1;
}
void update(int pos, long long x) {
while (pos <= n) {
(c[pos] *= x) %= mod;
pos += (pos & -pos);
}
}
long long ask(int pos) {
long long res = 1; while (pos) {
(res *= c[pos]) %= mod;
pos -= (pos & -pos);
} return res;
}
void solve() {
init();
for (int i = 1; i <= t; i++) {
read(q[i].l), read(q[i].r), q[i].id = i;
q[i].l = l[q[i].l], q[i].r = r[q[i].r];
}
sort(q + 1, q + t + 1, [&](node &a, node &b) { return a.r < b.r; });
int j = 0;
for (int i = 1; i <= n; i++) {
if (vis[b[i]]) update(vis[b[i]], inv[b[i]]);
update(vis[b[i]] = i, b[i]);
while (q[j + 1].r == i) {
j++;
ans[q[j].id] = ask(q[j].r) * quick_pow(ask(q[j].l - 1), mod - 2) % mod;
}
}
for (int i = 1; i <= t; i++) write(ans[i]);
}
}
char ed;
int main() {
freopen("lovelorn.in", "r", stdin);
freopen("lovelorn.out", "w", stdout);
// cerr << (&ed - &st) / 1024.0 / 1024.0 << endl;
// auto t1 = clock();
read(n);
for (int i = 1; i <= n; i++) {
read(a[i]);
}
read(t);
HH::solve();
// cerr << clock() - t1 << endl;
return 0;
}