完全没思路，题目也没看懂，直接参考大牛们的解法。
http://www.myexception.cn/program/723825.html
题意是说有N个字母组成的密码锁，如[wersdfj],每一位上的字母可以转动，变成字母表中的下一位。 如w可转动变成x，z变成a。但是题目规定，只能同时转动某个区间上的所有字母，如[1，3]， 那么第1到第3个的所有字母要同时转动， 那么[wersdfj]经过一次操作就变成[xfssdfj].一共有M个区间是可以操作的。
经过可操作区间进行的操作得到的所有情况，都是同一个的。 也就是指不管我在题目给出的某一个区间怎么转动，其它位上的字母都不变，它仍视为同一种。
假如原本是[abc]，给出可操作区间[1,2]，即我可以转动第一个、第二个字母，当然是同时转动的。 由于[1,2]区间情况所能变化得到的，都视为同一种。我不妨固定第一个字母，就为a，其余25个字母可有a变化得到。 那么第二位上的字母，就可以有26种可能，也就是[1,2]区间可能的情况有26种，再加上独立的第3个字母有26种可能，总共有26^2种。
也就是说，有n个字母组成的密码锁，原本会有26^n种。如果有一个可操作区间，那么会有26次变换。 相当于这个操作区间就减少了原来的26种,总的也就变为26^(n-1)。 也就是现在我们要统计有多少个可操作区间，若为cnt，则答案即为26^(n-cnt)，这当然要用到快速幂。
至于怎么求区间个数，采用的是区间合并的方法，给出一个区间[L,R]，若可以合并，则cnt++。
不过这里有一个情况要注意：
假设有区间[1,3],[3,5],[1,5],如果按照Union(L, R)来算， 那么[1,3],[3,5]可以合并，cnt为2， 但[1,5]因为已经属于同一个集合，则不合并。那么得到两种可操作区间。 但实际上是有3中可操作区间的，因为1～3， 3～5是有重叠了3的两个区间，所以1～5区间的情况不包括在前两个区间的情况内。
如果是[1,3],[4,5],[1,5]，如果合并的话，cnt为3，但实际就只有两种情况，因为最后一种的转动情况包含在了前两种转动的情况之内了。
这里大牛们就想出了一个解决办法：
合并[L-1,R]或者[L,R+1]。
如上述区间[1,3],[3,5],[1,5],[1,3]合并的是[0,3],[3,5]合并的是[2,5]，[1,5]合并的是[0,5]，这样cnt=3；
如果是[1,3],[4,5],[1,5]，那么cnt=2；
#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> using namespace std; const int maxn=10000005; const int mod=1000000000+7; int father[maxn]; int n,m; void init(){ for(int i=0;i<=n;i++) father[i]=i; } int find_root(int x){ if(father[x]!=x) father[x]=find_root(father[x]); return father[x]; } bool Union(int a,int b){ int x=find_root(a); int y=find_root(b); if(x==y) return false; father[y]=x; return true; } //注意要long long ,即使a(26)也要定义成long long long long quickPow(long long a,int b){ long long ans=1; while(b>0){ if(b&1){ ans=(ans*a)%mod; } a=a*a%mod; b=b>>1; } return ans; } int main() { int l,r; while(scanf("%d%d",&n,&m)!=EOF){ int cnt=0; init(); for(int i=1;i<=m;i++){ scanf("%d%d",&l,&r); l--; if(Union(l,r)) cnt++; } long long ans=quickPow(26,n-cnt); printf("%I64d ",ans); } return 0; }