T1 括号路径
知识点:并查集,启发式合并。
发现如果存在 \(x\to y\) 的路径是合法的,那么同时也必然存在 \(y\to x\) 的路径合法,说明合法是双向的。而括号路径的合法性有是由传递性的,也就是如果 \(x\leftrightarrow y\) 合法,\(y\leftrightarrow z\) 合法,那么 \(x\leftrightarrow z\) 合法。
这也就意味着,是否存在合法路径是可以用集合划分的,这也就启发我们使用并查集维护。
而经典的括号序列定义,如果 \(S\) 是括号序列,那么 \((S)\) 是括号序列。那么我们只需要关注如何向外面套括号。发现如果由 \(u\to v\) 的 \(k\) 边和 \(u'\to v\) 的 \(k\) 边,那么 \(u\leftrightarrow u'\) 就是合法的,那么我们就可以将这两个点看成同一个点。
使用启发式合并维护合并的过程,用 map
存边,时间复杂度是 \(O(m\log^2m)\) 的。
T2 表达式求值
知识点:表达式维护,DP。
发现这种之和 \(\min\) 或 \(\max\) 有关的问题,一般可以先考虑如果只有 \(0\) 和 \(1\) 两种数的情况。
发现 \(m\) 很小,所以我们枚举 \(2^m\) 种哪些数是 \(0\) 哪些数是 \(1\) 的情况,然后考虑求由多少种 ?
的选择使得结果是 \(1\)。
把表达式建成数,可以通过直接维护 \(f_{i,0/1}\) 表示树上 \(i\) 子树内的表达式有多少种选择 ?
的方式使得答案为 \(0/1\)。
这个 DP 是容易的。
最后我们只需要考虑每一组 \(A_{*,j}\),我们这 \(m\) 个元素从小到大排序,对于每一个 \(\ge A_{*,j}\) 的所有元素,可以计算出它的贡献。
时间复杂度 \(O(|S|2^m+nm\log m)\)。
T3 斐波那契
知识点:数学
记 \(f_0=0,f_1=1,f_i=f_{i-1}+f_{i-2}(i\ge 2)\)
那么有 \(F_i=af_{i-1}+bf_i\)
我们要找 \(af_{p-1}+bf_p\equiv 0\pmod m\)。
令 \(b=-b\),有 \(af_{p-1}\equiv bf_p\pmod m\)。
令 \(d=\gcd(a,b,m)\),则 \(\dfrac{a}{d}f_{p-1}\equiv \dfrac{b}{d}f_p\pmod{\dfrac{m}{d}}\)
令 \(d'=\gcd(\dfrac{b}{d},\dfrac{m}{d})\),则 \(\dfrac{a}{d}\dfrac{f_{p-1}}{d'}\equiv\dfrac{b}{dd;}f_p\pmod {\dfrac{m}{dd'}}\)。
那么就有 \(\dfrac{a}{d}(\dfrac{b}{dd'})^{-1}\dfrac{f_{p-1}}{d'}\equiv f_p\pmod {\dfrac{m}{dd'}}\)。
那么 \(\dfrac{a}{d}(\dfrac{b}{dd'})^{-1}\equiv \dfrac{f_p}{\dfrac{f_{p-1}}{d'}}\pmod {\dfrac{m}{dd'}}\)。
所以我们知道 \(d,d',\dfrac{f_p}{\dfrac{f_{p-1}}{d'}}\bmod {\dfrac{m}{dd'}}\) 就可以去检验 \(p\) 是不是 \((a,b)\) 的解了。
而我们可以得到 \(d'=\gcd(f_{p-1},\dfrac{m}{d})\),所以只需要枚举 \(d\) 和 \(p\) 就可以了,而可以证明这样枚举的数量级是 \(m\log\log m\) 的。
然后判掉一些 corner case 即可。
标签:括号,pmod,dfrac,dd,合法,WC2021,equiv From: https://www.cnblogs.com/Xun-Xiaoyao/p/18382885