F. Occurrences
好难想的一道题，光是 \(a\) 需要满足什么性质就要斟酌好久。。。
首先比较显然的性质是：对于 \(a\) 中某个 \(A_{i}\) 的出现，必然也会伴随着 \(A_{i}\) 的所有子数组的一次出现。那么其实题目约束中的 “不超过” 就可以改成 “必须相等”。
对于 \(\forall A_{i}\)：
- 若 \(A_{i}\) 中存在某个元素 \(v\) 的出现次数 \(> 1\) 次，那么只要 \(A_{i}\) 在 \(a\) 中出现一次，\(v\) 就会出现两次，显然不符约束。因此此时 \(A_{i}\) 就不能在 \(a\) 中出现，进而可推导 \(A_{i}\) 的任何一个元素都不能在 \(a\) 中出现。容易证明这个条件是充要的。
- 否则，\(A_{i}\) 中的每个元素都是唯一的。那么我们也有结论：对于 \(a\) 中出现的 \(\forall A_{i}\) 中的元素，在 \(a\) 中的左侧与右侧必然存在相应的左端点（\(A_{i,1}\)时为自身）与右端点（\(|A_{i}|=m\), \(A_{i,m}\)时为自身），使得这一段区间在 \(a\) 中构成的子数组与 \(A_{i}\) 相同，否则就会出现子数组有贡献而 \(A_{i}\) 无贡献的情况，使得性质不满足。这里贴一下官方题解中的定义，更有助于后面的分析：
由上图可知，每个 \(A_{i}\) 都会对 \(a\) 中的某些值有出现顺序上的要求：对于 \(\forall A_{i,j}\)，只要在 \(a\) 中出现并且不是 \(A_{i}\) 结尾，其后面必须紧跟一个 \(A_{i,j+1}\)。这种约束很容易想到用图论来建模。于是我们可以以值域 \([1,k]\) 中的每个数为结点，按照 \(A_{i}\) 来连若干条有向边。
建完图后，我们会得到若干个弱连通分量（与强连通分量的唯一区别在于不考虑边的方向）。首先考虑 \(a\) 中一定不能出现哪些元素：
- 存在某个元素 \(v\) 的出现次数 \(> 1\) 次的 \(A_{i}\) 中的任何元素显然不能在 \(a\) 中出现（由上面分析得到）。
- 对于每个入度 \(>1\) 或出度 \(>1\) 的结点代表的元素，也一定不能出现在 \(a\) 中。因为入度 \(>1\) 代表着 \(v\) 的前一个元素不确定是哪个；同理出度 \(>1\) 代表着 \(v\) 的后一个元素不确定是哪个（有向边的顺序约束最终需要体现在序列 \(a\) 中，显然每个结点的入度和出度均不能超过 \(1\)）
- 在某个环中的元素也不能出现在 \(a\) 中，因为环中的每个点均有后继，会导致序列的无限增长。
由上面的分析可知，每个约束在有向图中的形式一定是一条链（每个点的入度和出度都不超过 \(1\)，并且不是环）。于是我们可以预处理每个弱连通分量，最终得到若干条链，表示 \(a\) 中的元素顺序约束。
综上，考虑对满足条件的 \(a\) 计数。考虑 \(dp\)：
状态定义：\(dp_{i}\)：考虑 \(a_{1 \backsim i}\)，方案数。
由上面分析可知，\(a\) 中的序列一定是完整地由若干条链拼接得到。于是我们可以决策 \(a_{1 \backsim i}\) 的最后一条链，来统计方案数。设共 \(c\) 条链，第 \(i\) 条链的长度为 \(len_{i}\)，那么状态转移：
对于每个前缀都要用 \(c\) 条链转移，而链的数量级是 \(O(k)\) 的，因此这种做法的复杂度是 \(O(mk)\) 的，需要优化。
我们发现，对于长度相同的链是可以合并在一起转移的。而由于所有链的总长不超过值域大小 \(k\)，因此链的不同长度的种类数不会超过 \(O(\sqrt k)\)。设长度为 \(len\) 的链的数量为 \(cnt_{len}\)，则状态转移：
总复杂度 \(O(m \sqrt k)\)，\(m,k\) 最大均为 \(3e5\)。这也是这道题时限开 \(7s\) 的原因。
写好后 \(WA\) 了两发，想了一会儿后发现建图时可能会有重边，对判环有影响。判完重边之后再交就过了。。。
code