COCI2021-2022 Contest1 题解

更好的阅读体验戳此进入

（建议您从上方链接进入我的个人网站查看此 Blog，在 Luogu 中图片会被墙掉，部分 Markdown 也会失效）

原题面链接

Luogu题面

T1 Ljeto

题意

$n$ $t_i$ $a_i$ $b_i$ $100$ $50$ 分。

$1 \le a_i, b_i \le 8$ $1 \le a_i, b_i \le 4$ $5 \le a_i, b_i \le 8$ 表示其为二队，输出两队得分。

Examples

Input_1

3
10 1 6
20 1 7
21 8 1

Output_1

250 100

Input_2

3
10 2 5
15 2 6
25 2 5

Output_2

400 0

Input_3

2
10 5 2
11 6 3

Output_3

0 200

Solution

$50$ 分而不是三次，即若两次间隔小于十秒但中间仍有一次击中不算加分。

$t_i$ 升序输入，如果非升序则需要先离线排序一下，但原版题面中有这样一句

$t_i$ are distinct and are ordered increasingly.

保证了升序输入且不会有相同。

upd - 已向 Luogu 提交翻译错误，题面现已被修改。

将这两点想明白之后这个题就真的是一道入门题了，考虑记录每个人上次击中的时间，直接根据题意模拟即可。


xxxxxxxxxx
51
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7

8
using namespace std;
9

10
mt19937 rnd(random_device{}());
11
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
12

13
typedef unsigned int uint;
14
typedef unsigned long long unll;
15
typedef long long ll;
16

17
template<typename T = int>
18
inline T read(void);
19

20
int as(0), bs(0);
21
void shot(int n){n <= 4 ? as += 100 : bs += 100;}
22
void doub(int n){n <= 4 ? as += 50 : bs += 50;}
23
int lshot[10];
24
int main(){
25
    for(int i = 0; i <= 9; ++i)lshot[i] = -114514;
26
    int N = read();
27
    for(int i = 1; i <= N; ++i){
28
        int t = read(), a = read(); (void)read();
29
        if(t - lshot[a] <= 10)doub(a);
30
        shot(a);
31
        lshot[a] = t;
32
    }
33
    printf("%d %d\n", as, bs);
34
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
35
    return 0;
36
}
37
template<typename T>
38
inline T read(void){
39
    T ret(0);
40
    short flag(1);
41
    char c = getchar();
42
    while(c != '-' && !isdigit(c))c = getchar();
43
    if(c == '-')flag = -1, c = getchar();
44
    while(isdigit(c)){
45
        ret *= 10;
46
        ret += int(c - '0');
47
        c = getchar();
48
    }
49
    ret *= flag;
50
    return ret;
51
}

T2 Kamenčići

题面

$(n \le 350)$ $\texttt{Alice}$ $\texttt{Bob}$ $K$ 个红色石子时则失败，保证会有人获胜，求出两人谁获胜。

$\texttt{Alice}$ $\texttt{DA}$ $\texttt{NE}$ 。

Examples

Input_1

4 1
CCCP

Output_1

DA

Input_2

8 2
PCPPCCCC

Output_2

DA

Input_3

9 1
PPCPPCPPC

Output_3

NE

Solution

先说几个乱搞的做法：

首先观察发现似乎可以贪心，如果一边红色一边蓝色显然最优方案一定是取蓝色的。

对于两边都是红色或者都是蓝色，~~我有个别的贪心方案但是假掉了~~，题解里有一个贪心方案是尽量让对方更快碰到红色，也就是找到除头尾外，哪边红色石头更近，或者找哪个蓝色石头更远，按照这个思路似乎可以切掉这道题，不过我认为这个方案正确性并不显然，有可能只是运气好数据比较水。

$0 \texttt{pts}$ ）

$n$ $n \le 350$ ，这个数据范围显然可以区间 DP。

$dp(l, r, k)$ $\left[l, r\right]$ $k$ $\texttt{Alice}$ $\left[l + 1, r\right]$ $\left[l, r - 1\right]$ $k$ 如何计算。

$\texttt{Alice}$ $\texttt{Bob}$ 取走的。

$k$ $k'$ ，那么就有：

