网站建设实训个人总结3000,长沙房地产市场分析,wordpress获取文章标签,腾讯cdn WordPress文章目录 P1226 【模板】快速幂题目分析代码 P3367 【模板】并查集题目分析代码 P3378 【模板】堆题目分析代码 P3383 【模板】线性筛素数题目分析代码 P3366 【模板】最小生成树题目分析代码 P3390 【模板】矩阵快速幂题目分析代码 【模板】单源最短路径题目分析代码 P1226 【… 文章目录 P1226 【模板】快速幂题目分析代码 P3367 【模板】并查集题目分析代码 P3378 【模板】堆题目分析代码 P3383 【模板】线性筛素数题目分析代码 P3366 【模板】最小生成树题目分析代码 P3390 【模板】矩阵快速幂题目分析代码 【模板】单源最短路径题目分析代码 P1226 【模板】快速幂
题目地址【模板】快速幂
题目分析
快速幂原理 以这个为例 a 2 , b ( 11 ) 10 ( 1011 ) 2 a2,b(11)_{10}(1011)_{2} a2,b(11)10(1011)2求 2 11 。 2^{11}。 211。 2 11 2 8 × 2 0 × 2 2 × 2 1 2^{11}2^{8} \times 2^{0} \times 2^{2} \times 2^{1} 21128×20×22×21幂的次数正好对应 ( 1011 ) 2 (1011)_{2} (1011)2 那么只需循环判断即可。
“”“
ans 1
base a 2^1第一次循环
b 12 0b1011 # 0b是python里的二进制标志
1 0b0001
b 1 0b0001 1
ans ans * base 1 * 2 2
base 2^2
b b 1 0b101第二次循环
b 1 0b001 1
ans 2 * 2^2 2^3
base 2^4
b b 1 0b10第三次循环
b 1 0b00 0
base 2^8
b b 1 0b1第四次循环
b 1 0b1 1
ans 2^3 * 2^8 2^11
base 2^16
b b 1 0 # b0 退出循环最后的ans 2^11.
计算次数由O(b) log(b)
”“”通常对于快速幂一般结合取余(mod)来考。了解原理即可 ( A B ) m o d P ( A m o d P B m o d P ) m o d P (AB) \, mod \, P (A \, mod \, P B \, mod \,P)\,mod\,P (AB)modP(AmodPBmodP)modP ( A × B ) m o d P ( ( A m o d P ) × ( B m o d P ) ) m o d P (A \times B)\,mod\,P((A\,mod\,P) \times (B\,mod\,P))\,mod\,P (A×B)modP((AmodP)×(BmodP))modP 见代码。
代码
# 快速幂
def quickpower(a: int, b: int):base aans 1while b 0:if b 1:ans * basebase * baseb b 1return ans# 快速幂应用--取余
def quickmod(a: int, b: int):base aans 1while b 0:if b 1:ans * baseans % pbase * basebase % pb b 1return ansa, b, p map(int, input().split())
# 只能过一半百分之五十
# ans quickpower(a, b) % p
# print(f{a}^{b} mod {p}{ans})
# AC
ans quickmod(a, b)
print(f{a}^{b} mod {p}{ans})P3367 【模板】并查集
题目地址【模板】并查集
题目分析
这个找并集就是找他们共同的祖先。就以题目例题来看. n 4, m 7
fa [0, 1, 2, 3, 4]① 1、2的祖先分别为1、2 不相等输出N
② 将1、2合并设2为1的祖先fa [0, 2, 2, 3, 4]
③ 1、2的祖先分别为2、2 相等输出Y
④ 将3、4合并设4为3的祖先fa [0, 2, 2, 4, 4]
⑤ 1、4的祖先分别为2、4 不相等输出N
⑥ 将2、3合并设3是2的祖先fa [0, 2, 3, 4, 4]
⑦ 1的爸爸是22的爸爸是33的爸爸是4 1的祖先是44的祖先是4相等输出Y这个找祖先的函数递归一下就可以了。 见代码
代码
# 递归找爹
def find(x):if x fa[x]:return xfa[x] find(fa[x])return fa[x]n, m map(int, input().split())
fa [i for i in range(n1)] # 初始化自己为爹
for _ in range(m):z, x, y map(int, input().split())a, b find(x), find(y)if z 1:fa[a] belse: # z 2if a b:print(Y)else:print(N) P3378 【模板】堆
题目地址【模板】堆
题目分析
代码 P3383 【模板】线性筛素数
题目地址【模板】线性筛素数
题目分析
代码 P3366 【模板】最小生成树
题目地址【模板】最小生成树
题目分析
代码 P3390 【模板】矩阵快速幂
题目地址【模板】矩阵快速幂
题目分析
代码 【模板】单源最短路径
见【模板】单源最短路径
题目分析
见【模板】单源最短路径
代码
见【模板】单源最短路径
