[题解] [IOI2008] Island

[题解] [IOI2008] Island

给出一个 $n$ 个点的基环树森林(每一个点有一条无向边),让你求出所有基环树的直径(即一条不经过重复点的基环树上的最长路径)之和。

$2\le n\le 10^6$

阅读更多
[题解] [TJOI2013] 单词

[题解] [TJOI2013] 单词

一篇论文是由许多单词组成,但小张发现一个单词会在论文中出现很多次,问每个单词分别在论文中出现了多少次。

$1\le n \le 200$,单词总长度不超过 $10^6$

阅读更多
关于广义后缀自动机

关于广义后缀自动机

约束

tar[x][c]:SAM 转移

pre[x]:常用名有 linkfail(反正就那个东西)

len[x]:结点 x 代表的最长字符串的长度


广义后缀自动机(下文用广义 SAM 指代),即用多个字符串的后缀建出的一个后缀自动机,拥有和后缀自动机相似的性质。

有三种较流传广泛的广义后缀自动机写法:

阅读更多
[题解] [HNOI2008] Cards

[题解] [HNOI2008] Cards

给你 $n$ 张牌要求染成红、蓝、绿三种颜色(求染出 $S_r$ 张红色,$S_b$ 张蓝色,$S_g$ 张绿色),并给定了 $m$ 种洗牌方案,这些洗牌方案满足:

  • 任意多次洗牌都可用这 $m$ 种洗牌法中的一种代替
  • 对每种洗牌法,都存在一种洗牌法使得能回到原状态

问有多少种不同的染色方案。两种染色方法相同当且仅当其中一种可以通过任意的洗牌法(即可以使用多种洗牌法,而每种方法可以使用多次)洗成另一种。

$m\le 60$,$\max{S_r,S_b,S_g}\le20$

阅读更多
[题解] [SCOI2010] 序列操作
FFT | 3 | 数论变换NTT基础
FFT | 2 | FFT在字符串匹配中的应用
FFT | 1 | 基础傅立叶变换知识

FFT | 1 | 基础傅立叶变换知识

引入问题

什么是多项式卷积

假设我们现在有多项式 $f(x)$ 和 $g(x)$ ,它可以被表示为

$$
f(x)=\sum_{i=0}^{n-1} a_i\cdot x^i\\
g(x)=\sum_{i=0}^{m-1} b_i\cdot x^i
$$

其中 $a$ 和 $b$ 为系数数组, $n$ 和 $m$ 分别为两个多项式的长度

那么它们的卷积为

$$
f(x)\bigotimes g(x)=\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i\cdot b_j\cdot x^{i+j}
$$

也可以表示成

$$
c_k=\sum_{i=0}^ka_i\cdot b_{k-i}
$$

其实就是简单的两个多项式相乘

阅读更多
分数规划/01规划

分数规划/01规划

今天也是Mivik被智商碾压的一天啊QwQ

分数规划 貌似 和01规划是一个东西吧QwQ

问题

我们现在要求这样一个式子的最大值

$$
\frac{\sum e_i.a}{\sum e_i.b}
$$

其中 $e$ 中的元素是可以选择的,且 $e_i.a > 0$ ,$ e_i.b > 0$

阅读更多