遇到一个蜜钥问题，求解答。
Tom 最开始有一个密钥 s1，s1 是长度为 n 的由小写字母组成的字符串。Jerry也有一个长度为 n 的由小写字母组成的密钥 s2。现在有 m 组关系，每组关系由两个数字 [u,v] 构成 (1<=u,v<=26)，表示 26 个字母表中的第 u 个小写字母可以直接转换为第 v 个小写字母。假设u=1，v=2,那么说明字母'a'可以直接转换为字母'b'。现在Tom对于s1的每个字母使用无数次转换，请判断 s1 能否转换为 s2。输入内容为四部分，第一部分为 n(1<=n<=100000)，代表字符串的长度。接下来两部分分别是长度为 n 的 s1,s2。第四部分为 m（1 <=m<=325），代表关系个数。接下来是 m 组 [u,v] 关系。如果 s1 能变成 s2, 则输出 YES, 否则输出NO。
写回答
-
经过0-2次变换后可以达到的字母的结果相当于changechange，0-3 次对应的相当于 changechangechange，0-n 次对应的就是 change^n。这是一个矩阵求幂的过程。对于求幂操作有可以加快计算的方法，叫做矩阵快速幂。这里用求数的次幂举例。假设要求x^13。直接的方法是进行 12 次相乘。我们可以观察到 13 =8+ 4+1=2^3+2^2+1 所以 x^13=x^8+x^4+ x=(x^4)^2+(x^2)^2+0(x)^2+x从右向左，每一项都是前一项的平方。这样原来需要 12 次乘法的操作变成了3次惩罚，3 次加法（第二项系数为 0，不用加）。与求数的次幂类似，矩阵也可以用相同的方法加速计算。对于这道题本身，因为矩阵中非 0 的结果表示可以进行变换，所以相乘时没有必要算出具体的值，只需要判断结果是否非 0。 因为只有 26 个字母，所以只需要算到 26 次幂就可以了，也可以计算 32 次幂来去掉加法的部分。 时间复杂度 O(5262626) 5 是求 32 次幂需要的矩阵乘法次数。262626 是一次乘法需要的时间复杂度。 空间复杂度 O(226*26) 一个二维数组保存当前结果，一个保存相乘后的结果 输入：6 "aabbcc" "cdbcad" 4 [[1,3],[3,1],[1,4],[2,3]] 输出："YES" 注意 可以转换多次，比如 a 可以转换为 b，而 b 可以转换为 c，则 a 可以转换为 c。 样例：aabbcc->cabbcc->cdbbcc->cdbccc->cdbcac->cdbcaa->cdbcad
2021-12-23 18:45:59赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
