首页 > 其他分享 >WC2021

WC2021

时间:2024-08-27 16:48:18浏览次数:13  
标签:括号 pmod dfrac dd 合法 WC2021 equiv

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

相关文章

  • P7324 [WC2021] 表达式求值 题解
    题目链接点击打开链接题目解法不错的题首先建出表达式树说实话我一开始不知道怎么建,但看了代码之后就懂了这里简单说一下:假如要对区间\([l,r]\)建树,分\(E_r=)\)和\(E_r\neq)\)的情况\(E_r=)\),找到匹配的左括号,递归下去建树\(E_r\neq)\),\(r\)可以作为单独的一个......
  • luogu P7323 [WC2021] 括号路径
    题面传送门为了方便,我们仅保留\((v,u,-w)\)的反向边。可以发现,如果某个点\(u\)到\(v_1,v_2\)同时有相同边权的边,那么\((v_1,v_2)\)就是一个合法的点对。因此可以这样暴力......