51nod 题目口胡(1)

1039 X^3 Mod P

令g为P的原根，不妨设 $g^{t_1}\equiv X \pmod{P}$gt1​≡X(modP)，$g^{t_2}\equiv A \pmod{P}$gt2​≡A(modP) （求离散对数）
显然有$3t_1 \equiv t_2 \pmod{P-1}$3t1​≡t2​(modP−1)
求出离散对数t2之后， $t_1=t_2/3$t1​=t2​/3 或 $t_1=(t_2+(P-1))/3$t1​=(t2​+(P−1))/3 或 $t_1=(t_2+2*(P-1))/3$t1​=(t2​+2∗(P−1))/3
除3必须是整除，所以答案可能有0个,1个或者3个。
单次时间复杂度$O(P^{1/4}\log{P}+P^{1/2})$O(P1/4logP+P1/2)

1144 打字的猴子

记$dp[i]$dp[i]为打出前$i$i个字符的期望时间，要打出前$i+1$i+1个字符需要先打出前i个字符，而下一个字符打对的概率只有$\frac{1}{n}$n1​，而打错字符会使状态从$i$i退回到$i$i之前的某个状态，用kmp计算所有打错子符后会退到的状态，根据方程计算即可。

1146 斐波那契字符串

记$g(n)$g(n)为字符串S在$f(n)$f(n)中出现的次数，则$g(n)=g(n-1)+g(n-2)+C(n)$g(n)=g(n−1)+g(n−2)+C(n)，其中$C(n)$C(n)为S部分在$f(n-1)$f(n−1)另一部分在$f(n-2)$f(n−2)中出现的次数。注意到S的长度只有$10^5$105，当$f(m)$f(m)长度超过S之后，符$f(m+2)=f(m)+f(m-1)+f(m)$f(m+2)=f(m)+f(m−1)+f(m)前后缀都是固定的，只需要计算前几项$g$g，之后快速幂。

1147 连分数

令$c_i=a_i+\frac{1}{c_{i+1}}$ci​=ai​+ci+1​1​，其中$c_i$ci​可以表示为$\frac{\sqrt{x}+y}{z}$zx​+y​，迭代计算找到循环节（循环节不长），矩阵快速幂。

• 点赞
• 收藏
• 分享
• • 文章举报

Deja_vuuu 发布了7 篇原创文章 · 获赞 0 · 访问量 635 私信 关注