【训练记录】6.9 训练笔记

营业,营业!

A

有一天,主力手里有一个长度为 $n$ 的序列 ${a1,a2,…,an}$ 与 一个长度为 $m$ 的数列 ${b1,b2,…,bm}$, 他想知道有多少对 $(a_i,b_j){1≤i≤n,1≤j≤m}$ 满足两个数 XOR (异或) 以后,在二进制表示下恰好有两个 $1$。

输出这个对数。

$1\leq n\leq 10^5,1\leq a_i\leq 2^{30}$ 。

比较简单的套路题。考虑恰好有两个 $1$ 也就是说二进制下恰好有两位不同。于是可以开一个 map 扫一下 $\{a_n\}$,然后对于 $\{b_n\}$ 的每个数,$\log ^2$ 的复杂度去枚举一下 $p,q$ 。但这样 $\log ^3$ 并不可过。于是可以用一点 meet in middle 的思想,预处理 $n\log n$ 个值,分别是 $a_i$ 异或 $1,2,4,8\cdots$。这样就可以消掉一个 log。

B

有从 1 到 n 共 n个数,你需要将它们排成一列,使得任意两个相邻的数互质。

求一共有多少种排列方式。

共 $28$ 个测试点,对第 $n$ 个测试点有 $n=i$ 。

首先大概是 $30\sim 40$ 左右的分数可以直接暴力全排列出来。然后如果考虑更高一点的话,就可以设 $f_{s,i}$ 表示考虑了集合 $s$ 内的数,最后一个数是 $i$ 的方案数。这样复杂度就是 $O(2^n\times n^2)$ 的,空间复杂度是 $O(2^n\times n)$ 。可以获得大概 $80$ 左右的成绩。不过似乎是可以多插几个内存条来 A 掉这题,听上去很猛男。

正解考虑合并一些状态,大概是说发现诸如 $3,9,27$ 这样的数字,本质上是等价的。所以 $1\sim 28$ 就可以划分成 $14$ 个左右的等价类,对这些等价类 dp 就好了,状态数大概在 $2e7$ 左右。实现的时候稍有细节。

C

初始有 n 个小球,小球有 4 种颜色,初始的等级为 1

你每一次可以选择一个小球删除,删除后后面的小球会向前移动一位 。如果有至少 3 个相同颜色和等级的小球连续,那么左侧的 3 个会合并成一个颜色相同等级+1的小球(可能有连锁反应) 。

问有多少种能到达的局面 。两个局面是不同当且仅当长度不同或存在一个位置小球不同。

$n \leq 1000000$ 。

一个很重要的 Observation:合成一个 $p$ 级球,需要 $3^p$ 个 $1$ 级球。所以可以知道至多有 $\log $ 种不同的等级。然后可以对此进行 dp。设 $f_{i,(c,L),1/2}$ 表示考虑了原序列的前 $i$ 位,最后一个颜色球是 $c$,等级为 $L$ 时,末尾有 $1/2$ 个相同的球有多少种合法的序列。

那么首先不难发现 $c=col_i$ 。其次考虑转移,考虑一个 $(c,L_1)$ 后面可以转移到一个怎样的 $(d,L_2)$。这个地方需要分类讨论:

1、$c\neq d$ 。那么就可以直接转移

2、$c=d$ 。考虑这一部分由于题目中限制了「从最左端开始合成」,所以对于类似 aabaa 这种序列,(1,2,3)(4) 是合法的,而 (1)(2,3,4) 是不合法的。所以需要分类讨论一波长度关系:

(1)$L_1=L_2$ 。此时可以直接转移,但是注意到由于一个稳定的结束状态不会出现连续三个相同的球,所以转移应该为

(2)$L_1\gt L_2$ 。此时一定有一种合法的方式是先合完左边再合右边。所以可以正常转移

(3)$L_1\lt L_2$ 。注意到此时不能再这么合成了,因为必然会有一次合并使得右边超过左边,于是此时就需要调整分界线。考虑找到 $i$ 后面第一个颜色不等于 $c$ 的位置 $k$ ,然后从 $k$ 开始找 $3^j$ 个 $c$ 。这样就可以直接转移了,因为此时不存在左右部分互相影响的问题。

