COCI2021-2022 Contest1 题解

Tsawke · 2022-09-04 23:04:29 · 个人记录

COCI2021-2022 Contest1 题解

[TOC]

更好的阅读体验戳此进入

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

原题面链接

Luogu题面

T1 Ljeto

题意

给你 n 条信息，表示 t_i 时刻 a_i 击中 b_i ，得为 100 ，然后如果有十秒以内连续击中两次的额外加 50 分。

• \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

题面（重新翻译了一个新的题面，已经提交到 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

需要用到很多 FWT 思想，阅读之前请先完全理解 FWT， k 进制 FWT，及用转移矩阵进行变换的 FWT。

戳此链接去看刚写完的 FWT

观察题意，发现对于每个 SET 的同一位置的三个数，要么是完全相同的三个数，要么分别是 1, 2, 3 (unordered) 。

思考这个规律有什么性质

性质1

显然设这三个数为 m_{i, x}, m_{j, x}, m_{k, x} 一定有：

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

性质2

当这个 SET 中的两个序列被确定之后，第三个序列就有且仅有一种情况，或者说 uniquely \ \ determined 。

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

然后我们发现这两个性质无法继续向下推，于是我们考虑假设存在一个自洽的代数系统 S ，其中只有 1, 2, 3 三个数字，定义 S 中一种二元运算 \circ ，为了令其符合结合律，我们考虑使其符合以下规律及交换律：

同时我们考虑定义一元运算符 \bmod{3} ，其运算规律与代数系统 (\mathbb{N}, \bmod{3}) ，即自然数和 \bmod{3} 构成的代数系统相同，详细地表示即为：

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

性质3

一个数与其自身进行两次 \circ 运算后数值不改变。即：

证明：根据 \circ 的定义可知十分显然。

性质4

运算 \circ 的交换律与结合律。

证明：显然成立。

性质5

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

也就是：

此时根据这些性质，如果我们令 F(x) 表示题意中有多少种不同的 triplet 符合对于 \forall x \in \left[ 1, m \right] 都有：

则显然 F(0) 表示所有不同的 SET 的数量。

（注意这里并不是本质不同，所以也可以理解为 triplet 中三个序列的排列）

这里我们定义序列 g_n ，有：

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

存在与否指的是是否在题目给出的 n 个序列中。

容易看出会有如下式子：

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

而我们需要的便是这个式子的常数项 F(1) ，注意这里因为我们的代数系统中不存在 0 ，但如果我们用三进制离散化压位来存的话，最终需要的就是 F(0) ，即：

仔细观察一般的式子，这像什么？显然是多项式的各种快速变换！或者进一步说，很像 FWT。

FWT（快速沃尔什变换）一般用于处理形如如下式子的卷积：

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

此处的 \circ 一般为 \&, |, ^， 也就是 and, or, xor 。

发现我们当前的式子很像 FWT，所以也可以以 FWT 的思想去考虑本题。

FWT 的思路

与大多数多项式快速变换的思路一样，我们的目的都是找到一种变换，对于 FWT 可以考虑记作：

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

且：

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

这里额外说一下对于多项式约定俗成的几种运算表示什么，相信你们一定都知道（主要因为我最开始做这道题的时候有的符号理解错了）

这里我们假设 A 最高次为 N 次， B 最高次为 M 次。

令 \max(N, M) = P 。

\begin{aligned} &(A, B) = (\ A(0), A(1), \cdots, A(N), B(0), B(1), \cdots, B(M) \ ) \ \texttt{即拼接两个多项式} \\ &A + B = (\ A(0) + B(0), A(1) + B(1), \cdots, A(P) + B(P) \ ) \ \texttt{即按位相加} \\ &A - B = (\ A(0) - B(0), A(1) - B(1), \cdots, A(P) - B(P) \ ) \ \texttt{即按位相减} \\ &A \ast B = (\ A(0) \ast B(0), A(1) \ast B(1), \cdots, A(P) \ast B(P) \ ) \ \texttt{即按位相乘，注意不是卷积} \\ &A \times B = (\ \sum_{i + j = 0}A(i) \times B(j), \sum_{i + j = 1}A(i) \times B(j), \cdots, \sum_{i + j = N + M}A(i) \times B(j) \ ) \ \texttt{多项式卷积} \\ &A \circ B = (\ \sum_{i \circ j = 0}A(i) \times B(j), \sum_{i \circ j = 1}A(i) \times B(j), \cdots \ ) \ \texttt{可以理解为广义上的卷积} \end{aligned}

本题如何做？

通过上面的信息显然我们便可确定本题的核心：找出在代数系统 S 中运算 \circ 的卷积运算时的广义上的 FWT 变换。

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

如何推式子？

再次观察我们定义的这个二元运算符 \circ ：

题外话：写到这里突然发现我好像推不出来这个式子，于是决定先去把 FWT 的坑填了...

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

用和 FWT 一样的思想，因为我们只有三个数，所以可以考虑构造一个 3 \times 3 的转移矩阵，但是注意我们定义的运算 \circ 下标从 1 开始，所以与标准的矩阵可能有些差距。

我们需要保证对于转移矩阵 T 的 (i, j) 元，记作 \omega(i, j) ，满足：

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

可以化简为：

逆矩阵同理容易得出为：

可以化简为：

显然我们可以算出：

且：

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

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

两个小细节

