自闭场.
$masodik$
维护 $r$ 和 $c$ 的下凸壳,当前哪个斜率大走哪个.
$count$
$60$ 分的做法可以直接枚举 $a,b$ ,此时可以唯一确定 $c,d$ ,用 $hash$ 检验,时间复杂度 $O(n^2)$ ,但跑不满.
另外一个 $O(n^2)$ 的做法是枚举 $len=b-a+1$ .
当 $len$ 固定时,将串右移 $len+F$ 位,合法的 $(a,b,c,d)$ 中, $(a,b)$ 段和 $(c,d)$ 段就会匹配上.
于是扫一遍,计算匹配数,就可以得出 $len$ 确定时的解,时间复杂度 $O(n^2)$ .
考虑进行优化,仍然枚举 $len$ ,将原串按 $len$ 分段,发现下面这样的红色匹配是没有意义的:
因为红色匹配的长度不会超过 $len$ ,而有效的匹配一定是像绿色匹配那样跨越边界的.
段边界的匹配可以转化为段两端的 $LCP$ 和 $LCS$ ,二分 + $hash$ 来求.
用这一段的 $LCP$ 和前一段的 $LCS$ 组合,若 $LCS\ge len$ ,则这段的解全都合法.
否则这段的解有 $LCP+LCS-len+1$ 个.
时间复杂度 $O(n\log^2 n)$ .
这里的 $LCS$ 指最长公共后缀.
$theory$
先考虑 $m=0$ 的情况,此时相当于求解 $n^{2n}\equiv x$ .
保证有解,所以 $x$ 一定是二次剩余,等价于求解 $n^n\equiv \sqrt x \pmod p$ .
令 $n\equiv \sqrt x \pmod p,n\equiv 1 \pmod { p-1}$ .
因为 $\gcd(p,p-1)=1$ ,所以可以 $crt$ 合并得出一个合法解.
对于 $m>0$ 的情况,尝试枚举 $n\equiv t\pmod p$ ,只要 $x-t^m$ 在模 $p$ 意义下是二次剩余,就可以沿用上面的做法.
由于一个数是二次剩余的概率为 $\frac 1 2$ ,所以期望步数很小,可以视作常数.
时间复杂度 $O(\sqrt p)$ .