ResurrectionTX

分类

比赛(7) 笔记(6) 题解(32)

/ 注册

全部文章（共45篇）

Luogu P5840 【[COCI2015]Divljak】

Description 传送门 Solution 首先看到这题就想SAM对吧，然后qwaszx写了一发常数太大过不了就果断改AC自动机对吧。考虑对\(S\)建立\(AC\)自动机，因为字符串的所有前缀的所有后缀是字符串的所有子串，而\(fail\)指针指的状态就是该状态的最长可识别后缀...

AC自动机字符串 Luogu

2020-06-12

0 435

Luogu P3295 【[SCOI2016]萌萌哒】

Description 传送门 Solution 首先先考虑如果限制不是区间，而是告诉你两个位置的字符相等的做法。这样的话，我们可以把相等的位置加进一些集合里，最后答案就是\(9 \times 10 ^ {num - 1}\)，其中\(num\)代表不同的集合个数，这个可以简单地用并查...

倍增并查集 Luogu

2020-06-12

0 355

Codeforces 741D 【Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths】

Description 传送门 Solution 将字符串的路径看做二进制数，那么一个路径上的字符能重新调整成回文串的充要条件是从根到两个点的二进制数异或和为\(0\)或者\(2\)的幂。这是因为在一个回文串里，出现次数为奇数的字符只能有一个或者没有。那么问题现在变成\(x\)的子树里...

dsu on tree Codeforces

2020-06-12

0 413

Codeforces 235C 【Cyclical Quest】

Description 传送门 Solution 考虑循环同构的性质，每次相当于从最前面删去一个字符，从最后面加上一个字符。在\(SAM\)里对应着往上跳\(fa\)或不跳和走对应的字符串转移边。考虑对于长度为\(l\)的串，最多删\(l\)次，最多加\(l\)次，所以直接在\(SAM...

SAM 字符串 Codeforces

2020-06-12

0 530

UOJ #62.【UR #5】怎样跑得更快

Description 传送门 Solution 如题，有 \[\sum_{j = 1} ^ n gcd(i, j) ^ c \times lcm(i, j) ^ d \times x_j \equiv b_i \pmod p \] 首先先把\(lcm(i, j)\)用\(\f...

数论莫比乌斯反演 UOJ

2020-06-12

0 369