首先我们在做完 IFWT 之后需要乘一个 \dfrac{1}{3} ，我们当然可以每次都做一个除法，但是观察发现，项数需要满足 3^n 形式，而层数也就是 \log_3^{3^n} = n ，所以也可以在最后答案除一个 3^n （和 FFT 挺像的），不过属于常数优化，差别不大。

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

在运算的时候我们显然会把 i = j = k 的情况算在内了，而显然这是不合法的，所以需要减掉 N 。

并且，我们在运算的时候求的是不同，而非本质不同，也就是算的是排列，而我们要求的是组合，所以最后除一个 3! ，也就是 6 。

综上所述，我们将常数项算出来后最终答案就是 \dfrac{F(0) - N}{6} 。

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

（记得开 long long）

Code

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr
#define comp complex < long double > 

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;

template<typename T = int>
inline T read(void);
inline int read3(void);

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

int main(){
    N = read(), M = read();
    for(int i = 1; i <= N; ++i)poly[read3()].real(1.0);
    int lim(1), cnt(0);
    while(cnt++ < M)lim *= 3;
    FWT(poly, lim, _FWT);
    for(int i = 0; i < lim; ++i)poly[i] = poly[i] * poly[i] * poly[i];
    FWT(poly, lim, IFWT);
    ll ans = (poly[0].real() / (long double)lim) + 0.5;
    printf("%lld\n", (ans - N) / 6);
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}
void FWT(comp* poly, int lim, pattern pat){
    for(int len = 1; len < lim; len *= 3)
        for(int px = 0; px < lim; px += 3 * len)
            for(int p = 0; p < len; ++p){
                int pos1(px + p + len * 0),
                    pos2(px + p + len * 1),
                    pos3(px + p + len * 2);
                comp pol1 = poly[pos1];
                comp pol2 = poly[pos2];
                comp pol3 = poly[pos3];
                if(pat == _FWT){
                    poly[pos1] = pol1 + pol2 + pol3;
                    poly[pos2] = pol1 + pol2 * omega + pol3 * omega2;
                    poly[pos3] = pol1 + pol2 * omega2 + pol3 * omega;
                }else{
                    poly[pos1] = pol1 + pol2 + pol3;
                    poly[pos2] = pol1 + pol2 * omega2 + pol3 * omega;
                    poly[pos3] = pol1 + pol2 * omega + pol3 * omega2;
                }
            }
}

inline int read3(void){
    int ret(0);
    char c = getchar();
    while(!isdigit(c))c = getchar();
    while(isdigit(c)){
        ret *= 3;
        ret += int(c - '0' - 1);
        c = getchar();
    }
    return ret;
}
template<typename T>
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

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

考虑求 \texttt{LIS} 的长度直接 O(n \log n) 求即可，可以用 lower_bound 求。

而对于有哪些 \texttt{LIS} ，我们则需要找到其中的一些性质，考虑将每个数的下标作为 x ，数值作为 y ，把每个数丢到二维坐标系里面观察性质，比如对于 Input_3 ，最后会形成下图：

观察这个奇怪的图形我们可以考虑从 x = 1 开始划分层级，把 x 递增而 y 递减的点与初始点划分到同一层级。

也就是如下：

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

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

这里我们考虑如何分层，考虑当我们计算 LIS 时，一般用的状态是，以当前点为结尾的 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

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

#define PI M_PI
#define E M_E
#define npt nullptr

/******************************
abbr

******************************/

using namespace std;

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

typedef unsigned int uint;
typedef unsigned long long unll;
typedef long long ll;

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

vector < int > LISv;
pair < int, int > LIS[1100000];
int N;
vector < int > current;
vector < int > tier[1100000];
int arr[1100000];
vector < vector < int > > anss;
int main(){
    N = read();
    for(int i = 1; i <= N; ++i){
        arr[i] = read();
        if(LISv.empty() || LISv.back() < arr[i])LISv.push_back(arr[i]), tier[(int)LISv.size()].push_back(i);
        else{
            auto pos = lower_bound(LISv.begin(), LISv.end(), arr[i]);
            int len = distance(LISv.begin(), pos) + 1;
            *pos = arr[i];
            tier[len].push_back(i);
        }
    }
    int maxLen = (int)LISv.size();
    for(int i = 1; i <= maxLen; ++i)
        reverse(tier[i].begin(), tier[i].end());
    while(true){
        if(current.empty()){
            if(tier[1].empty())break;
            current.push_back(tier[1].back());
            tier[1].pop_back();
        }else if((int)current.size() == maxLen){
            anss.push_back(current);
            current.clear();
        }else{
            int pos = current.size() + 1;
            int last = current.back();
            while(!tier[pos].empty() && tier[pos].back() < last)tier[pos].pop_back();
            if(tier[pos].empty() || arr[tier[pos].back()] < arr[last])current.pop_back();
            else current.push_back(tier[pos].back()), tier[pos].pop_back();
        }
    }
    printf("%d %d\n", (int)anss.size(), maxLen);
    for(auto i : anss){
        for(auto j : i)printf("%d ", j);
        printf("\n");
    }
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
    return 0;
}

template<typename T>
inline T read(void){
    T ret(0);
    short flag(1);
    char c = getchar();
    while(c != '-' && !isdigit(c))c = getchar();
    if(c == '-')flag = -1, c = getchar();
    while(isdigit(c)){
        ret *= 10;
        ret += int(c - '0');
        c = getchar();
    }
    ret *= flag;
    return ret;
}

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 之前算法假掉了，修改了一下