k^{'} = s u m (N) - (s u m (r) - s u m (l - 1)) - k

考虑到对手之间获胜状态相反，所以需要取反。考虑到两人均选择最优方式挑选，所以需要或运算。

于是就会有如下状态转移方程：

d p (l, r, k) = \neg d p (l + 1, r, k^{'}) \lor \neg d p (l, r - 1, k^{'})

此时考虑到边界条件就可以得出最终方程：

\begin{matrix} d p (l, r, k) = {\begin{cases} false & k > K \\ true & k^{'} > K \\ \neg d p (l + 1, r, k^{'}) \lor \neg d p (l, r - 1, k^{'}) & otherwise \end{cases} \end{matrix}

$\texttt{dfs}$ + 记忆化搜索。

Code


xxxxxxxxxx
59
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7

8
using namespace std;
9

10
mt19937 rnd(random_device{}());
11
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
12

13
typedef unsigned int uint;
14
typedef unsigned long long unll;
15
typedef long long ll;
16

17
template<typename T = int>
18
inline T read(void);
19

20
int N, K;
21
bool stone[400];
22
int sum[400];
23
int dp[400][400][400];
24
int DFS(int l, int r, int k){
25
    if(~dp[l][r][k])return dp[l][r][k];
26
    if(k >= K)return false;
27
    int k_ = sum[N] - (sum[r] - sum[l - 1]) - k;
28
    if(k_ >= K)return true;
29
    return dp[l][r][k] = (!DFS(l + 1, r, k_) | !DFS(l, r - 1, k_));
30
}
31

32
int main(){
33
    memset(dp, -1, sizeof(dp));
34
    N = read(), K = read();
35
    for(int i = 1; i <= N; ++i){
36
        char c = getchar(); while(c != 'C' && c != 'P')c = getchar();
37
        stone[i] = (c == 'C' ? true : false);
38
        sum[i] = sum[i - 1] + stone[i];
39
    }
40
    printf("%s\n", DFS(1, N, 0) ? "DA" : "NE");
41
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
42
    return 0;
43
}
44

45
template<typename T>
46
inline T read(void){
47
    T ret(0);
48
    short flag(1);
49
    char c = getchar();
50
    while(c != '-' && !isdigit(c))c = getchar();
51
    if(c == '-')flag = -1, c = getchar();
52
    while(isdigit(c)){
53
        ret *= 10;
54
        ret += int(c - '0');
55
        c = getchar();
56
    }
57
    ret *= flag;
58
    return ret;
59
}

T3 Logičari

题面

对一个基环树进行染色，使每个点有且仅有一个，不包括自身的，与他相连的点被染色，求最少染色数（包括无解情况）。

$n \le 10^5$ 。

Examples

Input_1

4
1 2
2 3
3 4
4 1

Output_1

2

Input_2

3
1 2
2 3
3 1

Output_2

-1

Input_3

7
1 2
2 3
3 4
4 5
5 6
6 7
2 4

Output_3

4

Solution

思路

该说不说这题的细节是真的多，改了一下午才过了...

$\texttt{DP}$ 。

$\texttt{DP}$ 即可解决，而基环树与普通树的区别，也就是多了一条边，使“树”上有且仅有一个环，那么我们的思路也就是将他转化为普通的树上问题。

$\texttt{DP}$ 的时候随时考虑这两个点。

找环上边

一般有两种方法，一种是维护并查集，当新的边连接的两个节点，是同一颗子树上的时候，要找的就是这个边。

$\texttt{DFS}$ 遍历整个树，当访问到了非父亲节点，但曾经访问过的节点时便说明这个边是环上的边。


xxxxxxxxxx
6
1
void FindLoop(int p, int fa){
2
    for(auto i = head[p]; i; i = i->nxt){
3
        if(i->to != fa && vis[i->to]){loop = make_pair(p, i->to); return;}
4
        if(i->to != fa){vis[i->to] = true; FindLoop(i->to, p);}
5
    }
6
}

删边

如果用的并查集维护，直接记录下并不将这个边存到树里即可。

$\texttt{DFS}$ ，那么可以考虑直接遍历找到点删除，或每次调用的时候都判断是否为删掉的这个边。


xxxxxxxxxx
19
1
void RemoveLoop(void){
2
    for(auto i = head[loop.first], lasti = (Edge*)npt; i; lasti = i, i = i->nxt){
3
        if(i->to == loop.second){
4
            lasti
5
                ? lasti->nxt = i->nxt
6
                : head[loop.first] = i->nxt;
7
            break;
8
        }
9
    }
10
    for(auto i = head[loop.second], lasti = (Edge*)npt; i; lasti = i, i = i->nxt){
11
        if(i->to == loop.first){
12
            lasti
13
                ? lasti->nxt = i->nxt
14
                : head[loop.second] = i->nxt;
15
            break;
16
        }
17
    }
18
    tie(root1, root2) = loop;
19
}

状态设计

$\texttt{DP}$ $\texttt{root1}$ $\texttt{root2}$ 。

$\texttt{true}$ $\texttt{false}$ 。

$dp(i, j, k, l, m)$ $i$ $j, k$ $l,m$ 。

因为每个点有且只有一个与之相连的节点会被染色，所以我们可以考虑先假设当前节点所有子节点都不染色，并计算求和，然后分别枚举其每一个子节点，计算如果将该子节点涂色最终需要涂多少点，并取最小值。

但是这题的最大难点我认为就是上面这些过程中合法性的判断，也就是细节的处理。

$\texttt{DFS}$ + 记忆化实现。

细节处理

首先我们需要考虑，哪些状态是不可能出现的：

遍历到某个根节点，但当前状态与根节点已经定下来的状态不同。
遍历到某个根节点，父亲节点已被染色，且两个根节点都被染色，导致其中某个根节点，考虑上被临时删除的边之后有两个相连的点被染色。


xxxxxxxxxx
6
1
if(
2
    (currentPosition == root1 && currentStatus != root1Status) ||
3
    (currentPosition == root2 && currentStatus != root2Status) ||
4
    (currentPosition == root1 && fatherStatus && root2Status) ||
5
    (currentPosition == root2 && fatherStatus && root1Status)
6
)return DEFAULT_DP = INF;

然后我们需要考虑，什么时候当前的节点的子节点都不能被染色：

父节点已经被染色，即当前节点已经有了一个节点与之相连且被染色。
$1$ 同理。


xxxxxxxxxx
5
1
if(
2
    fatherStatus ||
3
    (currentPosition == root1 && root2Status) ||
4
    (currentPosition == root2 && root1Status)
5
) ret = min(ret, sonCost);

还有个很重要的点就是我们假设都不染色进行求和操作的时候会爆 int 所以需要在求和时需要开 long long。

主函数

回到我们之前说的，要枚举两个根节点的状态，我们可以考虑令其从其中某个根节点开始遍历，显然会简便很多，显然一共可能有如下四种情况。


xxxxxxxxxx
9
1
int ans = min(
2
    {
3
        Tintage(root1, 0, 0, 0, 0, -1),
4
        Tintage(root1, 0, 0, 0, 1, -1),
5
        Tintage(root1, 1, 0, 1, 0, -1),
6
        Tintage(root1, 1, 0, 1, 1, -1),
7
        INF
8
    }
9
);

Code


xxxxxxxxxx
135
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define INF 11451400
8
#define DEFAULT_DP dp[currentPosition][currentStatus][fatherStatus][root1Status][root2Status]
9

10
using namespace std;
11

12
mt19937 rnd(random_device{}());
13
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
14

15
typedef unsigned int uint;
16
typedef unsigned long long unll;
17
typedef long long ll;
18

19
template<typename T = int>
20
inline T read(void);
21

22
int N;
23
bool vis[110000];
24
pair < int, int >/*from, to*/ loop;
25
int root1, root2;
26

27
struct Edge{
28
    Edge* nxt;
29
    int to;
30
    void* operator new(size_t);
31
    Edge(Edge* nxt, int to):nxt(nxt), to(to){;}
32
    Edge(void) = default;
33
}eData[210000];
34
void* Edge::operator new(size_t){static Edge* P = eData; return ++P;}
35

36
Edge* head[110000];
37
int dp[110000][2][2][2][2]; /*CurrentPosition, CurrentStatus, FatherStatus, Root1Status, Root2Status*/
38

39
void FindLoop(int = 1, int = -1);
40
void RemoveLoop(void);
41
int Tintage(int, bool, bool, bool, bool, int);
42

43
int main(){
44
    memset(dp, -1, sizeof(dp));
45
    N = read();
46
    for(int i = 1; i <= N; ++i){
47
        int from = read(), to = read();
48
        head[from] = new Edge(head[from], to);
49
        head[to] = new Edge(head[to], from);
50
    }
51
    FindLoop();
52
    RemoveLoop();
53
    int ans = min(
54
        {
55
            Tintage(root1, 0, 0, 0, 0, -1),
56
            Tintage(root1, 0, 0, 0, 1, -1),
57
            Tintage(root1, 1, 0, 1, 0, -1),
58
            Tintage(root1, 1, 0, 1, 1, -1),
59
            INF
60
        }
61
    );
62
    printf("%d\n", ans == INF ? -1 : ans);
63
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
64
    return 0;
65
}
66
int Tintage(int currentPosition, bool currentStatus, bool fatherStatus, bool root1Status, bool root2Status, int fatherPosition){
67
    if(~DEFAULT_DP)return DEFAULT_DP;
68
    if(
69
        (currentPosition == root1 && currentStatus != root1Status) ||
70
        (currentPosition == root2 && currentStatus != root2Status) ||
71
        (currentPosition == root1 && fatherStatus && root2Status) ||
72
        (currentPosition == root2 && fatherStatus && root1Status)
73
    )return DEFAULT_DP = INF;
74
    ll sonCost(currentStatus);
75
    for(auto i = head[currentPosition]; i; i = i->nxt)
76
        if(i->to != fatherPosition)
77
            sonCost += Tintage(i->to, false, currentStatus, root1Status, root2Status, currentPosition);
78
    ll ret(INF);
79
    if(
80
        fatherStatus ||
81
        (currentPosition == root1 && root2Status) ||
82
        (currentPosition == root2 && root1Status)
83
    ) ret = min(ret, sonCost);
84
    else 
85
        for(auto i = head[currentPosition]; i; i = i->nxt)
86
            if(i->to != fatherPosition)
87
                ret = min({
88
                    ret,
89
                    (ll)INF,
90
                    sonCost - Tintage(i->to, false, currentStatus, root1Status, root2Status, currentPosition)
91
                            + Tintage(i->to, true,  currentStatus, root1Status, root2Status, currentPosition)
92
                });
93
    return DEFAULT_DP = ret;
94
}
95
void RemoveLoop(void){
96
    for(auto i = head[loop.first], lasti = (Edge*)npt; i; lasti = i, i = i->nxt){
97
        if(i->to == loop.second){
98
            lasti
99
                ? lasti->nxt = i->nxt
100
                : head[loop.first] = i->nxt;
101
            break;
102
        }
103
    }
104
    for(auto i = head[loop.second], lasti = (Edge*)npt; i; lasti = i, i = i->nxt){
105
        if(i->to == loop.first){
106
            lasti
107
                ? lasti->nxt = i->nxt
108
                : head[loop.second] = i->nxt;
109
            break;
110
        }
111
    }
112
    tie(root1, root2) = loop;
113
}
114
void FindLoop(int p, int fa){
115
    for(auto i = head[p]; i; i = i->nxt){
116
        if(i->to != fa && vis[i->to]){loop = make_pair(p, i->to); return;}
117
        if(i->to != fa){vis[i->to] = true; FindLoop(i->to, p);}
118
    }
119
}
120

121
template<typename T>
122
inline T read(void){
123
    T ret(0);
124
    short flag(1);
125
    char c = getchar();
126
    while(c != '-' && !isdigit(c))c = getchar();
127
    if(c == '-')flag = -1, c = getchar();
128
    while(isdigit(c)){
129
        ret *= 10;
130
        ret += int(c - '0');
131
        c = getchar();
132
    }
133
    ret *= flag;
134
    return ret;
135
}

T4 Set

题目背景
$\texttt{SET}$ $\texttt{triplet of cards}$ $\texttt{Marin}$ $\texttt{Josip}$ 很快就对这个游戏感到无趣，并对其进行了加强。
题目描述
$1, 2, 3$ $k$ $n$ 张卡片，卡片之间是无序的。
$\texttt{SET}$ $\texttt{triplet of cards}$ $\texttt{same}$ $\texttt{pairwise different}$ $S_i, S_j, S_k$ ，则一定满足如下条件：
$i \lt j \lt k$
$\forall x \in \left[1, k\right]$ $S_i(x) = S_j(x) = S_k(x)$ $S_i(x) \neq S_j(x) \neq S_k(x)$
$(1123, 1322, 1221)$ $1, 3$ $2,4$ 位各不相同。
$\texttt{SET}$ 。
输入格式
$n, k$ 。
$n$ $1, 2, 3$ $k$ 的序列，代表着一张卡片。
保证每张卡片上的序列不同。
输出格式
$\texttt{SET}$ 的数量。
说明 / 提示
样例 3 解释
$\texttt{SET}$ $(S_1, S_2, S_3)$ $(S_1, S_4, S_5)$ 。
数据范围
$1 \le k \le 12, 1 \le n \le 3^k$ $S_i$ $1 \le S_i \le 3$ 。
Subtask 特殊限制分数
1 $k \le 5$ 10
2 $k \le 7$ 30
3 无特殊限制 70

Subtask	特殊限制	分数
1	$k \le 5$	10
2	$k \le 7$	30
3	无特殊限制	70

题面（重新翻译了一个新的题面，已经提交到 Luogu）

Examples

Input_1

3 4
1123
1322
1221

Output_1

1

Input_2

2 2
11
22

Output_2

0

Input_3

5 3
111
222
333
123
132

Output_3

2

Solution

$\texttt{FWT}$ $\texttt{FWT}$ $k$ $\texttt{FWT}$ $\texttt{FWT}$ 。

戳此链接去看刚写完的 FWT

$\texttt{SET}$ $1, 2, 3 (\texttt{unordered})$ 。

思考这个规律有什么性质

性质1

$m_{i, x}, m_{j, x}, m_{k, x}$ 一定有：

m_{i, x} + m_{j, x} + m_{k, x} \equiv 0 (mod 3)

证明：~~这么显然还需要证明吗~~。

性质2

$\texttt{SET}$ $\texttt{uniquely determined}$ 。

证明：一共就三个可能的数，这个也很显然吧

$S$ $1, 2, 3$ $S$ $\circ$ ，为了令其符合结合律，我们考虑使其符合以下规律及交换律：

\begin{aligned} 1 \circ 1 = 1 \\ 2 \circ 2 = 3 \\ 3 \circ 3 = 2 \\ 1 \circ 2 = 2 \\ 1 \circ 3 = 3 \\ 2 \circ 3 = 1 \end{aligned}

$\bmod{3}$ $(\mathbb{N}, \bmod{3})$ $\bmod{3}$ 构成的代数系统相同，详细地表示即为：

\begin{aligned} 1 mod 3 = 1 \\ 2 mod 3 = 2 \\ 3 mod 3 = 0 \end{aligned}

此时我们会发现更多的性质：

性质3

$\circ$ 运算后数值不改变。即：

a \circ a \circ a = a

$\circ$ 的定义可知十分显然。

性质4

$\circ$ 的交换律与结合律。

证明：显然成立。

性质5

对于性质1，由新的定义可以转化为如下式子：

(m_{i, x} \circ m_{j, x} \circ m_{k, x}) mod 3 = 1

也就是：

m_{i, x} \circ m_{j, x} \circ m_{k, x} = 1

$F(x)$ $\texttt{triplet}$ $\forall x \in \left[ 1, m \right]$ 都有：

m_{i, x} \circ m_{j, x} \circ m_{k, x} = x

$F(0)$ $\texttt{SET}$ 的数量。

$\texttt{triplet}$ 中三个序列的排列）

$g_n$ ，有：

\begin{matrix} g_{i} = {\begin{cases} 0 & u n e x i s t \\ 1 & e x i s t \end{cases} \end{matrix}

$i$ 表示的不是一个数字，而是一个序列，由数据范围可以考虑按位存取，最简单的想法是类似离散化，把它按三进制，压成一个数，也可以考虑用两位二进制存这个数。

$n$ 个序列中。

容易看出会有如下式子：

F (x) = \sum_{i \circ j \circ k = x} g_{i} \times g_{j} \times g_{k}

当然这个式子也可以记作：

F = g \times g \times g

$F(1)$ $0$ $F(0)$ ，即：

F (0) = \sum_{i \circ j \circ k = 0} g_{i} \times g_{j} \times g_{k}

$\texttt{FWT}$ 。

FWT（快速沃尔什变换）一般用于处理形如如下式子的卷积：
$C (x) = \sum_{i \circ j = x} A (i) \times B (j)$
$\circ$ $and, or, xor$ 。

$\texttt{FWT}$ $\texttt{FWT}$ 的思想去考虑本题。

FWT 的思路

$\texttt{FWT}$ 可以考虑记作：

F W T (A)

我们需要让这个变换满足以下性质：

F W T (A) * F W T (B) = F W T (C)

且：

A \circ B = C

对于不同的运算都有着与之对应的不同的变换方式，我们的目的就是要找到一种优秀的变换并快速地进行变换。

这里额外说一下对于多项式约定俗成的几种运算表示什么，相信你们一定都知道~~（主要因为我最开始做这道题的时候有的符号理解错了）~~
$A$ $N$ $B$ $M$ 次。
$\max(N, M) = P$ 。
$\begin{aligned} (A, B) = (A (0), A (1), \dots, A (N), B (0), B (1), \dots, B (M)) 即拼接两个多项式 \\ A + B = (A (0) + B (0), A (1) + B (1), \dots, A (P) + B (P)) 即按位相加 \\ A - B = (A (0) - B (0), A (1) - B (1), \dots, A (P) - B (P)) 即按位相减 \\ A * B = (A (0) * B (0), A (1) * B (1), \dots, A (P) * B (P)) 即按位相乘，注意不是卷积 \\ A \times B = (\sum_{i + j = 0} A (i) \times B (j), \sum_{i + j = 1} A (i) \times B (j), \dots, \sum_{i + j = N + M} A (i) \times B (j)) 多项式卷积 \\ A \circ B = (\sum_{i \circ j = 0} A (i) \times B (j), \sum_{i \circ j = 1} A (i) \times B (j), \dots) 可以理解为广义上的卷积 \end{aligned}$

本题如何做？

$S$ $\circ$ $\texttt{FWT}$ 变换。

$\texttt{FWT}$ 变换式子，我们就会发现这些式子的存在本身就充满着人类智慧，似乎不像是可以很简单推导出来的，但是如果我们从矩阵的角度去考虑，并基于已有的运算的转移矩阵，就可以较为方便的得出结论。

如何推式子？

$\circ$ ：

\begin{aligned} 1 \circ 1 = 1 \\ 2 \circ 2 = 3 \\ 3 \circ 3 = 2 \\ 1 \circ 2 = 2 \\ 1 \circ 3 = 3 \\ 2 \circ 3 = 1 \end{aligned}

$\texttt{FWT}$ 的坑填了...

我们要求的可以理解为是以下的式子：

C (x) = \sum_{i \circ j = x} A (i) \times B (j)

$\texttt{FWT}$ $3 \times 3$ $\circ$ $1$ 开始，所以与标准的矩阵可能有些差距。

$T$ $(i, j)$ $\omega(i, j)$ ，满足：

ω (x, i) \times ω (x, j) = ω (x, k) (i \circ j = k)

观察运算的性质，和三进制下的异或运算性质较为相似，可以考虑尝试范德蒙德矩阵：

[\begin{matrix} \neg \exists & \neg \exists & \neg \exists & \neg \exists \\ \neg \exists & 1 & 1 & 1 \\ \neg \exists & 1 & ω_{3}^{1} & ω_{3}^{2} \\ \neg \exists & 1 & ω_{3}^{2} & ω_{3}^{4} \end{matrix}]

可以化简为：

[\begin{matrix} \neg \exists & \neg \exists & \neg \exists & \neg \exists \\ \neg \exists & 1 & 1 & 1 \\ \neg \exists & 1 & ω_{3} & ω_{3}^{2} \\ \neg \exists & 1 & ω_{3}^{2} & ω_{3} \end{matrix}]

逆矩阵同理容易得出为：

\begin{matrix} \frac{1}{3} [\begin{matrix} \neg \exists & \neg \exists & \neg \exists & \neg \exists \\ \neg \exists & 1 & 1 & 1 \\ \neg \exists & 1 & ω_{3}^{- 1} & ω_{3}^{- 2} \\ \neg \exists & 1 & ω_{3}^{- 2} & ω_{3}^{- 1} \end{matrix}] \end{matrix}

可以化简为：

\begin{matrix} \frac{1}{3} [\begin{matrix} \neg \exists & \neg \exists & \neg \exists & \neg \exists \\ \neg \exists & 1 & 1 & 1 \\ \neg \exists & 1 & ω_{3}^{2} & ω_{3} \\ \neg \exists & 1 & ω_{3} & ω_{3}^{2} \end{matrix}] \end{matrix}

显然我们可以算出：

\begin{aligned} ω_{3} & = \cos (\frac{2 π}{3}) + \sin (\frac{2 π}{3}) i \\ = - \frac{1}{2} + \frac{\sqrt{3}}{2} i \end{aligned}

且：

\begin{aligned} ω_{3}^{2} & = (- \frac{1}{2} + \frac{\sqrt{3}}{2} i)^{2} \\ = - \frac{1}{2} - \frac{\sqrt{3}}{2} i \end{aligned}

到此我们便可以求出来最终的结果了。

这里还有两个小细节需要注意：

两个小细节

$\texttt{IFWT}$ $\dfrac{1}{3}$ $3^n$ $\log_3^{3^n} = n$ $3^n$ $\texttt{FFT}$ 挺像的），不过属于常数优化，差别不大。

然后还需要注意当我们算出来常数项之后，并不能直接输出，观察一下性质 3：

a \circ a \circ a = a

$i = j = k$ $N$ 。

$3!$ $6$ 。

$\dfrac{F(0) - N}{6}$ 。

至此，这道卡了我两天多的题，终于结束了。

（记得开 long long）

Code


xxxxxxxxxx
90
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define comp complex < long double > 
8

9
using namespace std;
10

11
mt19937 rnd(random_device{}());
12
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
13

14
typedef unsigned int uint;
15
typedef unsigned long long unll;
16
typedef long long ll;
17

18
template<typename T = int>
19
inline T read(void);
20
inline int read3(void);
21

22
int N, M;
23
// 3^12 = 531441
24
comp poly[1100000];
25
comp omega(-0.5, 0.5 * sqrt(3));
26
comp omega2(conj(omega));
27
enum pattern{IFWT = 0, _FWT};
28
void FWT(comp*, int, pattern);
29

30
int main(){
31
    N = read(), M = read();
32
    for(int i = 1; i <= N; ++i)poly[read3()].real(1.0);
33
    int lim(1), cnt(0);
34
    while(cnt++ < M)lim *= 3;
35
    FWT(poly, lim, _FWT);
36
    for(int i = 0; i < lim; ++i)poly[i] = poly[i] * poly[i] * poly[i];
37
    FWT(poly, lim, IFWT);
38
    ll ans = (poly[0].real() / (long double)lim) + 0.5;
39
    printf("%lld\n", (ans - N) / 6);
40
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
41
    return 0;
42
}
43
void FWT(comp* poly, int lim, pattern pat){
44
    for(int len = 1; len < lim; len *= 3)
45
        for(int px = 0; px < lim; px += 3 * len)
46
            for(int p = 0; p < len; ++p){
47
                int pos1(px + p + len * 0),
48
                    pos2(px + p + len * 1),
49
                    pos3(px + p + len * 2);
50
                comp pol1 = poly[pos1];
51
                comp pol2 = poly[pos2];
52
                comp pol3 = poly[pos3];
53
                if(pat == _FWT){
54
                    poly[pos1] = pol1 + pol2 + pol3;
55
                    poly[pos2] = pol1 + pol2 * omega + pol3 * omega2;
56
                    poly[pos3] = pol1 + pol2 * omega2 + pol3 * omega;
57
                }else{
58
                    poly[pos1] = pol1 + pol2 + pol3;
59
                    poly[pos2] = pol1 + pol2 * omega2 + pol3 * omega;
60
                    poly[pos3] = pol1 + pol2 * omega + pol3 * omega2;
61
                }
62
            }
63
}
64

65
inline int read3(void){
66
    int ret(0);
67
    char c = getchar();
68
    while(!isdigit(c))c = getchar();
69
    while(isdigit(c)){
70
        ret *= 3;
71
        ret += int(c - '0' - 1);
72
        c = getchar();
73
    }
74
    return ret;
75
}
76
template<typename T>
77
inline T read(void){
78
    T ret(0);
79
    short flag(1);
80
    char c = getchar();
81
    while(c != '-' && !isdigit(c))c = getchar();
82
    if(c == '-')flag = -1, c = getchar();
83
    while(isdigit(c)){
84
        ret *= 10;
85
        ret += int(c - '0');
86
        c = getchar();
87
    }
88
    ret *= flag;
89
    return ret;
90
}

T5 Volontiranje

~~这题比 T4 简单多了。~~

题面

$n$ 的排列，求最多的不交叉最长上升子序列的（即每个数只能用一次）。~~（是的就这么简洁）~~

$n \le 10^6$ 。

Examples

Input_1

3
1 2 3

Output_1

1 3
1 2 3

Input_2

4
4 3 2 1

Output_2

4 1
1
2
3
4

Input_3

7
2 1 6 5 7 3 4

Output_3

2 3
1 3 5
2 6 7

Solution

$O(n \log n)$ 求即可，可以用 lower_bound 求。

$x$ $y$ ，把每个数丢到二维坐标系里面观察性质，比如对于 Input_3，最后会形成下图：

$x = 1$ $x$ $y$ 递减的点与初始点划分到同一层级。

也就是如下：

注意这里的层级划分是左下开右上闭的。

于是我们便可以发现，对于每一个 LIS 都应该是从每一个层级中选择一个点并且符合，下一层级的点符合在当前点的右上。

$A, B$ $1$ $C, D, F$ $2$ $E, G$ $3$ 。

$LIS_i = k$ $k$ $i$ 作为同一层级。

$AD$ $BC$ $AC$ $BD$ 都可以符合要求，是两组不同的合法解，但是考虑如下情况：

（这里为了方便表述省略了一些点）

$A$ $C$ $BD$ $AD$ $BC$ 不合法。故显然优先连结未选择里面横坐标更小的是最优方案。

至此我们的推导已经结束，可以进行实现了。

Code


xxxxxxxxxx
90
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7

8
/******************************
9
abbr
10

11
******************************/
12

13
using namespace std;
14

15
mt19937 rnd(random_device{}());
16
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21

22

23

24
template<typename T = int>
25
inline T read(void);
26

27
vector < int > LISv;
28
pair < int, int > LIS[1100000];
29
int N;
30
vector < int > current;
31
vector < int > tier[1100000];
32
int arr[1100000];
33
vector < vector < int > > anss;
34
int main(){
35
    N = read();
36
    for(int i = 1; i <= N; ++i){
37
        arr[i] = read();
38
        if(LISv.empty() || LISv.back() < arr[i])LISv.push_back(arr[i]), tier[(int)LISv.size()].push_back(i);
39
        else{
40
            auto pos = lower_bound(LISv.begin(), LISv.end(), arr[i]);
41
            int len = distance(LISv.begin(), pos) + 1;
42
            *pos = arr[i];
43
            tier[len].push_back(i);
44
        }
45
    }
46
    int maxLen = (int)LISv.size();
47
    for(int i = 1; i <= maxLen; ++i)
48
        reverse(tier[i].begin(), tier[i].end());
49
    while(true){
50
        if(current.empty()){
51
            if(tier[1].empty())break;
52
            current.push_back(tier[1].back());
53
            tier[1].pop_back();
54
        }else if((int)current.size() == maxLen){
55
            anss.push_back(current);
56
            current.clear();
57
        }else{
58
            int pos = current.size() + 1;
59
            int last = current.back();
60
            while(!tier[pos].empty() && tier[pos].back() < last)tier[pos].pop_back();
61
            if(tier[pos].empty() || arr[tier[pos].back()] < arr[last])current.pop_back();
62
            else current.push_back(tier[pos].back()), tier[pos].pop_back();
63
        }
64
    }
65
    printf("%d %d\n", (int)anss.size(), maxLen);
66
    for(auto i : anss){
67
        for(auto j : i)printf("%d ", j);
68
        printf("\n");
69
    }
70
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
71
    return 0;
72
}
73

74

75

76
template<typename T>
77
inline T read(void){
78
    T ret(0);
79
    short flag(1);
80
    char c = getchar();
81
    while(c != '-' && !isdigit(c))c = getchar();
82
    if(c == '-')flag = -1, c = getchar();
83
    while(isdigit(c)){
84
        ret *= 10;
85
        ret += int(c - '0');
86
        c = getchar();
87
    }
88
    ret *= flag;
89
    return ret;
90
}

UPD

update-2022_08_30 T1-T3

update-2022_09_01 完成一部分的 T4

update-2022_09_02 T4 肝完

update-2022_09_04 初稿

update-2022_09_04 发现 T4 之前算法假掉了，修改了一下

update-2022_09_06 完善 latex 以符合 Luogu 题解要求