于是可以先预处理出来每个位置后面第一个和它颜色不同的位置、以及从每个位置开始第 $3^j$ 个 $0/1/2/3$ 分别在哪。最后这样做的复杂度是 $O(nC\log^2n)$ 的。通过一点小优化可以优化到 $O(nC\log n)$,不过我这里偷了一下懒,优化到了 $O(nC\log n+\dfrac{1}{4}nC\log ^2n)$ ,也是可以过的。

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
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define il inline

typedef long long ll ;

const int C = 4 ;

const int M = 13 ;

const int N = 1000010 ;

const int P = 998244353 ;

using namespace std ;

template <typename T>
il void chkmin(T &x, T y){ x = x > y ? y : x ; }
template <typename T>
il void chkmax(T &x, T y){ x = x < y ? y : x ; }
template <typename T>
il void add(T &x, ll y, int mod = P){
x += y ; x = x >= mod ? x - mod : x ;
}

int n ;
char cc[N] ;
int buc[C] ;
int base[N] ;
int go_d[N] ;
int go_s[N][C][M] ;

int ans ;
int g[M] ;
int f[N][M][2] ;
//think about the first i_th numbers, the last level is j, ths suffix sum is 1/2

int main(){
cin >> n ;
f[0][0][0] = 1 ;
scanf("%s", cc + 1) ;
fill(buc, buc + C, n + 1) ;
fill(go_d, go_d + n + 1, n + 1) ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = (int)cc[i] - 'A' ;
// for (int i = 1 ; i <= n ; ++ i)
// base[i] = i & 1 ;
for (int i = n ; i >= 0 ; -- i){
for (int c = 0 ; c < C ; ++ c){
go_s[i][c][0] = buc[c] ;
if (c != base[i])
chkmin(go_d[i], buc[c]) ;
}
// cout << go_d[i] << '\n' ;
buc[base[i]] = i ;
}
for (int i = 0 ; i < C ; ++ i)
for (int j = 0 ; j < M ; ++ j)
go_s[n][i][j] = go_s[n + 1][i][j] = n + 1 ;
for (int i = n - 1 ; i >= 0 ; -- i)
for (int k = 0 ; k < C ; ++ k)
for (int j = 1 ; j < M ; ++ j)
go_s[i][k][j] = go_s[go_s[ go_s[i][k][j - 1] ][k][j - 1] ][k][j - 1] ;
for (int i = 0 ; i < C ; ++ i)
for (int j = 0 ; j < M ; ++ j)
f[go_s[0][i][j]][j][0] = (go_s[0][i][j] != n + 1) ;
for (int i = 1 ; i <= n ; ++ i){
int s = 0 ;
int o = base[i], u = go_d[i], v, z ;
for (int k = 0 ; k < M ; ++ k)
add(s, (f[i][k][1] + f[i][k][0]) % P) ;
for (int j = 0 ; j < 4 ; ++ j) {
if (j != o){
for (int q = 0 ; q < M ; ++ q)
v = go_s[i][j][q], add(f[v][q][0], s) ;
continue ;
}
for (int p = 0 ; p < M ; ++ p){
for (int q = 0 ; q < M ; ++ q){
v = go_s[i][j][q] ;
z = go_s[u][j][q] ;
if (q < p)
add(f[v][q][0], (f[i][p][1] + f[i][p][0]) % P) ;
else if (q > p)
add(f[z][q][0], (f[i][p][0] + f[i][p][1]) % P) ;
a else add(f[v][q][1], f[i][p][0]) ;
// if (v <= n){
// cout << i << " " << v << " " << p << " " << q << '\n';
// cout << f[v][q][0] << " " << f[v][q][1] << '\n' ;
// }
}
}
}
}
for (int i = 1 ; i <= n ; ++ i)
for (int j = 0 ; j < M ; ++ j)
add(ans, (f[i][j][0] + f[i][j][1]) % P) ;
cout << ans << "\n" ; return 0 ;
}