WC2021

P7323 [WC2021] 括号路径

注意到合法二元组具有传递性，因此形成若干等价类。若两个点在同一个等价类内，则它们出边指向的点也在同一等价类内，这可以用启发式合并简单维护。

P7324 [WC2021] 表达式求值

首先建出表达式树。直接暴力计算复杂度不会低于 \(O(n|S|)\) 或 \(O(nm!)\)。因此考虑拆贡献，考虑一种颜色成为最终答案的方案数，注意到我们只关心另外 \(m-1\) 种颜色的权值和它的大小关系，因此可以优化到 \(O(m2^m|S|+nm)\)。尝试将 \(m\) 优化掉，那么状态中就不能记录最终答案的颜色，因此考虑只记录一个集合 \(A\) 表示 \(A\) 比 \(U-A\) 的所有颜色权值都更大。发现可以差分求得一种颜色成为答案的方案数，时间复杂度 \(O(2^m|S|+nm)\)。

P7325 [WC2021] 斐波那契

即询问最小的 \(n\) 满足 \(f_{n-1}a+f_nb\equiv 0\pmod m\)，其中 \(f\) 是斐波那契数列。如果 \(m\) 是质数那么显然可以变形为 \(-\frac{f_{n-1}}{f_n}\equiv \frac{b}{a}\pmod m\)，然后直接用哈希表维护。

否则就会出现不互质，不存在逆元的问题。先将 \(a,b,m\) 同时除以三者的 \(\gcd\)，得到 \(f_{n-1}a'+f_nb'\equiv 0\pmod{m'}\)。又注意到 \(\gcd(f_{n-1}a',m')=\gcd(f_nb',m')\)，同时由于 \(f_{n-1}\perp f_n\) 以及 \(\gcd(a',b',m')=1\)，因此

\[ p=\gcd(f_{n-1},m')=\gcd(b',m')\\ q=\gcd(f_n,m')=\gcd(a',m') \]

于是原式等价于

\[ \frac{f_{n-1}}{p}\frac{a'}{q}+\frac{f_n}{q}\frac{b'}{p}\equiv 0\pmod{\frac{m'}{pq}} \]

并且左边每项都和模数互质。于是我们枚举所有 \(m'\)，此时 \(f_n\) 的循环节为 \(O(m')\) 级别，然后把所有 \((\frac{\frac{f_{n-1}}{p}}{\frac{f_n}{q}},p,q,m')\) 四元组都扔进哈希表即可，算上求 \(\gcd\) 和逆元，时间复杂度为 \(O(\sigma(m)\log m+n\log m)\)。