hdu 3461 Code Lock

<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=3461">点击打开hdu 3461</a>

思路: 并查集+离散化+快速幂

分析:

1 题目给定长度为n的字符串，然后给定m个操作，询问最后的不同字符串的个数

2 考虑长度为n的时候，因为每个字符有26种情况('a'~'z')，所以有26^n。因为有m次的操作，题目中说了如果可以被变换那么认为是相同的字符串，那么不同的字符串就是所有不被操作区间的组合

3 那么我们利用并查集去求有操作的集合的个数，比如[1,3],[3,5]和[1,5]是三个集合，而[1,3],[4,5]和[1,5]则是2个集合

4 对于区间[l,r]，那么我们一般转化为处理(l-1,r],这样不用考虑端点的问题了，最后利用快速幂求出ans即可

代码:

<a target="_blank" href="http://acm.hdu.edu.cn/showproblem.php?pid=3461"></a>