cf1574 F. Occurrences

题意

Link

中文大意：让你构造字符串 \(a,a_i\le k\)。

记 \(s(b)\) 为字符串 \(b\) 在 \(a\) 中出现次数

给你 \(n\) 个限制字符串 \(A_i\),表示对于任意 \(A_i\) 子串 \(b\),\(s(A_i)\ge s(b)\)。

---

题解

思路还蛮好想，只要合法的字符串 \(a\) ,\(s(A_i)\le s(b)\)，所以现在情况只有取等。

首先排除 \(\exist\ j\not =k\quad s.t.\ A_{i,j}=A_{i,k}\)。

此后问题就变为如何决策 \(A_i,A_j\) 两个冲不冲突。

rephrase 问题，如果我们选字符 \(A_{i,1}\) 那么有必须选 \(A_{i,2}\),如此递推。

认为这是一个顺次向下钦定的问题。

建出图那么，我们只需要统计有向链的个数。

合法链长分别为 \(l_1,l_2\dots,l_k\)。

注意单个字符。

那么可以使用多项式求逆 \([x^n]\sum_{i=0}f^i(x)=[x^n]\frac{1}{1-f(x)}\)。

\(\texttt{Complexity : }\mathcal{O(n\log n)}\)。

发现 \(\sum_{i}l_i\leq n\) ,可以想到根号分治。

\(\texttt{Complexity : }\mathcal{O(n\sqrt n)}\)。

注意算链的时候不要怕麻烦，要考虑周全，或许我是对了，但是正式考试+31可不是什么好东西。

code 略。

---

11.16胡一个，有向链大概就是看成无向的，然后看能不能dfs完全？