给定 $n$ ，代表有 $n$ 种字符。再给出多个数组 $a$ ，记其长度为 $m$，$1\le a_i\le n$。每次随机写下出一个字符，求第一次写下这个数组（即写下的字符串后缀为该数组）期望要写多少个字符。

$1\le n,m\le 10^5$

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

$2\le n\le 10^6$

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

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

约束

tar[x][c]：SAM 转移

pre[x]：常用名有 link、fail 等 （反正就那个东西）

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

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

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

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

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

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

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

题目链接

题目大意

给定一个01序列，要求支持如下操作：

• 区间赋值
• 区间取反
• 查询区间内1的个数
• 查询区间内最多有多少个连续的1

什么是 $NTT$

就是把把 $FFT$ 中所有的单位根换成了整数的单位根，也就是原根的 $n$ 次幂

通常用于求模意义下的多项式卷积

在上一篇文章里面我们介绍了 $FFT/IFFT$ 的基本原理和应用，今天我们来了解一下 $FFT$ 在字符串匹配中的神奇应用

引入问题

什么是多项式卷积

假设我们现在有多项式 $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}
$$

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

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

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

问题

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

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

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