Code Lock HDU 3461

给定由N个字母组成的密码锁,如【abcdef】每一位字母都可以转动,转动该字母时,将变成它的下一个字母,如‘a'转动后是b,x转动后是y,

接着给定M个区间,每次转动给定区间内的所有字母,如密码锁【abcdef】,给定区间【1,3】转动这个区间一次后变为【bcddef】;

 

题解:  要是用并查集蒙的话,有可能就很容易的蒙出来了,但是要是证明的话还是有点难度的。。。。

待续:证明为什么加了一个区间然后可能的情况就是减少了26倍。

1、我们考虑这样一种情况就是,加入可重复的区间答案是不会发生变化的。

2、当我们加入不重复的区间之前,肯定有一种[x1,x2,x3....xn]!=[y1,y2,y3.....yn]变成相等,所以原来不相同的26中情况会变成相同的情况。所以答案就是原来的1/26.

原文地址:https://www.cnblogs.com/Heilce/p/6670168.html